C++ STL之LIST详解A

List 容器

list是C++标准模版库(STL,Standard Template Library)中的部分内容。实际上,list容器就是一个双向链表,可以高效地进行插入删除元素。

使用list容器之前必须加上<vector>头文件：#include<list>;

list属于std命名域的内容，因此需要通过命名限定：using std::list;也可以直接使用全局的命名空间方式：using namespace std;

list类的STL实现允许在开头、末尾和中间插入元素,且所需的时间固定。

构造函数

　 list<int> c0; //空链表

　　list<int> c1(3); //建一个含三个默认值是0的元素的链表

　　list<int> c2(5,2); //建一个含五个元素的链表，值都是2

　　list<int> c4(c2); //建一个c2的copy链表

　　list<int> c5(c1.begin(),c1.end()); ////c5含c1一个区域的元素[_First, _Last)。

成员函数

c.begin() 返回指向链表第一个元素的迭代器。

c.end() 返回指向链表最后一个元素之后的迭代器。

 1 int main()
 2 {
 3     std::list<int> list1{1,2,3,4,5};
 4     std::list<int>::const_iterator iter;
 5     /*auto*/ for(iter=list1.cbegin();iter!=list1.cend();++iter)
 6     {
 7         std::cout<<*iter<<std::endl;
 8     }
 9     return 0;
10 }

逆迭代器，反向迭代(链表倒过来最后成为第一个向后迭代)

c.rbegin() 返回逆向链表的第一个元素,即c链表的最后一个数据。

c.rend() 返回逆向链表的最后一个元素的下一个位置,即c链表的第一个数据再往前的位置。

 1 int main()
 2 {
 3     std::list<int> list1{1,2,3,4,5};
 4     std::list<int>::reverse_iterator iter;
 5     for(iter=list1.rbegin();iter!=list1.rend();++iter)
 6     {
 7         std::cout<<*iter<<std::endl;
 8     }
 9 
10     return 0;
11 }

重载了operator=赋值运算符

 1 int main()
 2 {
 3     std::list<int> list_new{1,2,3,4,5};
 4     std::list<int> list1=list_new;      //operator= 赋值
 5     std::list<int>::reverse_iterator iter;
 6     for(iter=list1.rbegin();iter!=list1.rend();++iter)
 7     {
 8         std::cout<<*iter<<std::endl;
 9     }
10 
11     return 0;
12 }

c.assign(n,num) 将n个num拷贝赋值给链表c。

c.assign(beg,end) 将[beg,end)区间的元素拷贝赋值给链表c。

 1 template<typename T>
 2 void DisplayContents(const T& Input)              //打印容器模板函数
 3 {
 4     for(auto iter=Input.cbegin();iter!=Input.cend();++iter)
 5     {
 6         std::cout<<*iter<<" ";
 7     }
 8     std::cout<<std::endl;
 9 }
10 
11 int main()
12 {
13     std::list<int> list1{1,2,3,4,5};
14     int a[5]={6,7,8,9,10}; //数组名范围赋值      
15     list1.assign(a,a+5);
16     DisplayContents(list1);
17 
18     std::vector<int> vec1{11,12,13,14,15};
19     list1.assign(vec1.cbegin(),vec1.cend());  //迭代器范围赋值
20     DisplayContents(list1);
21 
22     list1.assign(3,100);       //3个100数值填充
23     DisplayContents(list1);
24     return 0;
25 }

c.front() 返回链表c的第一个元素。

c.back() 返回链表c的最后一个元素。

 1 template<typename T>
 2 void DisplayContents(const T& Input)              //打印容器模板函数
 3 {
 4     for(auto iter=Input.cbegin();iter!=Input.cend();++iter)
 5     {
 6         std::cout<<*iter<<" ";
 7     }
 8     std::cout<<std::endl;
 9 }
10 
11 int main()
12 {
13     std::list<int> list1{1,2,3,4,5};
14     std::cout<<list1.front()<<std::endl;
15     std::cout<<list1.back()<<std::endl;
16     DisplayContents(list1);
17     return 0;
18 }

c.empty() 判断链表是否为空。

 1 int main()
 2 {
 3     std::list<int> list1{1,2,3,4,5};
 4     while (!list1.empty())
 5     {
 6         std::cout<<list1.front()<<" ";
 7         list1.pop_front();
 8     }
 9     return 0;
10 }

c.size() 返回链表c中实际元素的个数。

c.max_size() 返回链表c可能容纳的最大元素数量。

1 int main()
2 {
3     std::list<int> list1{1,2,3,4,5};
4     std::cout<<list1.size()<<std::endl;
5     std::cout<<list1.max_size()<<std::endl;
6     return 0;
7 }

