C++复习笔记10

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)。

STL中list容器的各种接口演示：

#include<iostream>
#include<list>
#include<functional>
using namespace std;//构造方法
void test01()
{int arr[] = { 1,2,3,4,5,6,7,8,9,10 };list<int> list1;//空链表list<int> list2(10);//10个0list<int> list3(10, 5);//10个5list<int> list4(arr, arr + 10);//1到10list<int> list5(list4);//拷贝构造list<int> list6(list5.begin(), list5.end());//迭代器范围构造for (auto e : list6){cout << e << " ";}
}//迭代器的使用
//STL不成文的规定：1.STL的区间都是左闭右开区间
//begin()对应第一个元素
//end()对应最后一个元素的下一个元素
//2.带下划线的成员都是在底层内部调用的，不是外部对象调用的
//3.STL插入数据时，插入位置一般是在迭代器所指位置前面插入
void test02()
{int arr[] = { 1,2,3,4,5,6,7,8,9,10 };//list<int> list1(&arr[0], &arr[9]);//左闭右开，不包含10list<int> list1(arr, arr + 10);for (auto e : list1){cout << e << " ";}cout << endl;auto it = list1.begin();cout << typeid(it).name() << endl;while (it != list1.end()){cout << *it << " ";++it;}cout << endl;for (list<int>::iterator it = list1.begin(); it != list1.end(); it++){cout << *it << " ";}cout << endl;list<int>::reverse_iterator rit = list1.rbegin();//反向迭代器，整套使用while (rit != list1.rend()){cout << *rit << " ";++rit;//这里还是++}cout << endl;}//常链表对应常迭代器
void test03()
{int arr[] = { 1,2,3,4,5,6,7,8,9,10 };const list<int> list1(arr, arr + 10);for (list<int>::const_iterator it = list1.begin(); it != list1.end(); it++){cout << *it << " ";}cout << endl;list<int>::const_reverse_iterator rit = list1.rbegin();//反向迭代器，整套使用while (rit != list1.rend()){cout << *rit << " ";++rit;//这里还是++}cout << endl;
}void test04()
{int arr[] = { 1,2,3,4,5,6,7,8,9,10 };const list<int> list1(arr, arr + 10);cout << "empty = "<<list1.empty() << endl;cout << "size = " << list1.size() << endl;cout << "front = " << list1.front() << endl;cout << "back = " << list1.back() << endl;//push_back() push_front() pop_back() pop_front()
}void test05()
{int arr[] = { 1,2,3,4,5,6,7,8,9,10 };list<int> list1(arr, arr + 10);list<int> list2;list2.push_back(20);list2.push_back(25);list2.push_front(30);list<int>::iterator pos = list1.begin();//list1.insert(pos, 100);//插一个数//list1.insert(pos, 10, 2);//插10个数//list1.insert(pos, list2.begin(), list2.end());//插入迭代器区间list1.insert(pos, arr, arr + 10);//插入指针区间for (auto e : list1){cout << e << " ";}
}void test06()
{int arr[] = { 1,2,3,4,5,6,7,8,9,10 };list<int> list1(arr, arr + 10);list<int> list2;list2.push_back(20);list2.push_back(25);list2.push_front(30);auto pos = find(list1.begin(),list1.end(),5);//find算法//list1.insert(pos, list2.begin(), list2.end());list1.erase(pos);//按位置删除list1.erase(list1.begin(), list1.end());//按区间删除list1.swap(list2);//交换操作//list1.clear();//清除操作for (auto e : list1){cout << e << " ";}
}void test07()
{int arr[] = { 1,2,3,4,5,6,7,8,9,10 };list<int> list1(arr, arr + 10);//list1.resize(20);扩大，补零list1.resize(20, 13);//扩大，补指定值list1.resize(5, 15);//截断并保留原来值，指定的值不起作用for (auto e : list1){cout << e << " ";}
}void test08()
{int arr[] = { 1,2,3,4,5,6,7,8,9,10 };list<int> list1(arr, arr + 10);for (auto e : list1){cout << e << " ";}cout << endl;list1.assign(5, 0);for (auto e : list1){cout << e << " ";}
}//拼接，这里是l2移到l1后面，l2就空了
void test09()
{int arr[] = { 1,2,3,4,5,6,7,8,9,10 };int brr[] = { 10,20,30,40,50 };list<int> l1(arr,arr+10);list<int> l2(brr,brr+5);for (auto e : l1){cout << e << " ";}cout << endl;l1.splice(l1.end(), l2);for (auto e : l1){cout << e << " ";}cout << endl;for (auto e : l2){cout << e << " ";}
}//删除等于某个值的所有元素
void test10()
{int arr[] = { 1,2,3,4,5,6,7,8,9,10 };list<int> list1(arr, arr + 10);for (auto e : list1){cout << e << " ";}cout << endl;list1.remove(4);for (auto e : list1){cout << e << " ";}
}//unique连续重复值只保留一个
void test11()
{int arr[] = { 1,2,3,4,5,5,5,5,5,5,6,7,8,9,10,3,3,2,5,6 };int n = sizeof(arr) / sizeof(arr[0]);list<int> list1(arr, arr + n);for (auto e : list1){cout << e << " ";}cout << endl;list1.unique();for (auto e : list1){cout << e << " ";}cout << endl;
}class myCompare
{
public:bool operator()(int v1, int v2) const{return v1 > v2;}
};void test12()
{int arr[] = { 1,2,3,4,5,5,5,5,5,5,6,7,8,9,10,3,3,2,5,6 };int n = sizeof(arr) / sizeof(arr[0]);list<int> list1(arr, arr + n);//list1.sort(myCompare());//仿函数由升序变降序，自己写的谓词list1.sort(greater<int>());//使用内建函数对象for (auto e : list1){cout << e << " ";}cout << endl;list1.reverse();//反转for (auto e : list1){cout << e << " ";}cout << endl;
}void main()
{test12();system("pause");
}

list的迭代器失效：前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

删除it后，空间已经释放，t++无法正常指向下一个节点，出现段错误。

也就是说在删除某迭代器的对应结点后，就不能对这个迭代器进行操作了，因为它已经失效。

#include<iostream>
#include<list>
using namespace std;void test01()
{list<int> l1;int arr[] = { 1,2,3,4,5,6,7,8,9,10 };l1.assign(arr, arr + 10);auto it = l1.begin();while (it != l1.end()){l1.erase(it);++it;}
}void main()
{test01();system("pause");
}

其他节点不受影响：

void test02()
{list<int> l1;int arr[] = { 1,2,3,4,5,6,7,8,9,10 };l1.assign(arr, arr + 10);auto it = l1.begin();auto it1 = find(l1.begin(), l1.end(), 5);l1.erase(it);it1++;
}

防止迭代器失效：删除接口删除时会返回删除位置的下一个迭代器。

void test03()
{list<int> l1;int arr[] = { 1,2,3,4,5,6,7,8,9,10 };l1.assign(arr, arr + 10);auto it = l1.begin();while (it != l1.end()){it = l1.erase(it);//删除时会返回删除位置的下一个迭代器}	for (auto e : l1){cout << e << " ";}
}

list和vector的区别：

1.vector底层是动态顺序表存储在一段连续空间，shi是带头结点的双向循环链表。

2.vector支持随机访问，访问某元素效率为O(1)，list不支持随机访问，访问某个元素的效率为O(n)。

3.vector任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低，list任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1)。

4.vector的迭代器为原生态指针， list的迭代器是对原生态指针（结点指针）进行封装。

5.vector在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效。list插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响。

6.vector需要高效存储，支持随机访问，不关心插入删除效率,list大量插入和删除操作，不关心随
机访问。

list的模拟实现

#include<iostream>
#include<algorithm>
using namespace std;namespace Test
{template<typename Y>class list;//声明了才能找到template<class T>class List_iterator;template<typename T>class Node{friend class List_iterator<T>;friend class list<T>;//访问其私有成员Node():_val(T()),_next(nullptr),_prev(nullptr){}Node(const T& val, Node* next = nullptr, Node* prev = nullptr) :_val(val),_next(next), _prev(prev){}~Node(){}private:T _val;Node* _next;Node* _prev;};template<class T>class List_iterator{public:typedef List_iterator<T> self;List_iterator(Node<T>* _P) :_Ptr(_P) {}bool operator!=(const List_iterator<T>& it)//<T>别忘了{return this->_Ptr != it._Ptr;}T& operator*(){return _Ptr->_val;}self& operator++(){_Ptr = _Ptr->_next;return *this;}self operator++(int)//一直是int?{//List_iterator tmp(this->_Ptr);self tmp(*this);//类模板明确类型后才是具体类才能实例化对象this->_Ptr = this->_Ptr->_next;return tmp;}self& operator--(){_Ptr = _Ptr->_prev;return *this;}self operator--(int)//一直是int?{//List_iterator tmp(this->_Ptr);self tmp(*this);//类模板明确类型后才是具体类才能实例化对象this->_Ptr = this->_Ptr->_prev;return tmp;}Node<T>* _Mynode(){return _Ptr;}private:Node<T>* _Ptr;};template<class T>class list{public:typedef List_iterator<const T> const_iterator;typedef List_iterator<T> iterator;typedef iterator _It;list() :_Size(0){CreatHead();}Node<T>*& getHead(){return _Head;}iterator begin(){return iterator(_Head->_next);}const_iterator begin() const{return const_iterator(_Head->_next);}const_iterator end() const{return const_iterator(_Head->_next);}iterator end(){return iterator(_Head);}void push_back(const T& x){insert(end(), x);/*Node<T>* _S = new Node<T> (x);_S->_prev = _Head->_prev;_S->_next = _Head;_S->_next->_prev = _S;_S->_prev->_next = _S;_Size++;*/}void pop_back(){erase(--end());}void push_front(const T& x){insert(begin(), x);}void pop_front(){erase(begin());}iterator insert(iterator _P, const T& x){Node<T>* _S = new Node<T>(x);Node<T>* cur = _P._Mynode();_S->_next = cur;_S->_prev = cur->_prev;_S->_next->_prev = _S;_S->_prev->_next = _S;_Size++;return iterator(_S);}iterator erase(iterator _P){Node<T>* cur = _P._Mynode();Node<T>* next_node = cur->_next;cur->_next->_prev = cur->_prev;cur->_prev->_next = cur->_next;delete cur;_Size--;return iterator(next_node);}iterator erase(iterator _first, iterator _last){while (_first != _last){_first = erase(_first);//重载内部调另一个重载，秀}return iterator(_last);}void swap(list<T>& lt){std::swap(_Head, lt.getHead());}void clear(){erase(begin(), end());}size_t size() const{return _Size;}bool empty(){return _Size == 0;}T& front() {return *begin();}T& front() const{return *begin();}T& back() const{return *end();}T& back() {return *(--end());}list(int n, const T& val = T()){CreatHead();while (n-- ){insert(begin(), val);}}list(_It _first, _It _last){CreatHead();while (_first != _last){push_back(*_first);++_first;}}list( list& lt)//{CreatHead();list<T> tmp(lt.begin(), lt.end());std::swap(_Head, tmp._Head);//注意这里的作用域切换_Size = lt.size();}list<T>& operator=( list<T>& lt){if (this != &lt){list<T> tmp(lt.begin(), lt.end());std::swap(_Head, tmp._Head);//this->swap(lt);}return *this;}~list(){clear();delete _Head;_Head = nullptr;}protected:void CreatHead(){_Head = new Node<T>;_Head->_next = _Head;_Head->_prev = _Head;}private:Node<T>* _Head;size_t _Size;};
}void test01()
{Test::list<int> l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);l1.push_back(5);Test::list<int>::iterator it = l1.begin();while (it != l1.end()){cout << *it << " ";it++;}cout << endl;l1.erase(l1.begin());it = l1.begin();while (it != l1.end()){cout << *it << " ";it++;}cout << endl;l1.clear();it = l1.begin();while (it != l1.end()){cout << *it << " ";it++;}cout << endl;
}void test02()
{Test::list<int> l1(5, 10);for (auto it = l1.begin(); it != l1.end(); it++){cout << *it << " ";}cout << endl;Test::list<int>l2(l1);for (auto it = l2.begin(); it != l2.end(); it++){cout << *it << " ";}cout << endl;
}void test03()
{Test::list<int> l1(5, 10);Test::list<int> l2;l2 = l1;for (auto it = l2.begin(); it != l2.end(); it++){cout << *it << " ";}
}void test04()
{Test::list<int>l1;for (int i = 0; i < 6; i++){l1.push_back(i);}for (auto e : l1){cout << e << " ";}cout << endl;l1.push_front(10);for (auto e : l1){cout << e << " ";}cout << endl;l1.pop_back();for (auto e : l1){cout << e << " ";}cout << endl;l1.pop_front();for (auto e : l1){cout << e << " ";}
}void test05()
{Test::list<int>l1;for (int i = 0; i < 6; i++){l1.push_back(i);}Test::list<int>l2;for (int i = 6; i < 11; i++){l2.push_back(i);}l1.swap(l2);for (auto e : l1){cout << e << " ";}cout << endl;for (auto e : l2){cout << e << " ";}cout << endl;
}void test06()
{const Test::list<int>l1(5,10);cout << l1.front() << endl;
}void main()
{test06();system("pause");
}