C++初阶：STL之list类模板
发布时间：2024年01月19日
目录
一.list的介绍及使用
1.1.list的介绍
1.list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2.list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
3.list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
4.与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
5.与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素) 。
注意：
list列表是一种不能随机访问，但可以高效地在任意位置插入和删除元素的容器。列表容器一般实现为链表，而且是双向链表。
在链表中插入新的元素，只需要为新元素建立一个新链表结点，并修改前后两个结点的指针，而无须移动任何已有元素，因此在列表中插入新元素的效率很高，而且不会使任何已有元素的迭代器,指针,引用失效。
当删除列表中的元素时，需要释放被删除元素所占用的空间，然后修改前后两个结点的指针，也无须移动任何元素，因此效率也很高。执行删除操作时，只会使指向被删除元素的迭代器,指针,引用失效，而不会影响其他元素。
1.2.list的使用
list列表实现为一个双向链表，因为同为序列式容器，所以它的对外接口大部分与vector相同，因此我们学习起来也比较容易。
1.2.1.list的构造
| ???????????????????? 构造函数（constructor） | ???????????????????? 接口说明 |
| ?list (size_type n, const value_type& val = value_type()) | ??? 构造的list中包含n个值为val的元素 |
| ????????????????????????????????? list() | ?????????????????? 构造空的list |
| ???????????????????????? list (const list& x) | ????????????????? 拷贝构造函数 |
| ?????????? list (InputIterator first, InputIterator last) | ???? 用[first, last)区间中的元素构造list |
详解：
案例：
void list_test()
{
//list<T> lt;//创建一个空的列表对象
list<int> l1; //构造空的l1
//list<T> lt(n,elem);//创建一个列表对象，包含n个elem元素
list<int> l2(4, 10); //l2中放4个值为10的元素
//list<T> lt(begin,end);//创建一个列表对象，用[begin,end)区间的值为元素赋值
list<int> l3(l2.begin(), l2.end()); //用l2的[begin(),end())左闭右开的区间构造l3
//list<T> lt(lt1);//创建一个列表对象，用另一个对象初始化
list<int> l4(l3); //用l3拷贝构造l4
//以数组为迭代器区间构造l5
int array[] = { 16,2,77,29 };
list<int> l5(array, array + sizeof(array) / sizeof(int));
//列表格式初始化C++11
list<int> l6{ 1,2,3,4,5 };
}
int main()
{
list_test();
return 0;
}1.2.2.list iterator的使用
此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点。
| ? 函数声明 | ??????????????????????????????????????????? 接口说明 |
| ?begin+end | ???? 返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器 |
| rbegin+rend | 返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的reverse_iterator,即begin位置 |
图解：
迭代器有四种类型，分别为：
- ??? iterator：对于普通对象的正向迭代器；
- ??? const_iterator：对于const属性对象的正向迭代器；
- ??? reverse_iterator：对于普通对象的反向迭代器；
- ??? const_reverse_iterator：对于const属性对象的反向迭代器。
详解：
案例：
//list迭代器的使用
//注意：遍历链表只能用迭代器和范围for
void PrintList(const list<int>& l)
{
//注意：这里调用的是list的 begin() const，返回list的const_iterator对象
for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it)
{
cout << *it << " ";
//*it = 10; 编译不通过
}
cout << endl;
}
void list_test()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> l(array, array + sizeof(array) / sizeof(array[0]));
//使用正向迭代器遍历list中的元素
//list<int>::iterator it = l.begin(); //C++98中语法
auto it = l.begin(); //C++11之后推荐写法
while (it != l.end())
{
cout << *it << " ";
++it;
}
cout << endl;
//使用反向迭代器遍历list中的元素
//list<int>::reverse_iterator rit = l.rbegin(); //C++98中语法
auto rit = l.rbegin(); //C++11之后推荐写法
while (rit != l.rend())
{
cout << *rit << " ";
++rit;
}
cout << endl;
}
int main()
{
list_test();
return 0;
}运行结果：
注意：
1.begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动；
2.rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动。
1.2.3.list的capacity
| ?? 函数声明 | ??????????????????????????????????? 接口说明 |
| ???? empty | ???????????? 检测list是否为空，是返回true，否则返回false |
| ????? size | ???????????????????????? 返回list中有效节点的个数 |
详解：
案例：
void list_test()
{
list<int> lt1; //空链表
list<int> lt2(4, 10); //含有10个5
//判断lt1和lt2是否为空
cout << lt1.empty() << endl;
cout << lt2.empty() << endl;
//获取lt1和lt2中的元素个数
cout << lt1.size() << endl;
cout << lt2.size() << endl;
}
int main()
{
list_test();
return 0;
}
运行结果：
1.2.4.list的element access
| ????? 函数声明 | ????????????????????????????????? 接口说明 |
| ???????? front | ???????????????? 返回list的第一个节点中值的引用 |
| ???????? back | ??????????????? 返回list的最后一个节点中值的引用 |
详解：
因为list列表是由链表实现的，内存区域并不是连续的，所以无法用[ ]运算符来访问元素，也没有可随机访问元素的at()方法，但它提供了front()和back()用于访问容器中的元素。
注意：
front()与back()函数返回的是元素的引用，而begin()与end()函数返回的是相应的迭代器。
1.2.5.list的modifiers
| ????? 函数声明 | ???????????????????????????????? 接口说明 |
| ???? push_front | ??????????? ?? 在list首元素前插入值为val的元素 |
| ????? pop_front | ??????????????????????? 删除list中第一个元素 |
| ???? push_back | ?????????????????? 在list尾部插入值为val的元素 |
| ????? pop_back | ????????????????????? 删除list中最后一个元素 |
| ???????? insert | ?????????? 在list position 位置中插入值为val的元素 |
| ???????? erase | ?????????????????? 删除list position位置的元素 |
| ???????? swap | ??????????????????????? 交换两个list中的元素 |
| ???????? clear | ??????????????????????? 清空list中的有效元素 |
详解：
案例一：
//list的插入和删除
//push_back/pop_back/push_front/pop_front
void list_test01()
{
int array[] = { 1, 2, 3 };
list<int> L(array, array + sizeof(array) / sizeof(array[0]));
//在list的尾部插入4，头部插入0
L.push_back(4);
L.push_front(0);
PrintList(L);
//删除list尾部节点和头部节点
L.pop_back();
L.pop_front();
PrintList(L);
}
//insert/erase
void list_test02()
{
int array1[] = { 1, 2, 3 };
list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0]));
//获取链表中第二个节点
//注意：list并没有提供find，若要使用find需要加上algorithm头文件
auto pos = ++L.begin();
cout << *pos << endl;
//在pos前插入值为4的元素
L.insert(pos, 4);
PrintList(L);
//在pos前插入5个值为5的元素
L.insert(pos, 5, 5);
PrintList(L);
//在pos前插入[v.begin(), v.end)区间中的元素
vector<int> v{ 7, 8, 9 };
L.insert(pos, v.begin(), v.end());
PrintList(L);
//删除pos位置上的元素
L.erase(pos);
PrintList(L);
//删除list中[begin, end)区间中的元素，即删除list中的所有元素
L.erase(L.begin(), L.end());
PrintList(L);
}
int main()
{
list_test01();
return 0;
}注意：
pop_front和pop_back在使用时，一定要确保链表不能为空，否则程序会崩溃报错。
案例二：
//swap/clear
void list_test()
{
//用数组来构造list
int array[] = { 1, 2, 3 };
list<int> l1(array, array + sizeof(array) / sizeof(array[0]));
PrintList(l1);
//交换l1和l2中的元素
list<int> l2;
l1.swap(l2);
PrintList(l1);
PrintList(l2);
//将l2中的元素清空
l2.clear();
cout << l2.size() << endl;
}
int main()
{
list_test();
return 0;
}注意：
1.对于swap，在C++98中建议使用容器中自带的，而不建议使用算法中的。最后的结果虽然都相同，但是效率确大不一样。
算法中的swap在使用过程中，会涉及到三次深拷贝问题，而深拷贝的代价是很大的。如果使用容器中自带的swap，在进行lt1和lt2交换时，只需要对它们的头指针进行交换即可。当string,vector和list对象调用swap时，只需把lt1和lt2对应的_start,_finish和_endofstorage进行交换即可。相较于算法中的swap，容器中自带的swap可以认为没有任何代价。
2.clear在清空链表时，并不会把头节点也一并清除掉。
1.2.6.list的operations
sort函数使容器中的元素按从小到大的顺序排列，一般默认排升序。注意：这里的sort()函数并非是算法库中的，而是list容器自带的。
sort函数的底层原理是快排，而快排要求容器迭代器必须是随机迭代器，所以：sort(lt.begin(), lt.end())是不可行的。因为list底层是链表，不支持随机访问，但是可以使用list自带sort函数进行排序。
案例：
void list_test()
{
list<int> lt;
lt.push_back(7);
lt.push_back(0);
lt.push_back(9);
lt.push_back(8);
//注意：less<int>()默认排升序，greater<int>()默认排降序，一般默认为升序
//template <class Compare>
//void sort ( Compare comp );
//它是一个类模板，也是一个仿函数，包含在头文件<functional>中，sort所在头文件为<algorithm>
//可以通过仿函数将sort()改为默认排降序
//greater<int> g;
//lt.sort(g);
lt.sort(greater<int>());//同上,可以直接写成匿名对象
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
}
int main()
{
list_test();
return 0;
}
函数merge()可以将两个有序列表容器合并，函数的功能是把一个list对象作为参数插入到目标list容器中。两个容器合并后，容器中的元素按照从小到大排列，而且合并之后，x容器会变为一个空的容器。
案例：
void list_test()
{
list<int> lt1;
lt1.push_back(2);
lt1.push_back(1);
lt1.push_back(3);
//排序
lt1.sort();
list<int> lt2;
lt2.push_back(4);
lt2.push_back(6);
lt2.push_back(5);
//排序
lt2.sort();
//合并
lt1.merge(lt2);
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
for (auto e : lt2)
{
cout << e << " ";
}
cout << endl;
}
int main()
{
list_test();
return 0;
}
注意：
两个列表容器必须有序，才能进行合并，否则程序会报错。
函数splice()用于连接两个list对象，有三种调用形式：
- 第一种形式是将容器x插入到迭代器position指示的位置前；
- 第二种形式是将x中的元素i（i迭代器指示的元素）插入到迭代器position指示的位置前；
- 第三种形式是将x容器中[first,last)区间的元素插入到迭代器position指示的位置前面。
与merge()函数一样，一旦合并完成，则x中的元素就被“移走”，即x中不再有这些元素，如第一种形式splice()合并，合并之后，x容器就变成一个空的容器。
案例：
void list_test()
{
list<int> lt1;
lt1.push_back(2);
lt1.push_back(1);
lt1.push_back(3);
list<int> lt2;
lt2.push_back(4);
lt2.push_back(6);
lt2.push_back(5);
lt1.splice(lt1.begin(), lt2);//将容器lt2拼接到容器lt1的开头
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
for (auto e : lt2)
{
cout << e << " ";
}
cout << endl;
cout << "------------------------" << endl;
list<int> lt3;
lt3.push_back(7);
lt3.push_back(0);
lt3.push_back(9);
lt3.push_back(8);
list<int> lt4;
lt4.push_back(3);
lt4.push_back(6);
lt3.splice(lt3.begin(), lt4, lt4.begin());//将容器lt4的第一个数据拼接到容器lt3的开头
for (auto e : lt3)
{
cout << e << " ";
}
cout << endl;
for (auto e : lt4)
{
cout << e << " ";
}
cout << endl;
cout << "------------------------" << endl;
list<int> lt5;
lt5.push_back(2);
lt5.push_back(0);
lt5.push_back(1);
lt5.push_back(7);
list<int> lt6(3, 6);
lt5.splice(lt5.begin(), lt6, lt6.begin(), lt6.end());//将容器lt6的指定迭代器区间内的数据拼接到容器lt5的开头
for (auto e : lt5)
{
cout << e << " ";
}
cout << endl;
for (auto e : lt6)
{
cout << e << " ";
}
cout << endl;
}
int main()
{
list_test();
return 0;
}
其他：
void list_test()
{
//remove用于删除容器中特定值的元素, 找到了就删(所有的都删除)，没找到就不删除
//remove_if用于删除容器当中满足条件的元素,
list<int> lt1;
lt1.push_back(2);
lt1.push_back(1);
lt1.push_back(3);
lt1.push_back(1);
lt1.remove(1);
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
list<int> lt2;
lt2.push_back(7);
lt2.push_back(0);
lt2.push_back(9);
lt2.push_back(8);
//unique的功能是去重，去重的前提是要排好序，如果不排好序它只去重相邻的数据
lt2.unique();
for (auto e : lt2)
{
cout << e << " ";
}
cout << endl;
//remove用于删除列表中所有值为value的元素，有就全删，没有就不删
lt2.remove(3);
for (auto e : lt2)
{
cout << e << " ";
}
cout << endl;
//reverse的功能是逆置，带头双向循环链表的逆置比单链表简单的多
lt2.reverse();
for (auto e : lt2)
{
cout << e << " ";
}
cout << endl;
}
int main()
{
list_test();
return 0;
}1.3.list的迭代器失效
前面说过，此处可以将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
void test_list01()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> lt(array, array + sizeof(array) / sizeof(array[0]));
list<int>::iterator pos = find(lt.begin(), lt.end(), 5);
if (pos != lt.end())
{
//不会失效
lt.insert(pos, 45);
}
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
}
void test_list02()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> lt(array, array + sizeof(array) / sizeof(array[0]));
list<int>::iterator pos = find(lt.begin(), lt.end(), 5);
if (pos != lt.end())
{
//erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值
//会失效,可以重新指定迭代器pos
//lt.erase(pos);//err
//pos = lt.erase(pos);//ok
pos = lt.erase(pos++);//ok
}
cout << *pos << endl;
cout << endl;
}
int main()
{
test_list01();
test_list02();
return 0;
}二.list的模拟实现
在模拟实现list类之前，我们先来查看一下list的源码：
template <class T>
struct __list_node
{
typedef void* void_pointer;
void_pointer next;
void_pointer prev;
T data;
};
class list
{
protected:
typedef __list_node<T> list_node;
typedef list_node* link_type;
protected:
link_type node;
protected:
link_type get_node()
{
return list_node_allocator::allocate();
}
protected:
void empty_initialize()
{
//体现了带头双向循环链表的特性
node = get_node();
node->next = node;
node->prev = node;
}
public:
list()
{
empty_initialize();
}
}list类的模拟实现大致可分为三个部分：list的结点类实现，list的迭代器类实现以及list类实现。
2.1.list的结点类
list是一个带头双向循环链表，为此我们首先要模拟实现一个结点类，每一个结点由三部分组成：数据域_data，前驱指针_pre和后继指针_next。同时，结点类中还实现了一个构造函数，构造函数直接根据所给数值构造出一个结点，数据域存储的就是所给数据，而前驱指针和后继指针均初始化为nullptr即可。具体实现如下：
//List的结点类
//list是一个带头双向循环链表
//struct的默认成员访问限定符是公有的
template<class T>
struct list_node
{
list_node<T>* _next;
list_node<T>* _pre;
T _data;
//构造
//由于不知道要存储的数据类型，这里需使用匿名构造为缺省值赋值
list_node(const T& x = T())
:_next(nullptr)
, _pre(nullptr)
, _data(x)
{
}
};2.2.list的迭代器类
2.2.1.迭代器分析
迭代器有两种实现方式，具体应根据容器底层数据结构实现：
?? ?? 1. 原生态指针，比如：vector和string
?? ????? 因为string和vector对象都将其数据存储在了一块连续的内存空间，我们只需通过指针进行自增、自减以及解引用等操作就可以对相应位置的数据进行修改。
?? ?? 2. 将原生态指针进行封装，因迭代器使用形式与指针完全相同，因此在自定义的类中必须实现以下方法：
?? ??? ? 1. 指针可以解引用，迭代器的类中必须重载operator*()；
?? ??? ? 2. 指针可以通过->访问其所指空间成员，迭代器类中必须重载oprator->()；
?? ??? ? 3. 指针可以++向后移动，迭代器类中必须重载operator++()与operator++(int)；
?? ??? ??? ?至于operator--()/operator--(int)是否需要重载，根据具体的结构来抉择，双向链表可以向前移动，所以需要重载，如果是forward_list就不需要重载--；
?? ??? ? 4. 迭代器需要进行是否相等的比较，因此还需要重载operator==()与operator!=()。? ?
list不再能够像vector一样以普通指针作为迭代器，因为其结点不保证在存储空间中连续存在。list迭代器必须有能力指向list的结点，并有能力进行正确的递增，递减，取值，成员存取等操作所谓"list迭代器正确的递增，递减，取值，成员取用"操作是指，递增时指向下一个结点，递减时指向上一个结点，取值时取的是结点的数据值，成员取用时取用的是节点的成员。
对list而言，其各个结点在内存中的位置是随机而非连续的，我们不能仅通过结点指针的自增、自减以及解引用等操作对相应位置的数据进行修改。因此，list的迭代器实质上是对结点指针进行了封装，并对各种运算符进行了重载，进而让结点指针的各种行为看起来和普通指针相同。
2.2.2.迭代器模板参数说明
在模拟实现迭代器类之前，我们先来查看一下迭代器类的部分源码：
从源码中可以发现，它只实现了一个_list_iterator类，模板参数列表中的Ref和Ptr分别代表引用类型和指针类型。当我们调用普通迭代器时，编译器就会使用类模板实例化出一个普通迭代器对象，当我们调用const迭代器时，编译器就会使用类模板实例化出一个const迭代器对象。普通迭代器和const迭代器只是在*和->运算符重载的返回值方面有所不同，使用Ref和Ptr对其进行统一，可以有效减少程序的代码量，否则我们既要实现一个非const迭代器类，又要实现一个const迭代器类，最终会导致代码冗余。
2.2.3.成员函数模拟实现
构造
迭代器类实际上就是对结点指针进行封装，为此要在迭代器类内部定义一个结点指针，用于访问list的各个结点。
_list_iterator(node* n)
:_node(n)
{
}operator*
解引用操作符*，主要用于获取list的结点中所存储的数据域_date。因此，我们可以直接返回当前结点指针所指结点的数据域。注意：这里使用引用作为函数的返回值，可以避免在内存中产生一个临时变量，也可以直接对数据域进行修改。
Ref operator*()
{
return _node->_data; //对迭代器取值，取的是结点的数值域
}operator->
->操作符，主要用于获取当前迭代器的结点指针所指结点的数据域的地址。注意：这里返回的是指针类型。
Ptr operator->()
{
return &_node->_data; //返回迭代器的结点指针所指结点的数据域的地址
}operator++
分为前置++和后置++，对迭代器进行++操作，就是让迭代器的结点指针向后移动一位指向下一个结点，然后返回该结点的迭代器。
//++
//对迭代器++，就是前进一个结点
//前置
self& operator++()
{
_node = _node->_next;
return *this;
}
//++
//后置
self& operator++(int)
{
//先保存++之前的值
self tmp(*this);
_node = _node->_next;
return tmp;
}operator--
分为前置--和后置--，对迭代器进行--操作，就是让迭代器的结点指针向前移动一位指向上一个结点，然后返回该结点的迭代器。
//--
//对迭代器--，就是后退一个结点
//前置
self& operator--()
{
_node = _node->_pre;
return *this;
}
//--
//后置
self& operator--(int)
{
self tmp(*this);
_node = _node->_pre;
return tmp;
}operator!=
!=运算符，主要用于判断两个迭代器是否不同，也就是判断这两个迭代器中所对应的结点指针否不同。
//!=
//比较两个迭代器所对应的结点指针是否不同
bool operator!=(const self& s) const
{
return _node != s._node;
}operator==
==运算符，主要用于判断两个迭代器是否相同，也就是判断这两个迭代器中所对应的结点指针否相同。
//==
//比较两个迭代器对应的结点指针是否相同
bool operator==(const self& s) const
{
return _node == s._node;
}2.3.list类
list不仅是一个双向链表，而且还是一个双向循环链表。所以它只需要一个指针，便可以遍历整个链表。
2.3.1.默认成员函数
构造
法一：默认构造，即构造空的list
首先要创建一个空链表empty_init，也就是先创建一个头结点，并让其前驱指针和后继指针均指向该头结点。
//法一：默认构造，即构造空的list
//创建一个空链表
void empty_init()
{
_head = new node;
_head->_next = _head;
_head->_pre = _head;
}
list()
{
empty_init();
}法二：构造的list中包含n个值为val的元素
//法二：构造的list中包含n个值为val的元素
list(size_t n, const T& value = T())//注意:这里的val要给缺省值,不能给0之类的,因为T的类型未知
{
empty_init();
for (int i = 0; i < n; ++i)
{
push_back(value);
}
}法三：用[first, last)区间中的元素构造list
//法三：用[first, last)区间中的元素构造list
template <class Iterator>//可以是任意类型的迭代器构造
list(Iterator first, Iterator last)
{
empty_init();
while (first != last)
{
push_back(*first);
++first;
}
}注意：
与vector用法相同，法二和法三在调用过程中可能会存在冲突。因为编译器的原则是：若存在更匹配的则调用更匹配的，若存在现成的则不会对模板进行推演。如下所示：
为此，我们可以为法二增设一个int类型的版本，用以和size_t类型的版本加以区分，或者直接实现一个int类型的版本：
//法二：构造的list中包含n个值为val的元素
list(int n, const T& value = T())//注意:这里的val要给缺省值,不能给0之类的,因为T的类型未知
{
empty_init();
for (int i = 0; i < n; ++i)
{
push_back(value);
}
}拷贝构造
//拷贝构造
//传统写法
//lt2(lt1)
//list(const list<T>& lt)
//{
// //初始化
// empty_init();
// //遍历
// for (auto e : lt)
// {
// push_back(e);
// }
//}
void swap(list<T>& tmp)
{
std::swap(_head, tmp._head);
}
//现代写法
list(const list<T>& lt)
{
//必须初始化一个头结点，否则_head是一个随机值
empty_init();
list<T> tmp(lt.begin(), lt.end());
swap(tmp);
}赋值运算符重载
//赋值运算符重载
//list<T>& lt:不建议用引用
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}析构
//析构
//注意：要释放头结点
~list()
{
clear();
delete _head;
_head = nullptr;
}2.3.2.元素操作函数
insert
在插入新结点之前，首先要判断所插入位置是否合法，然后将当前迭代器pos中的结点指针赋值给cur，接着通过cur指针找到前一个位置的结点指针pre，最后构造一个新结点new_node并将三个结点pre，new_node以及cur三者相链接。
//插入
//用于在迭代器pos位置之前插入一个新结点
void insert(iterator pos, const T& x)
{
assert(pos._node);
//将迭代器pos中的结点指针赋值给cur
//pos是一个迭代器对象, 访问其成员变量或成员函数要用.访问
node* cur = pos._node;
//查找当前结点的前一个结点pre
node* pre = cur->_pre;
//创建一个新结点new_node
node* new_node = new node(x);
//链接三个结点：pre new_node cur
pre->_next = new_node;
new_node->_pre = pre;
new_node->_next = cur;
cur->_pre = new_node;
}erase
在删除之前，首先要判断所要删除的结点是否为头结点，然后查找当前结点的前一个结点pre和后一个结点next，接着将前结点pre和后结点next相链接并删除当前结点pos._node，最后返回一个匿名迭代器对象。
//删除
//哨兵位的头结点不能erase
iterator erase(iterator pos)
{
//哨兵位的头结点不能erase
assert(pos != end());
//查找前一个结点
node* pre = pos._node->_pre;
//查找后一个结点
node* next = pos._node->_next;
//将前后结点相连
pre->_next = next;
next->_pre = pre;
//删除当前结点
delete pos._node;
//构造一个匿名对象返回：用next节点，构造一个迭代器并返回
return iterator(next);//采用匿名对象，匿名对象的生命周期只有这一行
}push_back
首先查找尾结点tail，然后创建一个新结点new_node，最后将新结点new_node插入到尾结点tail的后面。或者调用函数insert完成插入。
//尾插
void push_back(const T& x)
{
查找尾结点
//node* tail = _head->_pre;
开辟一个新结点
//node* new_node = new node(x);
尾插
//tail->_next = new_node;
//new_node->_pre = tail;
//new_node->_next = _head;
//_head->_pre = new_node;
insert(end(), x);
}push_front
调用函数insert，在迭代器begin()位置插入一个值为x的结点。
//头插
void push_front(const T& x)
{
insert(begin(), x);
}pop_back
调用函数erase，删除迭代器end()前一个位置的结点。
//尾删
void pop_back()
{
erase(--end());
}pop_front
调用函数erase，删除迭代器begin()位置的结点。
//头删
void pop_front()
{
erase(begin());
}clear
函数clear用于清空容器，通过遍历的方式将结点逐个删除，只保留哨兵位的头结点即可。
//清空
//注意：不清理头结点
void clear()
{
iterator it = begin();
while (it != end())
{
//法一：
//erase(it);//迭代器失效，要用返回值接收
it = erase(it);
//法二：
//erase(it++);
}
}2.3.3.迭代器
正向迭代器
list的迭代器实际上就是对结点指针进行封装，使得结点指针的各种行为看起来和普通指针一样，可以自增++和自减--。正向迭代器又可分为非const迭代器和const迭代器。
//正向迭代器
typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T, const T&, const T*> const_iterator;
//typedef _list_const_iterator<T> const_iterator;
//非const
iterator begin()
{
//法一：
//iterator it(_head->_next);
//return it;
//法二：
//匿名对象返回
return iterator(_head->_next);
}
//const
const_iterator begin() const
{
//iterator it(_head->_next);
//return it;
//匿名对象返回
return const_iterator(_head->_next);
}
//非const
iterator end()
{
//匿名对象返回
return iterator(_head);
}
//const
const_iterator end() const
{
//匿名对象返回
return const_iterator(_head);
}反向迭代器
法一：模拟实现一个反向迭代器类
首先，同正向迭代器类_list_iterator相同，模拟实现一个反向迭代器类_list_reverse_iterator：
template<class T, class Ref, class Pef>//class Ref，class Pef：用于控制返回值不同
struct _list_reverse_iterator
{
//反向迭代器
typedef list_node<T> node;
typedef _list_reverse_iterator<T, Ref, Pef> self;
node* _node;
//构造
_list_reverse_iterator(node* n)
:_node(n)
{
}
//*
//解引用：分为const版本与非const版本
Ref operator*()
{
return _node->_data;
}
//->
//->：分为const版本与非const版本
Pef operator->()
{
return &_node->_data;
}
//++
//前置
self& operator++()
{
_node = _node->_pre;
return *this;
}
//++
//后置
self& operator++(int)
{
//先保存++之前的值
self tmp(*this);
_node = _node->_pre;
return tmp;
}
//--
//前置
self& operator--()
{
_node = _node->_next;
return *this;
}
//--
//后置
self& operator--(int)
{
self tmp(*this);
_node = _node->_next;
return tmp;
}
//!=
//比较两个结点的指针是否相等
bool operator!=(const self& s)
{
return _node != s._node;
}
//==
//比较两个结点的指针是否相等
bool operator==(const self& s)
{
return _node == s._node;
}
};然后，在list类中调用反向迭代器类_list_reverse_iterator并模拟实现rbegin()和rend()：
//反向迭代器
typedef _list_reverse_iterator<T, T&, T*> reverse_iterator;
typedef _list_reverse_iterator<T, const T&, const T*> const_reverse_iterator;
//非const
reverse_iterator rbegin()
{
//匿名对象返回
return reverse_iterator(_head->_pre);
}
//非const
reverse_iterator rend()
{
return reverse_iterator(_head);
}
//const
const_reverse_iterator rbegin() const
{
return const_reverse_iterator(end());
}
//const
const_reverse_iterator rend() const
{
return const_reverse_iterator(begin());
}法二：用正向迭代器去构造反向迭代器
通过前面例子知道，反向迭代器的++就是正向迭代器的--，反向迭代器的--就是正向迭代器的++，因此反向迭代器的实现可以借助正向迭代器，即：反向迭代器内部可以包含一个正向迭代器，对正向迭代器的接口进行包装即可。
注意：
为了使正向迭代器和反向迭代器的开始和结束位置保持对称，在设计上源码中的解引用*取的是前一个迭代器中的内容。如下所示：
首先，用正向迭代器去构造一个反向迭代器，这里为了便于将非const反向迭代器与const反向迭代器相统一，引用了两个模板类型参数Ref和Ptr，同时也是为了区分operator* 和operator->。我们将反向迭代器类封装在另外一个头文件iterator.h中，方便后期重复使用：
//用正向迭代器去构造反向迭代器
namespace bite
{
//const迭代器和普通迭代器只是在*和->运算符重载的返回值不同，使用Ref和Ptr对其进行统一，减少代码量
//Ref分为T&和const T&，Ptr分为T*和const T*
template<class Iterator, class Ref, class Ptr>
struct ReverseIterator
{
typedef ReverseIterator<Iterator, Ref, Ptr> Self;
Iterator _cur;
//构造
//使用正向迭代器进行构造
ReverseIterator(Iterator it)
:_cur(it)
{
}
//前置++
Self& operator++()
{
--_cur;
return *this;
}
//后置++
//tmp出了作用域就自动销毁传，要使用值返回，不能使用引用返回
Self operator++(int)
{
Self tmp(*this);
--_cur;//复用正向迭代器的--
return tmp;
}
//前置--
Self& operator--()
{
++_cur;
return *this;
}
//后置--
//tmp出了作用域就自动销毁传，要使用值返回，不能使用引用返回
Self operator--(int)
{
Self tmp(*this);
++_cur;//复用正向迭代器的++
return tmp;
}
//!=
bool operator!=(const Self& s) const
{
return _cur != s._cur;
}
bool operator== (const Self& s) const
{
return _cur == s._cur;
}
//*
//如果是非const反向迭代器：Ref就是T&；如果是const反向迭代器：Ref就是const T&
Ref operator*()
{
//获取当前迭代器前一个位置的迭代器tmp
Iterator tmp = _cur;
--tmp;
return *tmp;
}
//->
//如果是非const反向迭代器：Ptr就是T*；如果是const反向迭代器：Ptr就是const T*
Ptr operator->()
{
//获取当前迭代器前一个位置的迭代器
Iterator tmp = _cur;
--tmp;
return &tmp;
//return &operator*();//返回的是operator*()函数的返回数据的地址
}
};
}
然后，在list类中调用反向迭代器ReverseIterator类并模拟实现rbegin()和rend()：
//用正向迭代器实现反向迭代器
typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
typedef ReverseIterator<iterator, const T&, const T*> const_reverse_iterator;
//非const
reverse_iterator rbegin()
{
return reverse_iterator(end());
}
//非const
reverse_iterator rend()
{
return reverse_iterator(begin());
}
//const
const_reverse_iterator rbegin() const
{
return const_reverse_iterator(end());
}
//const
const_reverse_iterator rend() const
{
return const_reverse_iterator(begin());
}三.list与vector的对比
vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下：
| ?????????????????????? vector | ???????????????????????????? list | |
| ???? 底层结构 | ????????? 动态顺序表，一段连续空间 | ???????????? 带头结点的双向循环链表 |
| ???? 随机访问 | 支持随机访问，访问某个元素效率O(1) | 不支持随机访问，访问某个元素效率O(N) |
| ?? 插入和删除 | 任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低 | 任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1) |
| ?? 空间利用率 | 底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高 | 底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低 |
| ????? 迭代器 | ?????????????????? 原生态指针 | ?????? 对原生态指针(节点指针)进行封装 |
| ?? 迭代器失效 | 在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效 | 插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响 |
| ???? 使用场景 | 需要高效存储，支持随机访问，不关心插入删除效率 | 大量插入和删除操作，不关心随机访问 |
四.list类完整实现
list.h
#pragma once
#include<assert.h>
#include"iterator.h"
namespace bite
{
//List的结点类
//list是一个带头双向循环链表
//struct的默认成员访问限定符是公有的
template<class T>
struct list_node
{
list_node<T>* _next;
list_node<T>* _pre;
T _data;
//构造
//由于不知道要存储的数据类型，这里需使用匿名构造为缺省值赋值
list_node(const T& x = T())
:_next(nullptr)
, _pre(nullptr)
, _data(x)
{
}
};
/*
List的迭代器
迭代器有两种实现方式，具体应根据容器底层数据结构实现：
1. 原生态指针，比如：vector和string
因为string和vector对象都将其数据存储在了一块连续的内存空间，我们只需通过指针进行自增、自减以及解引用等操作就可以对相应位置的数据进行修改
2. 将原生态指针进行封装，因迭代器使用形式与指针完全相同，因此在自定义的类中必须实现以下方法：
1. 指针可以解引用，迭代器的类中必须重载operator*()
2. 指针可以通过->访问其所指空间成员，迭代器类中必须重载oprator->()
3. 指针可以++向后移动，迭代器类中必须重载operator++()与operator++(int)
至于operator--()/operator--(int)是否需要重载，根据具体的结构来抉择，双向链表可以向前移动，所以需要重载，如果是forward_list就不需要重载--
4. 迭代器需要进行是否相等的比较，因此还需要重载operator==()与operator!=()
对list来说，其各个结点在内存中的位置是随机而非连续的，我们不能仅通过结点指针的自增、自减以及解引用等操作对相应位置的数据进行修改
list的迭代器实质上是对结点指针进行了封装，使其对各种运算符进行重载，进而让结点指针的各种行为看起来和普通指针相同
*/
//List的迭代器
//const迭代器和普通迭代器只是在*和->运算符重载的返回值不同，使用Ref和Ptr对其进行统一，减少代码量
//Ref分为T&和const T&，Ptr分为T*和const T*
//List的非const迭代器
template<class T, class Ref, class Ptr> //Ref和Ptr：用于控制返回值不同
struct _list_iterator
{
//正向迭代器
typedef list_node<T> node; //结点重命名
typedef _list_iterator<T, Ref, Ptr> self; //迭代器重命名
node* _node; //迭代器内部当然要有一个普通指针，指向list的结点
//构造
_list_iterator(node* n)
:_node(n)
{
}
//*
//解引用：分为const版本与非const版本
Ref operator*()
{
return _node->_data; //对迭代器取值，取的是结点的数据域
}
//->
//->：分为const版本与非const版本
Ptr operator->()
{
return &_node->_data; //返回迭代器的结点指针所指结点的数据域的地址
}
//++
//对迭代器++，就是前进一个结点
//前置
self& operator++()
{
_node = _node->_next;
return *this;
}
//++
//后置
//tmp出了作用域就自动销毁传，要使用值返回，不能使用引用返回
self operator++(int)
{
//先保存++之前的值
self tmp(*this);
_node = _node->_next;
return tmp;
}
//--
//对迭代器--，就是后退一个结点
//前置
self& operator--()
{
_node = _node->_pre;
return *this;
}
//--
//后置
//tmp出了作用域就自动销毁传，要使用值返回，不能使用引用返回
self operator--(int)
{
self tmp(*this);
_node = _node->_pre;
return tmp;
}
//!=
//比较两个迭代器所对应的结点指针是否不同
bool operator!=(const self& s) const
{
return _node != s._node;
}
//==
//比较两个迭代器所对应的结点指针是否相同
bool operator==(const self& s) const
{
return _node == s._node;
}
};
//List的const迭代器
//template<class T>
//struct _list_const_iterator
//{
// typedef list_node<T> node;
// typedef _list_const_iterator<T> self;
// node* _node;
// //构造
// _list_const_iterator(node* n)
// :_node(n)
// {
// }
// //*
// //解引用
// //防止迭代器所指向的内容被修改
// const T& operator*()
// {
// return _node->_data;
// }
// //++
// //前置
// self& operator++()
// {
// _node = _node->_next;
// return *this;
// }
// //++
// //后置
// self& operator++(int)
// {
// //先保存++之前的值
// self tmp(*this);
// _node = _node->_next;
// return tmp;
// }
// //--
// //前置
// self& operator--()
// {
// _node = _node->_pre;
// return *this;
// }
// //--
// //后置
// self& operator--(int)
// {
// self tmp(*this);
// _node = _node->_pre;
// return tmp;
// }
// //!=
// //比较两个结点的指针是否相等
// bool operator!=(const self& s)
// {
// return _node != s._node;
// }
// //==
// //比较两个结点的指针是否相等
// bool operator==(const self& s)
// {
// return _node == s._node;
// }
//};
//List的反向迭代器
//template<class T, class Ref, class Pef>//class Ref，class Pef：用于控制返回值不同
//struct _list_reverse_iterator
//{
// //反向迭代器
// typedef list_node<T> node;
// typedef _list_reverse_iterator<T, Ref, Pef> self;
// node* _node;
// //构造
// _list_reverse_iterator(node* n)
// :_node(n)
// {
// }
// //*
// //解引用：分为const版本与非const版本
// Ref operator*()
// {
// return _node->_data;
// }
// //->
// //->：分为const版本与非const版本
// Pef operator->()
// {
// return &_node->_data;
// }
// //++
// //前置
// self& operator++()
// {
// _node = _node->_pre;
// return *this;
// }
// //++
// //后置
// self& operator++(int)
// {
// //先保存++之前的值
// self tmp(*this);
// _node = _node->_pre;
// return tmp;
// }
// //--
// //前置
// self& operator--()
// {
// _node = _node->_next;
// return *this;
// }
// //--
// //后置
// self& operator--(int)
// {
// self tmp(*this);
// _node = _node->_next;
// return tmp;
// }
// //!=
// //比较两个结点的指针是否相等
// bool operator!=(const self& s)
// {
// return _node != s._node;
// }
// //==
// //比较两个结点的指针是否相等
// bool operator==(const self& s)
// {
// return _node == s._node;
// }
//};
//List类
template<class T>
class list
{
typedef list_node<T> node;
public:
//正向迭代器
typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T, const T&, const T*> const_iterator;
//typedef _list_const_iterator<T> const_iterator;
//非const
iterator begin()
{
//法一：
//iterator it(_head->_next);
//return it;
//法二：
//匿名对象返回
return iterator(_head->_next);
}
//const
const_iterator begin() const
{
//iterator it(_head->_next);
//return it;
//匿名对象返回
return const_iterator(_head->_next);
}
//非const
iterator end()
{
//匿名对象返回
return iterator(_head);
}
//const
const_iterator end() const
{
//匿名对象返回
return const_iterator(_head);
}
反向迭代器
//typedef _list_reverse_iterator<T, T&, T*> reverse_iterator;
//typedef _list_reverse_iterator<T, const T&, const T*> const_reverse_iterator;
非const
//reverse_iterator rbegin()
//{
// //匿名对象返回
// return reverse_iterator(_head->_pre);
//}
非const
//reverse_iterator rend()
//{
// return reverse_iterator(_head);
//}
const
//const_reverse_iterator rbegin() const
//{
// return const_reverse_iterator(end());
//}
//
const
//const_reverse_iterator rend() const
//{
// return const_reverse_iterator(begin());
//}
//用正向迭代器实现反向迭代器
typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
typedef ReverseIterator<iterator, const T&, const T*> const_reverse_iterator;
//非const
reverse_iterator rbegin()
{
return reverse_iterator(end());
}
//非const
reverse_iterator rend()
{
return reverse_iterator(begin());
}
//const
const_reverse_iterator rbegin() const
{
return const_reverse_iterator(end());
}
//const
const_reverse_iterator rend() const
{
return const_reverse_iterator(begin());
}
//法一：默认构造，即构造空的list
//创建一个空链表
void empty_init()
{
_head = new node;
_head->_next = _head;
_head->_pre = _head;
}
list()
{
empty_init();
}
//法二：构造的list中包含n个值为val的元素
list(int n, const T& value = T())//注意:这里的val要给缺省值,不能给0之类的,因为T的类型未知
{
empty_init();
for (int i = 0; i < n; ++i)
{
push_back(value);
}
}
//法三：用[first, last)区间中的元素构造list
template <class Iterator>//可以是任意类型的迭代器构造
list(Iterator first, Iterator last)
{
empty_init();
while (first != last)
{
push_back(*first);
++first;
}
}
//拷贝构造
//传统写法
//lt2(lt1)
//list(const list<T>& lt)
//{
// //初始化
// empty_init();
// //遍历
// for (auto e : lt)
// {
// push_back(e);
// }
//}
void swap(list<T>& tmp)
{
std::swap(_head, tmp._head);
}
//现代写法
list(const list<T>& lt)
{
//必须初始化一个头结点，否则_head是一个随机值
empty_init();
list<T> tmp(lt.begin(), lt.end());
swap(tmp);
}
//赋值运算符重载
//传统写法
//lt2 = lt;//lt2.operator=(lt)
//list<T>& operator=(const list<T>& lt)
//{
// //防止自己给自己赋值
// if (this != <)
// {
// clear();
// for (const auto& e : lt)
// {
// push_back(e);
// }
// }
// return *this;
//}
//现代写法
//list<T>& lt:不建议用引用
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
//析构
//注意：要释放头结点
~list()
{
clear();
delete _head;
_head = nullptr;
}
//清空
//注意：不清理头结点
void clear()
{
iterator it = begin();
while (it != end())
{
//法一：
//erase(it);//迭代器失效，要用返回值接收
it = erase(it);
//法二：
//erase(it++);
}
}
//尾插
void push_back(const T& x)
{
查找尾结点
//node* tail = _head->_pre;
开辟一个新结点
//node* new_node = new node(x);
尾插
//tail->_next = new_node;
//new_node->_pre = tail;
//new_node->_next = _head;
//_head->_pre = new_node;
insert(end(), x);
}
//头插
void push_front(const T& x)
{
insert(begin(), x);
}
//插入
//用于在迭代器pos位置之前插入一个新结点
void insert(iterator pos, const T& x)
{
assert(pos._node);
//将迭代器pos中的结点指针赋值给cur
//pos是一个迭代器对象, 访问其成员变量或成员函数要用.访问
node* cur = pos._node;
//查找当前结点的前一个结点pre
node* pre = cur->_pre;
//创建一个新结点new_node
node* new_node = new node(x);
//链接三个结点：pre new_node cur
pre->_next = new_node;
new_node->_pre = pre;
new_node->_next = cur;
cur->_pre = new_node;
}
//尾删
void pop_back()
{
erase(--end());
}
//头删
void pop_front()
{
erase(begin());
}
//删除
//哨兵位的头结点不能erase
iterator erase(iterator pos)
{
//哨兵位的头结点不能erase
assert(pos != end());
//查找前一个结点
node* pre = pos._node->_pre;
//查找后一个结点
node* next = pos._node->_next;
//将前后结点相连
pre->_next = next;
next->_pre = pre;
//删除当前结点
delete pos._node;
//构造一个匿名对象返回：用next节点，构造一个迭代器并返回
return iterator(next);//采用匿名对象，匿名对象的生命周期只有这一行
}
size_t size()
{
size_t n = 0;
iterator it = begin();
while (it != end())
{
++it;
++n;
}
return n;
}
bool empty()
{
return begin() == end();
}
private:
node* _head; //定义一个指针，用于遍历整个双向循环链表
};
//const类型的list
void print_list(const list<int>& lt)
{
list<int>::const_iterator it = lt.begin();//拷贝构造
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
void test_list1()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
//int*
list<int>::iterator it = lt.begin();//拷贝构造
while (it != lt.end())
{
(*it) *= 2;
cout << *it << " ";
++it;
}
cout << endl;
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
print_list(lt);
}
struct AA
{
int _a1;
int _a2;
//构造
AA(int a1 = 0, int a2 = 0)
:_a1(a1)
, _a2(a2)
{
}
};
void test_list2()
{
list<AA> lt;
lt.push_back(AA(1, 1));
lt.push_back(AA(2, 2));
lt.push_back(AA(3, 3));
//AA* ptr
list<AA>::iterator it = lt.begin();
while (it != lt.end())
{
//cout << (*it)._a1 << ":" << (*it)._a2 << endl;
//本来应该是:it->->_a1，一个是运算符重载的调用，一个是对指针AA*的解引用，但为了增强可读性，通常省略了一个->
cout << it->_a1 << ":" << it->_a2 << endl;
cout << it.operator->()->_a1 << ":" << it.operator->()->_a2 << endl;//it.operator->() 可以省略为it
++it;
}
cout << endl;
}
void test_list3()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
auto pos = lt.begin();
++pos;
lt.insert(pos, 20);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
//头插尾插
lt.push_back(100);
lt.push_front(1000);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
//头删尾删
lt.pop_back();
lt.pop_front();
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
}
void test_list4()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
lt.clear();
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
lt.push_back(10);
lt.push_back(20);
lt.push_back(30);
lt.push_back(40);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
}
void test_list5()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
list<int> lt2(lt);
for (auto e : lt2)
{
cout << e << " ";
}
cout << endl;
list<int> lt3;
lt3.push_back(10);
lt3.push_back(20);
lt3.push_back(30);
for (auto e : lt3)
{
cout << e << " ";
}
cout << endl;
lt2 = lt3;
for (auto e : lt2)
{
cout << e << " ";
}
cout << endl;
for (auto e : lt3)
{
cout << e << " ";
}
cout << endl;
}
//反向迭代器的++就是正向迭代器的--，反向迭代器的--就是正向迭代器的++，因此反向迭代器的实现可以借助正向迭代器
//即：反向迭代器内部可以包含一个正向迭代器，对正向迭代器的接口进行包装即可。
void test_list6()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
(*it) *= 2;
cout << *it << " ";
++it;
}
cout << endl;
list<int>::reverse_iterator rit = lt.rbegin();
while (rit != lt.rend())
{
cout << *rit << " ";
++rit;
}
cout << endl;
}
}iterator.h
#pragma once
//用正向迭代器去构造反向迭代器
namespace bite
{
//const迭代器和普通迭代器只是在*和->运算符重载的返回值不同，使用Ref和Ptr对其进行统一，减少代码量
//Ref分为T&和const T&，Ptr分为T*和const T*
template<class Iterator, class Ref, class Ptr>
struct ReverseIterator
{
typedef ReverseIterator<Iterator, Ref, Ptr> Self;
Iterator _cur;
//构造
//使用正向迭代器进行构造
ReverseIterator(Iterator it)
:_cur(it)
{
}
//前置++
Self& operator++()
{
--_cur;
return *this;
}
//后置++
//tmp出了作用域就自动销毁传，要使用值返回，不能使用引用返回
Self operator++(int)
{
Self tmp(*this);
--_cur;//复用正向迭代器的--
return tmp;
}
//前置--
Self& operator--()
{
++_cur;
return *this;
}
//后置--
//tmp出了作用域就自动销毁传，要使用值返回，不能使用引用返回
Self operator--(int)
{
Self tmp(*this);
++_cur;//复用正向迭代器的++
return tmp;
}
//!=
bool operator!=(const Self& s) const
{
return _cur != s._cur;
}
bool operator== (const Self& s) const
{
return _cur == s._cur;
}
//*
//如果是非const反向迭代器：Ref就是T&；如果是const反向迭代器：Ref就是const T&
Ref operator*()
{
//获取当前迭代器前一个位置的迭代器tmp
Iterator tmp = _cur;
--tmp;
return *tmp;
}
//->
//如果是非const反向迭代器：Ptr就是T*；如果是const反向迭代器：Ptr就是const T*
Ptr operator->()
{
//获取当前迭代器前一个位置的迭代器
Iterator tmp = _cur;
--tmp;
return &tmp;
//return &operator*();//返回的是operator*()函数的返回数据的地址
}
};
}
test.cpp
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<list>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
#include"List.h"
#include"vector.h"
int main()
{
bite::test_vector8();
return 0;
}
文章来源:https://blog.csdn.net/weixin_36194037/article/details/135267283
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！
最新文章
- Python教程
- 深入理解 MySQL 中的 HAVING 关键字和聚合函数
- Qt之QChar编码（1）
- MyBatis入门基础篇
- 用Python脚本实现FFmpeg批量转换
- Qt的简单游戏实现提供完整代码
- Java实现大病保险管理系统 JAVA+Vue+SpringBoot+MySQL
- 有免费仓库出入库管理软件推荐吗？
- C++ 双指针思路OJ题
- 机器学习---模型评估
- 计算机组成原理 I/O方式
- 龙头老大OpenAI在和谷歌等其他同行“掰头”的时候，有一家“业界清流”公司
- 案例系列：便利店销售预测_基于Dart时间序列深度学习模型
- 深度学习｜3.6 激活函数 3.7 为什么需要非线性激活函数
- Small to Medium Coures_每天一个Linux命令