c.clear() 清除链表c中的所有元素

 1 template<typename T>
 2 void DisplayContents(const T& Input)              //打印容器模板函数
 3 {
 4     if(Input.empty())
 5     {
 6         std::cout<<"it's empty!";
 7     }
 8     for(auto iter=Input.cbegin();iter!=Input.cend();++iter)
 9     {
10         std::cout<<*iter<<" ";
11     }
12     std::cout<<std::endl;
13 }
14 
15 int main()
16 {
17     std::list<int> list1{1,2,3,4,5};
18     DisplayContents(list1);
19 
20     list1.clear();
21     DisplayContents(list1);
22     return 0;
23 }

c.insert(pos,num) 在pos位置插入元素num。

c.insert(pos,n,num) 在pos位置插入n个元素num。

c.insert(pos,beg,end) 在pos位置插入区间为[beg,end)的元素。

 1 template<typename T>
 2 void DisplayContents(const T &Input)              //打印容器模板函数
 3 {
 4     if (Input.empty())
 5     {
 6         std::cout << "it's empty!";
 7     }
 8     for (auto iter = Input.cbegin(); iter != Input.cend(); ++iter)
 9     {
10         std::cout << *iter << " ";
11     }
12     std::cout << std::endl;
13 }
14 
15 int main()
16 {
17     std::list<char> list1;
18     list1.insert(list1.cbegin(),'H');
19     list1.insert(list1.cbegin(),'E');
20     list1.insert(list1.cbegin(),'L');
21     list1.insert(list1.cbegin(),'L');
22     list1.insert(list1.cbegin(),'O');
23     DisplayContents(list1);
24     list1.clear();
25     list1.insert(list1.cbegin(),5,'H');
26     DisplayContents(list1);
27 
28     list1.clear();
29     char aray[5]={'H','E','L','L','O'};
30     list1.insert(list1.cbegin(),aray,aray+5);
31     DisplayContents(list1);
32     return 0;

c.erase(pos)　　　　删除pos位置的元素。

c.erase(iterator.begin(),iterator.end()) 删除范围内的数据

//删除POS即迭代器；

c.push_back(num) 在末尾增加一个元素(向后延伸添加)

c.pop_back() 删除末尾的元素。

c.push_front(num) 在开始位置增加一个元素(向前延伸添加)

c.pop_front() 删除第一个元素。

 1 template<typename T>
 2 void DisplayContents(const T &Input)              //打印容器模板函数
 3 {
 4     if (Input.empty())
 5     {
 6         std::cout << "it's empty!";
 7     }
 8     for (auto iter = Input.cbegin(); iter != Input.cend(); ++iter)
 9     {
10         std::cout << *iter << " ";
11     }
12     std::cout << std::endl;
13 }
14 
15 int main()
16 {
17     std::list<int> list1;
18     list1.push_back(1);
19     list1.push_back(2);
20     list1.push_back(3);
21     DisplayContents(list1);
22     list1.push_front(1);
23     list1.push_front(2);
24     list1.push_front(3);
25     DisplayContents(list1);
26     while(!list1.empty())
27     {
28         list1.pop_front();
29         list1.pop_back();
30         DisplayContents(list1);
31     }
32     return 0;
33 }

resize(n) 从新定义链表的长度,超出原始长度部分用0代替,小于原始部分删除。

resize(n,num) 从新定义链表的长度,超出原始长度部分用num代替。

 1 int main()
 2 {
 3     std::list<int> list1{1,2,3,4,5};
 4     std::cout<<"list_size:"<<list1.size()<<std::endl;
 5     DisplayContents(list1);
 6     
 7     list1.resize(10);
 8     std::cout<<"list_size:"<<list1.size()<<std::endl;
 9     DisplayContents(list1);
10     
11     list1.resize(2);      //原来的丢失
12     std::cout<<"list_size:"<<list1.size()<<std::endl;
13     DisplayContents(list1);
14     
15     list1.resize(5,9);
16     std::cout<<"list_size:"<<list1.size()<<std::endl;
17     DisplayContents(list1);
18 
19     return 0;
20 }

c1.swap(c2); 将c1和c2交换。

swap(c1,c2); 同上

 1 int main()
 2 {
 3     std::list<int> list1{1, 2, 3, 4, 5};
 4     std::list<int> list2{6, 7, 8, 9, 10,11};
 5 
 6     std::cout<<"list1:";
 7     DisplayContents(list1);
 8     std::cout<<"size: "<<list1.size()<<std::endl;
 9     std::cout<<"list2:";
10     DisplayContents(list2);
11     std::cout<<"size: "<<list2.size()<<std::endl;
12 
13     list1.swap(list2);
14 
15     std::cout<<"list1:";
16     DisplayContents(list1);
17     std::cout<<"size: "<<list1.size()<<std::endl;
18     std::cout<<"list2:";
19     DisplayContents(list2);
20     std::cout<<"size: "<<list2.size()<<std::endl;
21     return 0;
22 }

c1.merge(c2) 合并2个有序的链表并使之有序,从新放到c1里,释放c2。

c1.merge(c2,comp) 合并2个有序的链表并使之按照自定义规则排序之后从新放到c1中,释放c2。

 1 template <typename T>
 2 struct Sort
 3 {
 4     bool operator()(const T& a,const T& b)
 5     {
 6         return (a<b);
 7     }
 8 };
 9 
10 int main()
11 {
12     std::list<int> list1{1,2,3,4,5};
13     std::list<int> list2{6,7,8,9,10};
14 
15     list1.merge(list2);  //注意LIST2 被释放掉了;
16     DisplayContents(list1);
17 
18     std::list<int> list3{89,23,23,45,234,55,23};
19     list1.merge(list3,Sort<int>());  //升序方式   前提2个链表必须有序为你想要的排序方式
20     DisplayContents(list1);
21 
22     return 0;
23 }

c1.splice(c1.beg,c2) 将c2连接在c1的beg位置,释放c2

c1.splice(c1.beg,c2,c2.beg) 将c2的beg位置的元素连接到c1的beg位置，并且在c2中施放掉beg位置的元素

c1.splice(c1.beg,c2,c2.beg,c2.end) 将c2的[beg,end)位置的元素连接到c1的beg位置并且释放c2的[beg,end)位置的元素

 1 template<typename T>
 2 void DisplayContents(const T &Input)              //打印容器模板函数
 3 {
 4     if (Input.empty())
 5     {
 6         std::cout << "it's empty!";
 7     }
 8     for (auto iter = Input.cbegin(); iter != Input.cend(); ++iter)
 9     {
10         std::cout << *iter << " ";
11     }
12     std::cout << std::endl;
13 }
14 
15 
16 int main()
17 {
18     std::list<int> list1{1,2,3,4,5};
19     std::list<int> list2{6,7,8,9,10};
20 
21     std::list<int>::iterator iter1;
22     for(auto iter2=list1.begin();iter2!=list1.end();++iter2)
23     {
24         if(*iter2==4)
25         {
26             iter1=iter2;
27             break;
28         }
29     }
30     //整段链接过去
31     list1.splice(iter1,list2);  //释放list2(clear()),从连接位置前面间隔开始；
32     DisplayContents(list1);
33 
34     list2.assign(10,99);
35     DisplayContents(list2);
36 
37     //点对点连接(转移一个)
38     list2.splice(list2.begin(),list1,list1.begin());
39     DisplayContents(list2);
40 
41     //选取某段目的数据段连接到另一个段的某点开始转移,释放原来的；
42     list2.splice(list2.begin(),list1,list1.begin(),list1.end());
43     DisplayContents(list2);
44 
45 
46     return 0;
47 }

remove(num) num of list_type_date;

remove_if([](){}) 删除符合条件的;

 1 int main()
 2 {
 3     std::list<int> list1{1,2,3,4,5};
 4     list1.remove(5);
 5     DisplayContents(list1);
 6 
 7     list1.remove_if([](int& a){return (a==3);});
 8     DisplayContents(list1);
 9 
10     return 0;
11 }

reverse() 翻转链表数据；

它是一个没有参数的简单函数,确保指向元素的迭代器在反转后仍有效——如果程序员保存了该迭代器。

1 int main()
2 {
3     std::list<int> list1{1,2,3,4,5};
4     list1.reverse();
5     DisplayContents(list1);
6     return 0;
7 }

unique() 删除相邻重复元素;

1 int main()
2 {
3     std::list<int> list1{1,1,1,2,2,3,3,3,4,4,5};
4     list1.unique();   //删除重复元素(追求独一无二);
5     DisplayContents(list1);
6     return 0;
7 }

c.sort() 将链表排序，默认升序(std::less)

c.sort(comp) 自定义回调函数实现自定义排序

 1 int main()
 2 {
 3     std::list<int> list1{22,33,123,423,35,564,65,354};
 4     list1.sort();// std::less;
 5     DisplayContents(list1);
 6 
 7     list1.sort([](int& a,int& b){ return (a>b);});
 8     DisplayContents(list1);
 9     return 0;
10 }

待续补充forword_list...................

C++ STL之LIST详解A

推荐阅读