【C++】list

OK，最近浅浅学习了STL的list，有兴趣不妨垂阅！

目录

1.constructor

2.assign

 3.insert

4.erase 

5. reverse

6.swap 

 7.merge

8.unique 

9.splice 

10.小知识

---

 

同样的，使用list 需要包含一个头文件<list>。<list>中实现了一个类模板list就是我在本博客想要介绍的！！

那么list到底是个啥？

list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代，其底层结构是带头（哨兵卫）双向循环链表。举个栗子：

老规矩，我只介绍一些list 常用接口，且我只介绍C++98版本的接口，其他接口可去list文档细细查阅！！

1.constructor

重载了4个构造函数。好像没什么好介绍的，跟vector的构造函数有异曲同工之妙！！

---

 1.explicit list (const allocator_type& alloc = allocator_type())

无参构造。

#include<list>
using namespace std;
void test()
{list<int> il;list<double> dl;
}
int main()
{test();return 0;
}

---

2.explicit list (size_type n, const value_type& val = value_type(), const allocator_type& alloc = allocator_type())

 构造并初始化n个val。

#include<list>
#include<iostream>
using namespace std;
void test()
{list<int> l(5, 6);for (auto ch : l){cout << ch << ' ';}
}
int main()
{test();return 0;
}

---

3.template <class InputIterator>

list (InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type())

使用迭代器进行初始化构造，也就是构造并用迭代器区间[first，last)的值（包括*first到*(last-1)）初始化。

#include<list>
#include<vector>
#include<iostream>
using namespace std;
void test()
{vector<double> v(3, 9.7);list<double> l(v.begin(), v.end());for (auto ch : l){cout << ch << ' ';}
}
int main()
{test();return 0;
}

---

4.list (const list& x)

拷贝构造。

#include<list>
#include<iostream>
using namespace std;
void test()
{list<int> l1(5, 6);list<int> l2 = l1;//调用拷贝构造for (auto ch : l2){cout << ch << ' ';}
}
int main()
{test();return 0;
}

2.assign

为list容器分配新内容，替换其当前内容，并相应地修改其大小。

---

1.template <class InputIterator>  

void assign (InputIterator first, InputIterator last)

用迭代器区间[first,last)的值来替换list容器原值。 

#include<list>
#include<vector>
#include<iostream>
using namespace std;
void test()
{vector<char> v(6, 'a');list<char> l(2, 'b');l.assign(v.begin(), v.end());for (auto& ch : l){cout << ch << ' ';}
}
int main()
{test();return 0;
}

---

2.void assign (size_type n, const value_type& val)

 用n个val的值来替换list容器原值。

#include<list>
#include<iostream>
using namespace std;
void test()
{list<char> l(2, 'b');l.assign(5, 'Z');for (auto& ch : l){cout << ch << ' ';}
}
int main()
{test();return 0;
}

 3.insert

 看到重载了3个成员函数，其中1个还是函数模板。

均是通过在指定位置的元素之前插入新元素来扩展容器。

我就介绍其中1个：iterator insert (iterator position, const value_type& val)。 在迭代器position指定位置的元素前插入新元素val。返回一个迭代器，该迭代器指向新插入元素。

#include<list>
#include<iostream>
using namespace std;
void test()
{list<int> l(8, 0);auto it = l.begin();for (int i = 0; i < 4; ++i){it++;}it=l.insert(it, 1);cout << *it << endl;for (auto ch : l){cout << ch << ' ';}
}

4.erase 

 重载了2个函数：iterator erase (iterator position)和iterator erase (iterator first, iterator last)

从列表容器中删除单个元素（位置）或一系列元素（[first，last），这有效地减少了被移除的元素数量，从而减小了容器的大小。返回一个迭代器，指向被函数调用擦除的最后一个元素之后的元素。如果操作擦除了序列中的最后一个元素，则这是容器端（end()）。

#include<list>
#include<iostream>
using namespace std;
void test()
{list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);auto it = l.erase(l.begin());//iterator erase (iterator position)cout << *it << endl;
}
int main()
{test();return 0;
}

#include<list>
#include<iostream>
using namespace std;
void test()
{list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);auto it = l.erase(l.begin(),--l.end());//iterator erase (iterator first, iterator last)cout << *it << endl;
}
int main()
{test();return 0;
}

