前言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 val
list<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 22
mylist.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 100
mylist.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 5
int arr1[] = { 11,12,13,14,15 };// 11 12 13 14 15
vector<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 val
it = 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 90
it1 = 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;
}
}