C++--＞stl: list的使用
前言list的认识
list是可以在固定时间（O（1））内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向(当然有一个哨兵位 就是说头节点)其前一个元素和后一个元素。3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能向前迭代，已让其更简单高（list是doubly list的接口 forward_list是单链表的接口）效。4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率 更好。5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list 的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间 （需要创建一个结点去遍历，比随机访问效率低）开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的list来说这不合适 可能是一个重要的因素
1 list的构造
常用的构造函数
default (1)
（默认构造）
explicit list (const allocator_type& alloc = allocator_type());fill (2)
n个val值填充
explicit list (size_type n, const value_type& val = value_type(),const allocator_type& alloc = allocator_type());range (3)
迭代器构造
template <class InputIterator>list (InputIterator first, InputIterator last,const allocator_type& alloc = allocator_type());copy (4)
拷贝构造
list (const list& x);
参考代码 ：
void print_list(list<int>& list1)
{list<int>::iterator it = list1.begin();while (it != list1.end()){cout << *it;it++;}cout << endl;}
void construct_test()
{list<int>list_1;// 空构造list<int>list_2(20,0);// n vallist<int>::iterator it = list_2.begin(); // 迭代器构造 list<int> th(list_2.begin(),list_2.end());// 不支持的写法 list<int> th(list_2.begin(),list_2.begin()+4);// 因为list的迭代器不支持随机访问哦 其实本质上是因为只给迭代器封装了++的操作 int arr[] = {1,2,3,4,5,6};list<int>four(arr,arr+4);// 这也是迭代器构造 数组肯定是可以通过下标 随机访问啦 // 拷贝构造//list<int> five = four;list<int> five(four);print_list(five);}2. list的迭代器
list的图解
迭代器的理解:
这个迭代器的内部封装可以大致这么理解：
肯定是对node的操作，封装node的移动，有++,--以及!= 判断俩个迭代器是否相等就这样就很常见，封装的目的很简单，就是为了统一容器的操作哦！。后期博客我会更新其中的模拟实现这是很有意思的：内部是没有封装+某个数的所以之前例子中指出 像这样的 list<int>::iterator(it,it+3); 是不被允许的哦！总之因为list的底层容器是双向链表，每个节点地址之间是不连续的，所以我们为了统一容器操作就封装迭代器了。
迭代器使用：代码实例：
void iterator_test() {int arr[] = { 1,2,3,4,5,6 };list<int>four(arr, arr + 5);// 用迭代器遍历four这个链表list<int>::iterator it = four.begin();// 正向迭代器list<int>::reverse_iterator rit = four.rbegin();// 反向迭代器while (it != four.end()){cout << *it;it++;}cout << endl;while (rit != four.rend()){cout << *rit;rit++;}cout << endl;}
输出：12345
54321
doubly list的图解
这里只标出了 node之间指针的关系，这里值得注意的就是如何实现双向循环的，就是创建一个头节点，头节点作用就是用来很方便的实现增删查改（减少判空这个策略数据结构中可以多了解理解） 总之就是让头节点的pre指向尾节点，尾节点的next指向头节点。 总之头节点是不存放有效数据的！ 所以下面我说说迭代器遍历的问题！
list迭代器遍历的理解：
显然 list<T>iterator:: begin 指向的是头节点的下一个位置，node结构体中总是存放的是头节点，所以需要遍历的时候需要总是从头节点开始一一遍历，而不是随机访问。判断到尾部的方法有很多一个是根据size，以及cur节点的遍历到了头节点了。
3. list element access(元素获取)
list的获取常用的就是一个是front 和 back 双向链表根据头节点实现起来很方便的。
3.1 reference front() 和reference back的使用
这个list的front的成员函数，简单来说就是返回一个头节点的元素引用。这里的referrence其实是一个typedef，这个在库里面实现是很常见的 可以这样理解：typedef reference T;back同理如上。
// list::front
#include <iostream>
#include <list>int main ()
{std::list<int> mylist;mylist.push_back(77);mylist.push_back(22);// now front equals 77, and back 22mylist.front() -= mylist.back();std::cout << "mylist.front() is now " << mylist.front() << '\n';return 0;
}输出： 55
4. list modified 元素修改
list常用的修改方面的有： 头插，头删，尾删，尾插，还有指定位置删除，和指定位置插入，还有指定尾插删除， 以及swap （经常被用于去写构造函数的还有拷贝构造）
4.1 push_front 和pop_front
实现：
// list::push_front
#include <iostream>
#include <list>int main ()
{std::list<int> mylist (2,100); // two ints with a value of 100mylist.push_front (200);mylist.push_front (300);std::cout << "mylist contains:";for (std::list<int>::iterator it=mylist.begin(); it!=mylist.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';return 0;
}
实现：
// list::pop_front
#include <iostream>
#include <list>int main ()
{std::list<int> mylist;mylist.push_back (100);mylist.push_back (200);mylist.push_back (300);std::cout << "Popping out the elements in mylist:";while (!mylist.empty()){std::cout << ' ' << mylist.front();mylist.pop_front();}std::cout << "\nFinal size of mylist is " << mylist.size() << '\n';return 0;
}
4.2 push_back和pop_front
尾插和尾删 返回值都是void注意哦
// list::push_back
#include <iostream>
#include <list>int main ()
{std::list<int> mylist;int myint;std::cout << "Please enter some integers (enter 0 to end):\n";do {std::cin >> myint;mylist.push_back (myint);} while (myint);std::cout << "mylist stores " << mylist.size() << " numbers.\n";return 0;
}
// list::pop_back
#include <iostream>
#include <list>int main ()
{std::list<int> mylist;int sum (0);mylist.push_back (100);mylist.push_back (200);mylist.push_back (300);while (!mylist.empty()){sum+=mylist.back();mylist.pop_back();}std::cout << "The elements of mylist summed " << sum << '\n';return 0;
}4.3 insert
在指定位置（用迭代器哦） 插入一个元素，插入n个val 在指定位置在指定位置插入一个范围迭代器区间的元素
void insert_test() {int arr[] = { 1,2,3,4,5 };// 1 2 3 4 5int arr1[] = { 11,12,13,14,15 };// 11 12 13 14 15vector<int>v1(arr,arr+5);list<int> mylist(arr1,arr1+5); // !list<int>::iterator it = mylist.begin();it++;mylist.insert(it,10);// 迭代器可能存在失效的问题 所以这里一定要给it重赋值 print_list(mylist);// n valit = mylist.begin();it++;mylist.insert(it, 10,1);print_list(mylist);// 范围插入it = mylist.begin();it++;mylist.insert(it, v1.begin()+2, v1.end());print_list(mylist);}
输出：11 10 12 13 14 15
11 1 1 1 1 1 1 1 1 1 1 10 12 13 14 15
11 3 4 5 1 1 1 1 1 1 1 1 1 1 10 12 13 14 15
11 1 1 1 1 1 1 1 1 1 1 10 12 13 14 15
11 3 4 5 1 1 1 1 1 1 1 1 1 1 10 12 13 14 15
4.4 erase 删除
传递的参数是list的迭代器，指定位置删除和指定的迭代器范围区间的元素删除。
std:: iterator& advance(iterator，len) 这是库里的移动迭代器的函数
// erasing from list
#include <iostream>
#include <list>int main ()
{std::list<int> mylist;std::list<int>::iterator it1,it2;// set some values:for (int i=1; i<10; ++i) mylist.push_back(i*10);// 10 20 30 40 50 60 70 80 90it1 = it2 = mylist.begin(); // ^^advance (it2,6); // ^ ^++it1; // ^ ^it1 = mylist.erase (it1); // 10 30 40 50 60 70 80 90// ^ ^it2 = mylist.erase (it2); // 10 30 40 50 60 80 90// ^ ^++it1; // ^ ^--it2; // ^ ^mylist.erase (it1,it2); // 10 30 60 80 90// ^std::cout << "mylist contains:";for (it1=mylist.begin(); it1!=mylist.end(); ++it1)std::cout << ' ' << *it1;std::cout << '\n';return 0;
}
5. 迭代器失效问题
我们之前说过迭代器的实现可以理解为一个封装了node的移动和判断的类。 这里的数据存放是node，所以本质上还是用node*指向了一个节点，所以在list中只要该节点不删除，这个节点依然存在。在list中插入不会导致迭代器失效，因为这个节点并没有被销毁（vector中的迭代器失效是因为他们的内存是连续的，当扩容的时候可能导致旧内存被销数据被移动到新内存）但是list的底层是双向循环链表，内存之间都是用指针（地址）连接起来的，不用在乎是否连续，你不主动销毁内存是不会被销毁的。所以只有当删除的时候才会被销毁。
谈谈erase和insert的返回值
erase:
iterator erase (iterator position); iterator erase (iterator first, iterator last);
insert:
| single element (1) | iterator insert (iterator position, const value_type& val); |
|---|---|
| fill (2) | void insert (iterator position, size_type n, const value_type& val); |
| range (3) | template <class InputIterator>void insert (iterator position, InputIterator first, InputIterator last); |
insert：大体上分为两，一种是插入一个元素，一个是插入多个元素。返回值：简单理解就是返回插入元素后的下一个位置的元素erase则是返回删除元素的下一个位置
处理迭代器失效： 就是重新赋值给迭代器：
错误实例 没有重新赋值
修正：
代码：
void TestListIterator1()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array + sizeof(array) / sizeof(array[0]));auto it = l.begin();while (it != l.end()){// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给//其赋值it =l.erase(it);++it;}
}