5. reverse

 反转列表容器中元素的顺序。

这个接口和算法库<algorithm>里面的函数模板reverse使用于list容器来说，功能是一样的。

#include<list>
#include<iostream>
#include<algorithm>
using namespace std;
void test()
{list<int> l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);list<int> l2(l1);l1.reverse();//list自带的reversereverse(l2.begin(), l2.end());//算法库的reversefor (auto ch : l1){cout << ch << ' ';}cout << endl;for (auto ch : l2){cout << ch << ' ';}
}
int main()
{test();return 0;
}

6.swap 

重载了2个成员函数：void sort()和template <class Compare> void sort (Compare comp)

对列表中的元素进行排序，改变它们在容器中的位置。

其中第1个成员函数void sort()是排升序的，至于另一个成员函数（函数模板）可以实现按需排序，我还不会操作好吧。

#include<list>
#include<iostream>
using namespace std;
void test()
{list<int> l1;l1.push_back(4);l1.push_back(10);l1.push_back(5);l1.push_back(6);l1.sort();//排升序for (auto ch : l1){cout << ch << ' ';}
}
int main()
{test();return 0;
}

PS：算法库<algorithm> 里面也有sort，那为什么list内部要实现一个sort呢？

因为算法库的sort不支持排序list容器的数据，为什么不支持，请看小知识部分！

 7.merge

这个接口重载有2个成员函数，我就介绍其中这个： void merge (list& x)。这个函数的功能就是将2个均为升序或均为降序的list容器对象合并成1个，合并完后有1个list容器对象就空了。

#include<list>
#include<iostream>
using namespace std;
void test()
{list<int> l1;l1.push_back(1);list<int> l2;l2.push_back(9);l2.push_back(10);l2.push_back(15);l1.merge(l2);cout << "l1: ";for (auto ch : l1){cout << ch << ' ';}cout << endl;cout << "l2: ";for (auto ch : l2){cout << ch << ' ';}
}
int main()
{test();return 0;
}

8.unique 

这个接口重载有2个成员函数，我就介绍其中这个void unique()。从list容器中每个连续的相等元素组中删除除第一个元素外的所有元素。

#include<list>
#include<iostream>
using namespace std;
void test()
{list<int> l;l.push_back(1);l.push_back(2);l.push_back(2);l.push_back(4);l.push_back(5);l.push_back(4);l.push_back(7);l.unique();for (auto ch : l){cout << ch << ' ';}
}
int main()
{test();return 0;
}

所以，如果list对象中，所有相等元素能“挨在一起”的话，例如1个有序list对象，调用了这个接口的话，剩下的元素都是独一无二的，例如：

#include<list>
#include<iostream>
using namespace std;
void test()
{list<char> l;l.push_back('a');l.push_back('c');l.push_back('e');l.push_back('e');l.push_back('e');l.push_back('f');l.push_back('f');l.unique();for (auto ch : l){cout << ch << ' ';}
}
int main()
{test();return 0;
}

9.splice 

 重载了3个成员函数。

---

1.void splice (iterator position, list& x)

将x的所有元素转移（剪切）到容器中，具体是转移（剪切）到position前。

#include<list>
#include<iostream>
using namespace std;
void test()
{list<char> l1(3, 'e');list<char> l2(3, 'b');l2.splice(--l2.end(), l1);for (auto ch : l2){cout << ch << ' ';}
}
int main()
{test();return 0;
}

PS：x和*this可以是同1个 list容器对象，下同。

---

2.void splice (iterator position, list& x, iterator i)

 只将i指向的元素从x转移（剪切）到容器中，具体是转移（剪切）position前。

#include<list>
#include<iostream>
using namespace std;
void test()
{list<char> l(3, 'c');l.push_back('a');l.splice(l.begin(), l, --l.end());for (auto ch : l){cout << ch << ' ';}
}
int main()
{test();return 0;
}

---

