公司网站建设济宁,网站设计 工作,东莞企业网站推广怎么做,二手车的网站建设例子~~~~ 前言1. list是什么2. list接口函数的使用1. 构造相关默认构造n个val构造迭代器范围构造拷贝构造 2 赋值运算符重载函数2 析构函数3 迭代器相关begin 和 endrbegin 和rend 4 容量相关emptysize 5 元素访问相关frontback 6 修改相关push_backpop_backpush_frontpop_frontins… ~~~~ 前言1. list是什么2. list接口函数的使用1. 构造相关默认构造n个val构造迭代器范围构造拷贝构造 2 赋值运算符重载函数2 析构函数3 迭代器相关begin 和 endrbegin 和rend 4 容量相关emptysize 5 元素访问相关frontback 6 修改相关push_backpop_backpush_frontpop_frontinsert - 插入新值eraseresizeassignswapclear 7 其他操作相关reverse - 逆置sort - 排序unique - 去重merge - 合并remove - 删除值为val的元素remove_if - 删除满足条件的元素splice - 从list对象转移元素到另一个list对象 8 非成员函数swap 3. list的模拟实现基本框架定义节点结构定义链表结构定义迭代器结构 - 类的封装迭代器分类模板类的类型与内部类型的特殊使用方式版本1只支持非const对象基本结构构造函数*运算符重载-运算符重载前置运算符重载后置运算符重载前置--运算符重载后置--运算符重载!运算符重载运算符重载代码汇总 版本2支持const对象和非const对象基本结构*运算符重载-运算符重载代码汇总 版本3支持const对象和非const对象且简化写法基本结构*运算符重载-运算符重载前置后置前置--后置--!运算符重载运算符重载代码汇总 构造函数初始化链表 - 代码复用无参构造迭代器范围构造 拷贝构造函数传统写法 - 自己实现现代写法 - 复用 赋值运算符重载函数传统写法 - 自己实现现代写法 - 复用 析构函数正向迭代器相关beginend 增删inserterasepush_backpop_backpush_frontpop_frontclearswapresizesize 关系运算符重载! list与vector比较list与vector排序效率简要分析list与vector迭代器差异再次分析 - 调试 结语 前言
本节将介绍list的使用之后模拟实现list的基本功能最后将分析与连续顺序容器vector的差异。 1. list是什么
list是逻辑上的顺序容器实际list的储存中是不连续的相邻节点之间通过指针进行链接。 list是带头节点的双向循环链表在所有的链表中结构最复杂使用也最方便。 list在头部和尾部的插入和删除操作、中间部分的插入删除操作都是常数时间效率很高与连续顺序容器相比的优势是中间位置的插入和删除操作时间复杂度是常数时间 O ( 1 ) O(1) O(1)而像vector在中间插入或删除元素往往涉及到元素的移动时间复杂度是 O ( N ) O(N) O(N)。劣势是list作为不连续存储的顺序容器不能实现随机访问元素 O ( 1 ) O(1) O(1)需要从第一个元素开始依次查找直到找到或到最后一个元素为止时间复杂度是 O ( N ) O(N) O(N)。 2. list接口函数的使用
1. 构造相关
初始化list对象
默认构造 声明 list ();eg listint l1;n个val构造 声明 list (size_type n, const value_type val value_type());eg listint l1(5, 7); // l1: 7 7 7 7 7迭代器范围构造 声明 template class InputIterator
list (InputIterator first, InputIterator last);eg vectorint v{1, 2, 3, 4, 5};
listint l1(v.begin() 1, v.end()); // l1: 2 3 4 5拷贝构造 声明 list (const list x);eg listint l1(5, 6); // 6 6 6 6 6
listint l2(l1); // l2: 6 6 6 6 6 2 赋值运算符重载函数 声明 list operator (const list x);eg listint l1(4, 3); // l1: 3 3 3 3
listint l2(3, 6); // l2: 6 6 6
l2 l1; // l2: 3 3 3 32 析构函数
释放对象申请的所有资源为对象销毁做好准备。
~list();3 迭代器相关
迭代器是像指针一样的类型。
begin 和 end 声明 begin 返回第一个对象的所在位置的迭代器。 iterator begin();
const_iterator begin() const;end 返回最后一个对象所在位置的下一个位置的迭代器。 iterator end();
const_iterator end() const;eg listint l1{1,2,3,4,5};
listint::iterator it l1.begin();
while (it ! l1.end()) {cout *it ;it;
}
cout endl endl; // 结果为 1 2 3 4 5rbegin 和rend 声明 rbegin 返回第一个对象的前一个位置的迭代器。 reverse_iterator rbegin();
const_reverse_iterator rbegin() const;rend 返回最后一个对象的迭代器。 reverse_iterator rend();
const_reverse_iterator rend() const;eg listint l1{1,2,3,4,5};listint::reverse_iterator rit l1.rbegin();
while (rit ! l1.rend()) {cout *rit ;rit;
}
cout endl endl; // 结果为 5 4 3 2 14 容量相关
empty 声明 判断list对象是否为空是返回true反之返回false。 bool empty() const;eg listint l1;
l1.empty(); // true
l1.push_back(10);
l1.empty(); // falsesize 声明 返回list对象的元素个数 size_type size() const;5 元素访问相关
front 声明 返回第一个有效元素的引用。 当list为空时调用front函数会产生未定义的行为。 reference front();
const_reference front() const;eg listint l1{1,2,3,4,5}; // l1: 1 2 3 4 5
l1.front(); // 1back 声明 返回最后一个元素的引用。 当list为空时调用back函数会产生未定义的行为。 reference back();
const_reference back() const;eg listint l1{1,2,3,4,5}; // l1: 1 2 3 4 5
l1.back(); // 56 修改相关
push_back 声明 尾插一个新元素 void push_back (const value_type val);eg listint l1{1,2,3,4,5}; // l1: 1 2 3 4 5
l1.push_back(10); // l1: 1 2 3 4 5 10
l1.size() // 6pop_back 声明 尾删一个元素。 当list对象为空时调用该函数程序将会出错。 void pop_back();eg listint l1{1,2,3,4,5}; // l1: 1 2 3 4 5
l1.pop_back(); // l1: 1 2 3 4
l1.size() // 4push_front 声明 头插一个新元素 void push_front (const value_type val);eg listint l1{1,2,3,4,5}; // l1: 1 2 3 4 5
l1.push_front(9); // l1: 9 1 2 3 4 5
l1.size() // 6pop_front 声明 头删一个元素 当list对象为空时调用该函数程序将会出错。 void pop_front();eg listint l1{1,2,3,4,5}; // l1: 1 2 3 4 5
l1.pop_front(); // l1: 2 3 4 5
l1.size() // 4insert - 插入新值 声明 在迭代器pos指向的元素之前插入一个值为val的元素。 iterator insert (iterator pos, const value_type val);eg listint l1{1,2,3,4,5}; // l1: 1 2 3 4 5
listint::iterator pos find(l1.begin(), l1.end(), 3);l1.insert(pos, 9); // l1: 1 2 9 3 4 5声明 在迭代器pos指向的元素之前插入n个值为val的元素。 void insert (iterator pos, size_type n, const value_type val);eg listint l1{1,2,3,4,5}; // l1: 1 2 3 4 5
listint::iterator pos find(l1.begin(), l1.end(), 3);l1.insert(pos, 3, 6); // l1: 1 2 6 6 6 3 4 5声明 在迭代器pos指向的元素之前插入指定迭代器范围内的所有元素。 指定的迭代器范围是左闭右开区间。 template class InputIterator
void insert (iterator pos, InputIterator first, InputIterator last);eg listint l1{1,2,3,4,5}; // l1: 1 2 3 4 5
vectorint v{7, 8, 9, 0};
listint::iterator pos find(l1.begin(), l1.end(), 3);l1.insert(pos, 3, 6); // l1: 1 2 7 8 3 4 5erase 声明 删除迭代器pos指向的元素 iterator erase (iterator position);eg listint l1{1, 2, 3, 4, 5}; // l1: 1 2 3 4 5
listint::iterator pos find(l1.begin(), l1.end(), 3);
if (pos ! l1.end()) {l1.erase(pos); // l1: 1 2 4 5a
}声明 删除迭代器范围内的所有元素。 iterator erase (iterator first, iterator last);eg listint l1{1, 2, 3, 4, 5}; // l1: 1 2 3 4 5
listint::iterator pos find(l1.begin(), l1.end(), 3);
l1.erase(l1.begin(), l1.end()); // l1: 空resize 声明 设置list对象的大小为n每个元素都使用val初始化 如果 n 大于list对象的大小就尾插新元素直到list对象大小恰好为n 如果 n 小于list对象的大小就尾删元素直到list对象大小恰好为n 如果 n 等于list对象大小就什么也不做。 void resize (size_type n, value_type val value_type());eg listint l1{1,2,3,4,5}; // l1: 1 2 3 4 5
l1.size(); // 5l1.resize(8, 9); // l1: 1 2 3 4 5 8 8 8
l1.size(); // 8l1.resize(3, 1); // l1: 1 2 3
l1.size(); // 3assign
用新值替换就值 声明 使用n个val赋值给list对象。 list对象的大小可能发生变化。 void assign (size_type n, const value_type val);eg listint l1{1, 2, 3, 4, 5}; // l1: 1 2 3 4 5
l1.size(); // 5
vectorint v{2, 2, 3, 3};
l1.assign(4, 6); // l1: 6 6 6 6
l1.size(); // 4声明 使用指定迭代器范围内的所有元素赋值给list对象。 template class InputIterator
void assign (InputIterator first, InputIterator last);eg listint l1{1, 2, 3, 4, 5}; // l1: 1 2 3 4 5
l1.size(); // 5
vectorint v{2, 2, 3, 3};// 4
l1.assign(v.begin(), v.end()); // l1: 2 2 3 3
l1.size(); // 4swap 声明 交换两个list对象的内容。 void swap (list x);eg listint l1{1, 2, 3, 4, 5};
l1.size();
listint l2{2, 2, 3 ,3};
l2.size();l1.swap(l2);
// l1: 2 2 3 3 size: 4
// l2: 1 2 3 4 5 size: 5clear 声明 删除list对象的所有元素并使list对象的大小为0。 void clear();eg listint l1{1, 2, 3, 4, 5};// l1: 1 2 3 4 5
l1.size(); // 5l1.clear(); // 清空l1
l1.size(); // 07 其他操作相关
reverse - 逆置 声明 逆置list对象的所有元素。 void reverse();eg listint l1{1, 2, 3, 4, 5}; // l1: 1 2 3 4 5
l1.reverse(); // l1: 5 4 3 2 1
reverse(l1.begin(), l1.end()); // l1: 1 2 3 4 5sort - 排序 声明 对list对象的所有元素进行排序无参时采用默认排序规则有参时传入函数指针或仿函数使用函数或仿函数定义的规则。 排序方法是归并排序。 void sort();template class Compare
void sort (Compare comp);eg listint l1{1, 3, 5, 2, 4, 6}; // l1: 1 3 5 2 4 6
l1.sort(); // l1: 1 2 3 4 5 6// 传入函数指针
listint l2{ 1, 3, 5, 2, 4, 6 }; // l2: 1 3 5 2 4 6
l2.sort(compareint); // l2: 6 5 4 3 2 1// 传入函数对象
listint l3{ 1, 3, 5, 2, 4, 6 }; // l3: 1 3 5 2 4 6
l3.sort(comint()); // l3: 6 5 4 3 2 1从大到小排序
templateclass T
bool compare(const T t1, const T t2) {return t1 t2;
}从大到小排序
templateclass T
struct com {bool operator()(const T t1, const T t2) {return t1 t2;}
};unique - 去重 声明 无参数时删除相邻的重复元素 有参数时参数是一个函数指针或函数对象删除的不再是重复的相邻元素而是满足传入参数所设置的条件的元素 unique函数不对list对象所有参数进行排序所以在使用该函数之前需要额外调用排序函数进行排序以保证重复的元素是相邻的。 void unique();template class BinaryPredicate
void unique (BinaryPredicate binary_pred);eg listint l1{3, 2, 3, 1, 1, 2, 2}; // l1: 3, 2, 3, 1, 1, 2, 2// 不排序直接去重
l1.unique(); // l1: 3, 2, 3, 1, 2listint l2{3, 2, 3, 1, 1, 2, 2}; // l2: 3, 2, 3, 1, 1, 2, 2// 先排序在去重
l2.sort(); // l2: 1, 1, 2, 2, 2, 3, 3
l2.unique(); // l2: 1, 2, 3merge - 合并 声明 合并两个已经排好序的list对象 无参时按默认规则把x中的所有元素依次转移到本list对象中转移的操作为把x的元素的值依次与本list对象元素的值进行比较如果x的元素的值大于比较的值则把x的元素插入到比较的元素之后反之就继续比较直到最后一个元素。转移完成后x对象就为空了。 有参时区别是传入的函数指针或函数对象定义了比较的规则转移时不在根据默认默认的规则进行。 void merge (list x);template class Compare
void merge (list x, Compare comp);eg listint l1{1, 9, 7, 6, 4}; // l1: 1 9 7 6 4 size: 5
listint l2{3, 2, 8}; // l2: 3 2 8 size: 3l1.sort(); // l1: 1 4 6 7 9
l2.sort(); // l2: 2 3 8l1.merge(l2); // l1: 1 2 3 4 6 7 8 9 size: 8// l2: size: 0remove - 删除值为val的元素 声明 void remove (const value_type val);eg listint l1{0, 1, 2, 3, 3, 4, 3}; // l1: 0, 1, 2, 3, 3, 4, 3 size: 7
l1.remove(3); // l1: 0, 1, 2, 4 size: 4remove_if - 删除满足条件的元素 声明 template class Predicate
void remove_if (Predicate pred);eg listint l2{0, 1, 2, 3, 4}; // l1: 0, 1, 2, 4 size: 4
l2.remove_if(isOdd()); // l1: 1, 3 size: 2是偶数就返回true
struct isOdd {
bool operator()(const int t) {return t % 2 0;
}
};splice - 从list对象转移元素到另一个list对象 声明 把list对象x的元素转移到另一个list对象的pos迭代器位置之前 // 转移x所有的元素
void splice (iterator pos, list x);
// 转移x迭代器i指向的元素
void splice (iterator pos, list x, iterator i);
// 转移x中指定迭代器范围的元素
void splice (iterator pos, list x, iterator first, iterator last);eg listint l1{1, 2, 3, 4, 5}; // l1: 1, 2, 3, 4, 5
listint l2{6, 7, 8}; // l2: 6, 7, 8
auto pos find(l1.begin(), l1.end(), 3);
l1.splice(pos, l2); // l1: 1, 2, 6, 7, 8, 3, 4, 5 size: 8// l2: size: 08 非成员函数
swap 声明 template class T
void swap (listT x, listT y);eg listint l1{1, 2, 3}; // l1: 1, 2, 3 size: 3
listint l2{6, 7, 8, 9}; // l2: 6, 7, 8, 9 size: 4
swap(l1, l2); // 交换 // l1: 6, 7, 8, 9 size: 4// l2: 1, 2, 3 size: 33. list的模拟实现
本次list实现是简化版主要以学习为主着重关注的是list的基本结构和其迭代器的具体实现。特别是const的迭代器与连续顺序容器的迭代器以Linux下G采用的SGI版本为例VS2019下vector的迭代器被封装为了一个类不再是原生指针有着巨大的差异如vector的迭代器是由原生指针typedef而来的而list迭代器必须封装为一个类才能达到与vector迭代器类似的行为。
基本框架
list是带头双向循环链表本次实现参考的是Linux中g中采用的STL的SGI版。
定义节点结构
由于list可以存放多种类型的数据需要采用类模板的方式。 包含三个成员变量 节点指针_prev: 指向前一个节点 节点指针_next: 指向后一个节点 _val: 节点储存该类型对应的元素 struct和class作用基本相同只是默认成员变量和成员函数是public的。 下文定义的list类模板需要在类内访问节点的成员变量和成员函数直接使用struct定义节点结构就可以方便实现需求。
templateclass T
struct __list_node {__list_node(const T val):_val(val),_prev(nullptr),_next(nullptr){ }__list_node* _prev;__list_node* _next;T _val;
};定义链表结构
链表结构list也是一个类模板因为其节点储存的元素类型不确定 list的成员变量有两个 节点指针_phead: 指向头结点头结点是整个链表的开始但不存放有效元素 _size: 表示当前链表的有效节点个数不包括头结点 templateclass T
class list {typedef __list_nodeT node; // 对节点类实例化重定义以简化写法
public:typedef __list_iteratorT iterator; // 迭代器类型typedef __list_const_iteratorT const_iterator;
private:node* _phead;size_t _size;
};定义迭代器结构 - 类的封装
迭代器分类 原生指针实现 类的封装实现 模板类的类型与内部类型的特殊使用方式
类名与类型的区别 普通类类名就是类型 类模板类名模板参数才是类型 例外是在类内可以省略模板参数只写类名表示类型 但是并不推荐这种写法应该写出具体完整的类型防止以后给自己或他人造成困扰 例如标准库中list的构造实现
版本1只支持非const对象
迭代器对于链表来说是一个行为像指针一样的类型。 指针支持的操作有 解引用*、-、前置、后置、前置–、后置–、指针比较操作 原生的节点指针 不支持、–操作解引用操作*得到的是整个节点而不是预期的节点的值-操作得到的是整个节点的地址而不是节点值的地址比较操作是符合的可以满足比较操作 如string、vector可以直接借助原生指针实现迭代器类型当然不是所有版本的string、vector的迭代器是原生指针可能是被封装为了一个复杂的类这依赖于它们天生的物理结构优势-连续存储。
原生指针的迭代器基本不能满足list对迭代器的需求所以需要把迭代器定义为一个单独的类依赖运算符重载功能对**运算符*、-、前置、后置、前置–、后置–**进行重载以便于满足我们对迭代器的预期。 对迭代器的预期 *得到节点内部的值-得到节点内部值的地址支持迭代器由当前节点指向下一个节点支持–迭代器由当前节点指向前一个节点 基本结构
迭代器只包含一个节点指针成员变量
templateclass T
struct __list_iterator {typedef __list_nodeT node;typedef __list_iteratorT iterator;node* _pnode;
};构造函数
实现基本的构造函数接受节点地址进行初始化 由于迭代器类本身不涉及资源的申请和释放故析构、拷贝构造、赋值运算符重载等函数都不需要显式实现由编译器生成默认的即可。
__list_iterator(node* pnode):_pnode(pnode){ }*运算符重载
得到节点内部的值并传引用返回 由于这个迭代器是非const的所以迭代器指向的节点也是非const的故返回类型是非const的T。
T operator*() {return _pnode-_val;
}-运算符重载
返回节点内部值的地址 由于这是非const迭代器所以迭代器指向的节点也是非const的故·返回类型是非const的T*
T* operator-() {return (_pnode-_val);
}前置运算符重载
迭代器指向下一个位置返回下一个位置的迭代器 即前置返回之前的值
iterator operator() {_pnode _pnode-_next;return *this;
}后置运算符重载
迭代器指向下一个位置返回当前位置的迭代器 即后置返回之后的值
iterator operator(int) {iterator tmp(*this);_pnode _pnode-_next;return tmp;
}前置–运算符重载
迭代器指向前一个位置返回前一个位置的迭代器
iterator operator--() {_pnode _pnode-_prev;return *this;
}后置–运算符重载
迭代器指向前一个位置返回当前位置的迭代器
iterator operator--(int) {iterator tmp(*this);_pnode _pnode-_prev;return tmp;
}!运算符重载
两个迭代器不相等即两个迭代器指向的节点不相等
bool operator!(iterator it) {return _pnode ! it._pnode;
}运算符重载
两个迭代器相等即两个迭代器指向的节点相等
bool operator(iterator it){return !(*this ! it);
}代码汇总
templateclass T
struct __list_iterator {typedef __list_nodeT node;typedef __list_iteratorT iterator;node* _pnode;__list_iterator(node* pnode):_pnode(pnode){ }T operator*() {return _pnode-_val;}iterator operator() {_pnode _pnode-_next;return *this;}iterator operator(int) {iterator tmp(*this);_pnode _pnode-_next;return tmp;}iterator operator--() {_pnode _pnode-_prev;return *this;}iterator operator--(int) {iterator tmp(*this);_pnode _pnode-_prev;return tmp;}bool operator!(iterator it) {return _pnode ! it._pnode;}bool operator(iterator it){return !(*this ! it);}
};版本2支持const对象和非const对象
版本1只实现了非const的迭代器对于const对象无法使用非const迭代器需要实现const迭代器 也许你有疑问为什么不是普通迭代器前加上const就是const迭代器呢 比如typedef const __list_iterator const_iterator; 首先清楚const迭代器的const实际上修饰的谁 肯定不是修饰的迭代器本身因为不管迭代器是const还是非const的都应该能满足、–操作而、–迭代器一定会改变迭代器故迭代器本身是非const的而简单的在普通迭代器之前加上const修饰而成的迭代器将会导致迭代器本身是const的而不能进行、–操作故其不是const迭代器。 那const修饰的是谁呢 const迭代器的const修饰的其实是迭代器指向的节点特别是包括节点内的值 const迭代器与普通迭代器的不同在于operator()和-operator返回类型分别是const T和const T 至于、–、比较大小操作同普通迭代器相同 需要一个新的类模板作为const迭代器类以满足于不同于普通迭代器的*和-操作
基本结构
templateclass T
struct __list_const_iterator {typedef __list_nodeT node;typedef __list_const_iteratorT const_iterator;node* _pnode;
};*运算符重载
返回迭代器指向节点内的值的引用 由于是const迭代器所以指向的节点是const的故返回类型是const T
const T operator*() {return _pnode-_val;
}-运算符重载
返回迭代器指向节点内的值的地址 由于是const迭代器所以指向的节点是const的故返回类型是const T*;
const T* operator-(){return (_pnode-_val);
}代码汇总
templateclass T
struct __list_const_iterator {typedef __list_nodeT node;typedef __list_const_iteratorT const_iterator;node* _pnode;__list_const_iterator(node* pnode):_pnode(pnode) { }const T operator*() {return _pnode-_val;}const_iterator operator() {_pnode _pnode-_next;return *this;}const_iterator operator(int) {const_iterator tmp(*this);_pnode _pnode-_next;return tmp;}const_iterator operator--() {_pnode _pnode-_prev;return *this;}const_iterator operator--(int) {const_iterator tmp(*this);_pnode _pnode-_prev;return tmp;}bool operator!(const_iterator it) {return _pnode ! it._pnode;}bool operator(const_iterator it){return !(*this ! it);}
};版本3支持const对象和非const对象且简化写法 版本1和版本2分别是普通迭代器的实现和const迭代器的实现仔细分析发现二者的代码基本上很相似主要区别是*和-操作返回的类型普通迭代器返回非const的类型const迭代器返回const的类型 为了简化代码书写选择合并这两个类模板把两个不同之处分别多增加参数进行表示 即操作的返回类型分为普通类型和const类型用参数Ref表示 -操作的返回类型分为普通类型和const*类型用参数Ptr表示 本质仍然是会生成两个迭代器类型只是不再是由我们自己显式写出而是由编译器根据类模板及其参数进行推导然后生成两个迭代器类型所做的工作没有减少只是交给类编译器承担。
基本结构
templateclass T, class Ref, class Ptr
struct __list_iterator {typedef __list_nodeT node;typedef __list_iteratorT, Ref, Ptr Self;node* _pnode;
};typedef __list_iteratorT, Ref, Ptr Self; 在一开始重定义了迭代器类型本身简化后续书写 如果还需要对迭代器模板参数进行改动只需要在此处进行修改即可不需要对后续涉及到的代码进行修改很便利。 *运算符重载
Ref operator*() {return _pnode-_val;
}-运算符重载
Ptr operator-() {return (_pnode-Val);
}前置
Self operator() {_pnode _pnode-_next;return *this;
}后置
Self operator(int) {Self tmp *this;*this;return tmp;
}前置–
Self operator--() {_pnode _pnode-_prev;return *this;
}后置–
Self operator--(int) {Self tmp(*this);_pnode _pnode-_prev;return tmp;
}!运算符重载
bool operator!(const Self it) const{return _pnode ! it._pnode;
}运算符重载
bool operator(const Self it) const {return !(*this ! it);
}代码汇总
templateclass T, class Ref, class Ptr
struct __list_iterator {typedef __list_nodeT node;typedef __list_iteratorT, Ref, Ptr Self;node* _pnode;__list_iterator(node* pnode):_pnode(pnode) { }Ref operator*() {return _pnode-_val;}Ptr operator-() {return (_pnode-Val);}Self operator() {_pnode _pnode-_next;return *this;}Self operator(int) {Self tmp *this;*this;return tmp;}Self operator--() {_pnode _pnode-_prev;return *this;}Self operator--(int) {Self tmp(*this);_pnode _pnode-_prev;return tmp;}bool operator!(const Self it) const{return _pnode ! it._pnode;}bool operator(const Self it) const {return !(*this ! it);}
};构造函数
初始化链表 - 代码复用
当定义一个list对象时将会调用构造函数对该对象进行初始化申请一个节点作为头结点并使节点指针均指向自己。 除了无参的构造函数需要这个功能迭代器范围做参数的构造函数、拷贝构造函数也需要该功能为了减少代码冗余便把申请头结点并处理的功能代码单独抽出来作为一个函数供其他需要的构造函数调用。
void initialize() {_phead new node(T());_phead-_next _phead;_phead-_prev _phead;_size 0;
}无参构造
list() {initialize();
}迭代器范围构造 范围: [ f i r s t , l a s t ) [first, last) [first,last) templateclass InputIterator
list(InputIterator first, InputIterator last) {initialize();while (first ! last) {push_back(*first);first;}
}拷贝构造函数
传统写法 - 自己实现 申请并初始化头结点 遍历链表lt依次取节点中的元素尾插到本链表this中 list(const listT lt) {initialize();node* cur lt._phead-_next;while (cur ! lt._phead) {push_back(cur-_val);cur cur-_next;}
}现代写法 - 复用 复用迭代器范围的构造函数先构造一个局部list对象tmp 交换tmp内指针_phead和this内指针_phead之后除了构造函数作用域tmp对象将自动销毁 list(const listT lt) {initialize();listT tmp(lt.begin(), lt.end());swap(tmp);
}赋值运算符重载函数
传统写法 - 自己实现 避免自己给自己赋值特殊判断一下比较两个list对象用到了!的运算符重载 赋值之前先依次delete本身的所有节点 listT operator(const listT lt) {if (*this ! lt) {clear();node* cur lt._phead-_next;while (cur ! lt._phead) {push_back(cur-_val);cur cur-_next;}}return *this;
}现代写法 - 复用 由传引用传参变为传值传参构造局部list对象lt 交换本对象this和lt内部的_phead指针 listT operator(listT lt) {swap(lt);return *this;
}析构函数 delete释放所有申请的节点包括头节点 复用了clear函数实现出头节点之外的所有节点的delete释放 ~list() {clear();delete _phead;_phead nullptr;
}正向迭代器相关
begin 头结点不是储存数据节点第一个储存数据的有效节点是头结点的下一个节点 iterator begin() {return iterator(_phead-_next);
}
const_iterator begin() const {return const_iterator(_phead-_next);
}end 循环链表最后一个节点的下一个节点是头结点 iterator end() {return iterator(_phead);
}
const_iterator end() const {return const_iterator(_phead);
}增删
insert 在pos迭代器指向的节点之前插入一个新节点 iterator insert(iterator pos, T val) {// prev cur newnodenode* newnode new node(val);node* cur pos._pnode;node* prev cur-_prev;newnode-_prev prev;prev-_next newnode;newnode-_next cur;cur-_prev newnode;_size;return iterator(newnode);
}erase
iterator erase(iterator pos) {assert(pos ! end());// prev cur nextnode* cur pos._pnode;node* prev cur-_prev;node* next cur-_next;prev-_next next;next-_prev prev;delete cur;--_size;return iterator(prev);
}push_back
void push_back(const T val){// phead tail newnodeinsert(end(), val);
}pop_back
void pop_back() {erase(--end());
}push_front
void push_front(const T val) {insert(begin(), val);
}pop_front
void pop_front() {erase(begin());
}clear
void clear() {iterator it begin();while (it ! end()) {it erase(it);}
}swap
void swap(listT lt) {std::swap(_phead, lt._phead);
}resize
void resize(size_t n, const T val T()) {size_t sizes size();if (n sizes) {while (sizes n) {push_back(val);sizes;}}else if (n sizes) {while (n sizes) {pop_back();--sizes;}}
}size
size_t size() const {return _size;
}关系运算符重载 bool operator(const listT lt) const {return _phead lt._phead;
}!
bool operator!(const listT lt) const {return !(*this lt);
}list与vector比较
list与vector排序效率简要分析
算法库algorithm中的sort函数底层使用快速排序实现不支持对list进行排序。 list内部实现了自己的排序函数sort该函数底层使用归并排序实现。 快速排序和归并排序的时间复杂度都是 O ( N ∗ l n N ) O(N*lnN) O(N∗lnN)但是实际上比较算法库中的sort函数和list内部的sort函数效率时对同一组数list内部实现的排序函数运行效率明显低于算法库中的排序函数。 使用同一组数不同情况下效率的比较
对vector进行排序list的元素先拷贝vector中对vector排序再拷贝回list中对list进行排序
void testSort() {int n 100000;vectorint v1;vectorint v2;listint l1;listintl2;srand(time(0));for (int i 0; i n; i) {int val rand();l1.push_back(val);l2.push_back(val);}v1.reserve(n);v2.reserve(n);for (auto e : l1) {v1.push_back(e);}// vector 对vector进行排序int begin1 clock();sort(v1.begin(), v1.end());int end1 clock();// list-vector-list list的元素先拷贝vector中对vector排序再拷贝回list中int begin2 clock();for (auto e : l1) {v2.push_back(e);}sort(v2.begin(), v2.end());int i 0;for (auto e : l1) {e v2[i];}int end2 clock();// list 对list进行排序int begin3 clock();l2.sort();int end3 clock();cout vector: end1 - begin1 endl;cout list-vector-list: end2 - begin2 endl;cout list: end3 - begin3 endl;
}list与vector迭代器差异再次分析 - 调试
相同点
迭代器的行为相似都支持*、-、、–、比较大小、范围for等操作都不支持迭代器相加操作
不同点
vector迭代器是一个原生指针实现不排除不同版本STL的vector迭代器也是类的封装实现list迭代器是类的封装实现vector的数据连续存储支持迭代器1、-1、迭代器之间的相减操作后指向相邻的下一个位置–后指向相邻的前一个位置list的节点在堆上随机存储节点之间在储存上没有先后顺序通过节点内的指针逻辑上链接相邻的节点不支持1、-1、迭代器相减操作后指向不相邻的下一个位置–后指向不相邻的前一个位置。 结语
本节简要介绍了list的接口函数重点实现了list的主要接口函数特别是封装的迭代器。list由于是节点链接insert之后直接插入了一个新的节点原迭代器还指向原节点并不会导致迭代器失效问题与连续容器不同erase之后删除了原有节点原迭代器指向了被删除的节点迭代器是失效的与连续容器相同。 T h e The The E n d End End
