从C语言到C++_17(list的模拟实现)list不是原生指针的迭代器（中）：https://developer.aliyun.com/article/1521342
4.2 迭代器区间构造和交换
我们直接写现代写法，因为list本来就是提供迭代器区间初始化和交换函数的，
现在我们实现一下，并且拷贝构造的话至少保证有个头结点把，
所以我们把构造函数拎出来复用一下，写成一个empty_init 函数 （源码里也是这样写的），
这几个函数我们很熟了，直接放代码：
void empty_init()// 创建并初始化哨兵位头结点（即构造函数） { _head = new Node; _head->_next = _head; _head->_prev = _head; } template <class InputIterator> list(InputIterator first, InputIterator last) { empty_init(); while (first != last) { push_back(*first); ++first; } } list() { empty_init(); } void swap(list<T>& x)//提一嘴：void swap(list& x)也行（类里面可以省略<T>，类外不行> { std::swap(_head, x._head); // 换哨兵位头结点就行 }
4.3 拷贝构造和赋值重载
在上面的基础上我们直接用现代写法：
list(const list<T>& lt)//lt2(lt1) { empty_init(); list<T> tmp(lt.begin(), lt.end()); // 迭代器区间构造一个(lt1) swap(tmp); // 直接和lt2换哨兵位头结点 } list<T>& operator=(list<T> lt)//lt3 = lt1 这里lt1直接深拷贝给lt，lt是局部对象，出来作用域直接调析构 { swap(lt);// 把深拷贝出来的lt和lt3交换 return *this; // 把lt3返回 }
测试一下：
void Test_copy() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); list<int> lt2(lt); for (auto& e : lt2) { e *= 10; } print_list(lt); print_list(lt2); }
5. list相关选择题
1. 以下程序输出结果为( )
int main() { int ar[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int n = sizeof(ar) / sizeof(int); list<int> mylist(ar, ar + n); list<int>::iterator pos = find(mylist.begin(), mylist.end(), 5); reverse(mylist.begin(), pos); reverse(pos, mylist.end()); list<int>::const_reverse_iterator crit = mylist.crbegin(); while (crit != mylist.crend()) { cout << *crit << " "; ++crit; } cout << endl; }
A.4 3 2 1 0 5 6 7 8 9
B.0 1 2 3 4 9 8 7 6 5
C.5 6 7 8 9 0 1 2 3 4
D.5 6 7 8 9 4 3 2 1 0
2. 下面程序的输出结果正确的是( )
int main() { int array[] = { 1, 2, 3, 4, 0, 5, 6, 7, 8, 9 }; int n = sizeof(array) / sizeof(int); list<int> mylist(array, array + n); auto it = mylist.begin(); while (it != mylist.end()) { if (*it != 0) cout << *it << " "; else it = mylist.erase(it); ++it; } return 0; }
A.1 2 3 4 5 6 7 8 9
B. 1 2 3 4 6 7 8 9
C.程序运行崩溃
D.1 2 3 4 0 5 6 7 8 9
3. 对于list有迭代器it, 当erase(it)后，说法错误的是( )
A.当前迭代器it失效
B.it前面的迭代器仍然有效
C.it后面的迭代器失效
D.it后面的迭代器仍然有效
4. 下面有关vector和list的区别，描述错误的是( )
A.vector拥有一段连续的内存空间，因此支持随机读取，如果需要高效的随机读取，应该使用vector
B.list拥有一段不连续的内存空间，如果需要大量的插入和删除，应该使用listC.vector<int>::iterator支持“+”、“+=”、“<”等操作符
D.list<int>::iterator则不支持“+”、“+=”、“<”等操作符运算，但是支持了[]运算符
5. 下面有关vector和list的区别，描述正确的是( )
A.两者在尾部插入的效率一样高
B.两者在头部插入的效率一样高
C.两者都提供了push_back和push_front方法
D.两者都提供了迭代器，且迭代器都支持随机访问
6. 以下代码实现了从 list 中删除重复项的功能，请选择其中空白行应填入的正确代码（ ）
template<typename T> void removeDuplicates(list<T>& aList) { T curValue; list<T>::iterator cur, p; cur = aList.begin(); while (cur != aList.end()) { curValue = *cur; //空白行 1 while (p != aList.end()) { if (*p == curValue) { //空白行 2 } else { p++; } } } }
A. p=cur+1;aList.erase(p++);
B.p=++cur; p == cur ? cur = p = aList.erase(p) : p = aList.erase(p);
C.p=cur+1;aList.erase(p);
D.p=++cur;aList.erase(p);
答案：
1. C
分析:list<int>::iterator pos = find(mylist.begin(), mylist.end(), 5); //找到5的位置
reverse(mylist.begin(), pos);//逆置0 1 2 3 4 为 4 3 2 1 0
reverse(pos, mylist.end()); //逆置5 6 7 8 9 为 9 8 7 6 5
逆置完成之后其数据为：4 3 2 1 0 9 8 7 6 5
list<int>::const_reverse_iterator crit = mylist.crbegin(); //反向迭代器进行反向访问
while(crit != mylist.crend()){}
所以答案为:5 6 7 8 9 0 1 2 3 4
2. B
分析:程序在使用迭代器取值时，如果不等于0就进行打印，为0时不打印并删除当前节点，且返回删除结点的下一个结点。
3. C
分析：删除节点后，只有指向当前节点的迭代器失效了，其前后的迭代器仍然有效，因为底层为不连续空间，只有被删除的 节点才会失效。
4. D
A.如果想大量随机读取数据操作，vector是首选的容器
B.如果想大量的插入和删除数据，list效率较高，是首选
C.由于vector底层是连续空间，其迭代器就是相应类型的指针，所以支持对应的操作
D.list迭代器不支持[]运算符
5. A
A.vector在尾部插入数据不需要移动数据，list为双向循环链表也很容易找到尾部，因此两者在尾部插入数据效率相同
B.vector头部插入效率极其低，需要移动大量数据
C.vector由于在头部插入数据效率很低，所以没有提供push_front方法
D.list不支持随机访问
6. B
分析：迭代p需要迭代不重复节点的下一节点，重要的是cur迭代器需要往下迭代，因此cur需要往前移动，二答案A C的cur都不会改变，空白行2是当需要找到重复值时进行节点删除，当删除时当前迭代器会失效，因此需要将迭代器p往后迭代。
6. 完整代码
list.h
#pragma once #include<iostream> #include<assert.h> using namespace std; namespace rtx { template<class T> struct list_node // 定义结点 { T _data; list_node* _prev; list_node* _next; list_node(const T& x = T()) :_data(x) ,_prev(nullptr) ,_next(nullptr) {} }; template<class T, class Ref, class Ptr> struct __list_iterator // 定义迭代器 { typedef list_node<T> Node; typedef __list_iterator<T, Ref, Ptr> iterator; // 在list类里面： // typedef __list_iterator<T, T&, T*> iterator; // typedef __list_iterator<T, const T&, const T*> const_iterator; Node* _node; __list_iterator(Node* node) :_node(node) {} bool operator!=(const iterator& it) { return _node != it._node; } //T& operator*() Ref operator*() { return _node->_data; // 返回结点的数据 } //T* operator->() Ptr operator->() { return &(operator*()); //即 return &(_node->_data); } iterator& operator++() { _node = _node->_next; return *this; // 返回加加后的值 } iterator operator++(int) { iterator tmp(*this); // 拷贝构造一个tmp存储原来的值 _node = _node->_next; return tmp; // 返回加加前的值 } iterator& operator--() { _node = _node->_prev; return *this; // 返回减减后的值 } iterator operator--(int) { iterator tmp(*this); // 拷贝构造一个tmp存储原来的值 _node = _node->prev; return tmp; // 返回减减前的值 } }; template<class T> class list // 定义list类 { typedef list_node<T> Node; public: typedef __list_iterator<T, T&, T*> iterator; typedef __list_iterator<T, const T&, const T*> const_iterator; const_iterator begin() const { return const_iterator(_head->_next); } const_iterator end() const { return const_iterator(_head); } iterator begin()// begin是实际数据的第一个，_head 是哨兵位头结点 { return iterator(_head->_next); } iterator end()// end是实际数据的下一个 { return iterator(_head); } void empty_init()// 创建并初始化哨兵位头结点（即构造函数） { _head = new Node; _head->_next = _head; _head->_prev = _head; } template <class InputIterator> list(InputIterator first, InputIterator last) { empty_init(); while (first != last) { push_back(*first); ++first; } } list() { empty_init(); } void swap(list<T>& x)//提一嘴：void swap(list& x)也行（类里面可以省略<T>，类外不行> { std::swap(_head, x._head); // 换哨兵位头结点就行 } list(const list<T>& lt)//lt2(lt1) { empty_init(); list<T> tmp(lt.begin(), lt.end()); // 迭代器区间构造一个(lt1) swap(tmp); // 直接和lt2换哨兵位头结点 } list<T>& operator=(list<T> lt)//lt3 = lt1 这里lt1直接深拷贝给lt，lt是局部对象，出来作用域直接调析构 { swap(lt);// 把深拷贝出来的lt和lt3交换 return *this; // 把lt3返回 } ~list() { clear(); delete _head; _head = nullptr; } void clear() { iterator it = begin(); while (it != end()) { it = erase(it); // 返回删除位置的下一个结点 } } iterator insert(iterator pos, const T& x) { Node* cur = pos._node; Node* prev = cur->_prev; Node* NewNode = new Node(x); prev->_next = NewNode; NewNode->_prev = prev; NewNode->_next = cur; cur->_prev = NewNode; return iterator(NewNode); } void push_back(const T& x) { //Node* tail = _head->_prev; //Node* NewNode = new Node(x); 思路图：head tail NewNode //tail->_next = NewNode; //NewNode->_prev = tail; //_head->_prev = NewNode; //NewNode->_next = _head; insert(end(), x); } void push_front(const T& x) { insert(begin(), x); } iterator erase(iterator pos) { assert(pos != end()); Node* cur = pos._node; // 删cur Node* prev = cur->_prev; prev->_next = cur->_next; // cur前一个指向cur后一个 cur->_next->_prev = prev; // cur后一个指回cur前一个 delete cur; return iterator(prev->_next); // 返回删除位置下一个 } void pop_back() { erase(begin()); } void pop_front() { erase(--end()); } private: Node* _head; // 哨兵位头结点 }; }
Test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "list.h" namespace rtx { void Test_arrow() { struct Pos { int _a1; int _a2; Pos(int a1 = 0, int a2 = 0) :_a1(a1) , _a2(a2) {} }; Pos aa; Pos* p2 = &aa; p2->_a1; p2->_a2; list<Pos> lt; lt.push_back(Pos(10, 20)); lt.push_back(Pos(10, 21)); list<Pos>::iterator it = lt.begin(); while (it != lt.end()) { //cout << (*it)._a1 << "，" << (*it)._a2 << endl; cout << it->_a1 << "，" << it->_a2 << endl; //实际要写，it->->_a1，但是编译器优化了一个箭头 ++it; } cout << endl; } 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_push_back() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); list<int>::iterator it = lt.begin(); print_list(lt); for (const auto& e : lt) { cout << e << " "; } cout << endl; } void Test_insert() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); //list<int>::iterator pos = find(lt.begin(), lt.end(), 2);// 涉及其它问题，先不这样写 //if (pos != lt.end()) //{ // lt.insert(pos, 20); //} lt.insert(++lt.begin(), 20); lt.push_front(0); lt.push_front(-1); print_list(lt); } void Test_erase() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); lt.erase(++++lt.begin());//发现个好玩的，（删除3） lt.pop_back(); lt.pop_front(); print_list(lt); } void Test_copy() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); list<int> lt2(lt); for (auto& e : lt2) { e *= 10; } print_list(lt); print_list(lt2); } } int main() { //rtx::Test_push_back(); //rtx::Test_arrow(); //rtx::Test_insert(); //rtx::Test_erase(); rtx::Test_copy(); return 0; }
本篇完。
list 的反向迭代器放在后面栈和队列期间讲，下一部分：栈和队列：使用，OJ，模拟实现。