3.void splice (iterator position, list& x, iterator first, iterator last)

 将范围[first，last）从x转移（剪切）到容器中，具体转移（剪切）到position前。

#include<list>
#include<iostream>
using namespace std;
void test()
{list<char> l(3, 'c');l.push_back('a');l.splice(l.begin(), l, --l.end(), l.end());for (auto ch : l){cout << ch << ' ';}
}
int main()
{test();return 0;
}

---

总的来说，这个接口可以用来：

1.调整当前list对象元素顺序；

2.将1个list对象元素转移（剪切）到另外1个list对象上。

10.小知识

抛砖引玉：

#include<list>
#include<iostream>
using namespace std;
void test()
{list<char> l(4, 'c');auto it = l.begin();cout << *(it + 3) << endl;
}
int main()
{test();return 0;
}

为什么报错呢？

 因为list的迭代器属于双向迭代器（bidirectional_iterator）。浅浅介绍一下这些知识：

---

迭代器按功能来划分可以分为：普通正向迭代器（iterator）、普通反向迭代器（reverse_iterator）、const正向迭代器（const_iterator）、const反向迭代器（const_reverse_iterator）。  

迭代器按性质类划分可以分为：单向迭代器（forward_iterator）、双向迭代器（bidirectional_iterator）、随机迭代器（random_access_iterator）：

• 单向迭代器（forward_iterator）：支持++等操作，不支持--、+、-等操作。forward_list、unordered_map等容器的迭代器都属于单向迭代器。
• 双向迭代器（bidirectional_iterator）：支持++、--等操作，不支持+、-等操作。list、map等容器的迭代器都属于双向迭代器。
• 随机迭代器（random_access_iterator）：支持++、--、+、-等操作。string、vector等容器的迭代器都属于随机迭代器。
• 其实除了这3种，还引申出了2种抽象的迭代器：只读迭代器（input_iterator）、只写迭代器（output_iterator），这2种迭代器没有哪种容器直接对应它们。

还要明白这些个迭代器的包含关系，如上图：随机迭代器是1种特殊的双向迭代器；双向迭代器是1种特殊的单向迭代器；单向迭代器是1种特殊的只读迭代器 ，亦是1种特殊的只写迭代器。

---

 如何查看某个容器的迭代器性质上归属于哪种迭代器呢？去查询对应的文档就行了。

例如list，看到文档Member types：

 那么容器迭代器的性质上归属于哪种迭代器是什么决定的？

……

回答这个问题之前，别忘了迭代器是在模拟指针的行为。

……

是由该容器底层结构实现的。例如：

……

vector底层是顺序表，得益于其底层物理空间是连续的，所以其迭代器可以支持++、--、+、-等操作以达到任意位置的随机访问。

……

list底层是带头双向循环链表，所以其迭代器可以支持++、--等操作，但是不支持+、-等操作，例如其迭代器执行+n操作，无法得到下n个节点的迭代器，因为它们底层物理空间并不连续，固然可以用操作符重载+来实现，但是是不划算的。

……

 forward_list底层是单链表，所以其迭代器可以支持++等操作，但是不支持--、+、-等操作。例如其迭代器执行--操作，无法得到上1个节点的迭代器，因为它们底层物理空间并不连续且逻辑上是单向的。

---

容器迭代器的性质，决定了该容器适用哪些算法。

例如算法库<algorithm>中的sort，看到其重载了2个函数模板，分别是template <class RandomAccessIterator> void sort (RandomAccessIterator first, RandomAccessIterator last)和template <class RandomAccessIterator, class Compare> void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp)。这里sort函数模板模板参数名字（之一）是RandomAccessiterator，这个名字不是白取的，就是暗示这个算法只能排序其迭代器是随机迭代器的容器的数据。

若某个迭代器是非随机迭代器的容器使用算法库的sort，例如：

#include<list>
#include<iostream>
#include<algorithm>
using namespace std;
void test()
{list<int> l(2, 3);sort(l.begin(), l.end());
}
int main()
{test();return 0;
}

报错： 

若迭代器是随机迭代器的容器使用算法库的sort，例如：

#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
void test()
{string s;s.push_back('a');s.push_back('e');s.push_back('b');s.push_back('g');sort(s.begin(), s.end());for (auto ch : s){cout << ch << ' ';}
}
int main()
{test();return 0;
}

成功排升序：

造成sort只能排序迭代器是随机迭代器的容器数据的原因在于：sort底层是快速排序，需要迭代器能支持++、--、+、-等操作的，具体的就要去看sort的源代码了。

这就是为什么 算法库的sort不支持排序list容器的数据了。

 所以，以后使用算法库的算法时，要搞清楚该容器适合用该算法吗！！！

感谢阅读！