C++ list总结

系统管理员 2023-03-03 15:28 18阅读 0赞

**目录**

介绍

常用函数

函数使用举例

创建list并赋值

遍历和查找

删除元素

清空列表

向list中插入元素

使用assign给容器增加新元素

两个list交换

使用resize改变list的大小。

使用splice函数操作list

删除重复的元素

合并list

排序

list和vector的区别

--------------------

# **介绍   **  #

list是线性双向链表结构，它的数据由若干个节点构成，每一个节点都包括一个**信息块**（即实际存储的数据）、一个**前驱指针**和一个**后驱指针**。它无需分配指定的内存大小且可以任意伸缩，这是因为它存储在非连续的内存空间中，并且由指针将有序的元素链接起来。由于其结构的原因，list 随机检索的性能非常的不好，因为它不像vector 那样直接找到元素的地址，而是要从头一个一个的顺序查找，这样目标元素越靠后，它的检索时间就越长。检索时间与目标元素的位置成正比。虽然随机检索的速度不够快，但是它可以迅速地在任何节点进行插入和删除操作。因为list 的每个节点保存着它在链表中的位置，插入或删除一个元素仅对最多三个元素有所影响，不像vector 会对操作点之后的所有元素的存储地址都有所影响，这一点是vector 不可比拟的。

![https://images2015.cnblogs.com/blog/849009/201602/849009-20160203142350538-1403083351.png][https_images2015.cnblogs.com_blog_849009_201602_849009-20160203142350538-1403083351.png]

***list ******的特点***：

(1) 不使用连续的内存空间，这样可以随意地进行动态操作；  
(2) 可以在内部任何位置快速地插入或删除，当然也可以在两端进行push 和pop 。  
(3) 不能进行内部的随机访问，即不支持\[ \] 操作符和vector.at() ；  
(4) 相对于verctor 占用更多的内存。

# **常用函数** #

<table> 
 <tbody> 
 <tr> 
 <td colspan="2" style="vertical-align:top;width:414.3pt;"> List的构造函数和析构函数 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.1pt;"> list&lt;Elem&gt; c </td> 
 <td style="vertical-align:top;width:308.2pt;"> 产生一个空list，其中没有任何元素 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.1pt;"> list&lt;Elem&gt; c1(c2) </td> 
 <td style="vertical-align:top;width:308.2pt;"> 产生另一个同型list的副本(所有的元素都被拷贝) </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.1pt;"> list&lt;Elem&gt; c(n) </td> 
 <td style="vertical-align:top;width:308.7pt;"> 利用元素的default构造函数产生一个大小为n的list </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.1pt;"> list&lt;Elem&gt; c(n,elem) </td> 
 <td style="vertical-align:top;width:308.7pt;"> 产生一个大小为n的list，每个元素值都是elem </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.1pt;"> list&lt;Elem&gt; c(beg, end) </td> 
 <td style="vertical-align:top;width:308.7pt;"> 产生一个list，以区间[beg, end)做为元素初值 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.1pt;"> c.~list&lt;Elem&gt;()&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </td> 
 <td style="vertical-align:top;width:308.7pt;"> 销毁所有元素，并释放内存 </td> 
 </tr> 
 <tr> 
 <td colspan="2" style="vertical-align:top;width:414.8pt;"> list的非变动性操作 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.1pt;"> size() </td> 
 <td style="vertical-align:top;width:308.7pt;"> 返回容器的大小 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.1pt;"> empty()&nbsp;&nbsp;&nbsp; </td> 
 <td style="vertical-align:top;width:308.7pt;"> 判断容器是否为空,等价于size()==0,但可能更快 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.1pt;"> max_size() </td> 
 <td style="vertical-align:top;width:308.7pt;"> 返回容器最大的可以存储的元素 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.1pt;"> reserve() </td> 
 <td style="vertical-align:top;width:308.7pt;"> 如果容量不足，扩大之 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.1pt;"> c1 == c2 </td> 
 <td style="vertical-align:top;width:308.7pt;"> 判断c1 是否等于c2 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.1pt;"> c1 != c2 </td> 
 <td style="vertical-align:top;width:308.7pt;"> 判断c1是否不等于c2 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.1pt;"> c1 &lt; c2 </td> 
 <td style="vertical-align:top;width:308.7pt;"> 判断c1 是否小于c2 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.1pt;"> c1 &gt; c2 </td> 
 <td style="vertical-align:top;width:308.7pt;"> 判断c1 是否大于c2 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.1pt;"> c1 &lt;= c2&nbsp;&nbsp; </td> 
 <td style="vertical-align:top;width:308.7pt;"> 判断c1是否小于等于c2 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.1pt;"> c1 &gt;= c2&nbsp;&nbsp; </td> 
 <td style="vertical-align:top;width:308.7pt;"> 判断c1是否大于等于c2 </td> 
 </tr> 
 <tr> 
 <td colspan="2" style="vertical-align:top;width:414.8pt;"> list的赋值操作 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.1pt;"> c1 = c2&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </td> 
 <td style="vertical-align:top;width:308.7pt;"> 将c2的全部元素赋值给c1 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.1pt;"> assign(n, elem) </td> 
 <td style="vertical-align:top;width:308.7pt;"> 复制n个elem，复制给c </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.1pt;"> assign(beg, end)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </td> 
 <td style="vertical-align:top;width:308.7pt;"> 将区间[beg;end）内的元素赋值给c </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.1pt;"> c1.swap(c2) </td> 
 <td style="vertical-align:top;width:308.7pt;"> 将c1和c2元素互换 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.1pt;"> swap(c1,c2) </td> 
 <td style="vertical-align:top;width:308.7pt;"> 同上，此为全局函数 </td> 
 </tr> 
 <tr> 
 <td colspan="2" style="vertical-align:top;width:414.3pt;"> 元素访问 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.05pt;"> front&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </td> 
 <td style="vertical-align:top;width:308.25pt;"> 返回第一个元素，不检查元素存在与否 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.05pt;"> back </td> 
 <td style="vertical-align:top;width:308.25pt;"> 返回最后一个元素，不检查元素存在与否 </td> 
 </tr> 
 <tr> 
 <td colspan="2" style="vertical-align:top;width:414.3pt;"> 迭代器相关函数 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.05pt;"> begin() </td> 
 <td style="vertical-align:top;width:308.25pt;"> 返回一个双向迭代器，指向第一个元素 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.05pt;"> end() </td> 
 <td style="vertical-align:top;width:308.25pt;"> 返回一个双向迭代器，指向最后一个元素的下一个位置 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.05pt;"> rbegin()&nbsp;&nbsp;&nbsp; </td> 
 <td style="vertical-align:top;width:308.25pt;"> 返回一个逆向迭代器，指向逆向迭代的第一个元素 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.05pt;"> end() </td> 
 <td style="vertical-align:top;width:308.25pt;"> 返回一个逆向迭代器，指向逆向迭代的最后一个元素的下一个位置 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.05pt;"> list安插、移除操作函数 </td> 
 <td style="vertical-align:top;width:308.25pt;"> &nbsp; </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.05pt;"> insert(pos, elem) </td> 
 <td style="vertical-align:top;width:308.25pt;"> 在迭代器pos所指位置上安插一个elem副本，并返回新元素的位置 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.05pt;"> insert(pos,n,elem) </td> 
 <td style="vertical-align:top;width:308.25pt;"> 在pos位置上插入n个elem副本，无返回值 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.05pt;"> insert(pos,beg,end) </td> 
 <td style="vertical-align:top;width:308.25pt;"> 在pos位置上插入区间[beg,end)内的所有元素的副本，没有返回值 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.05pt;"> push_back(elem) </td> 
 <td style="vertical-align:top;width:308.25pt;"> 在尾部添加一个elem副本 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.05pt;"> pop_back() </td> 
 <td style="vertical-align:top;width:308.25pt;"> 移除最后一个元素，无返回值 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.05pt;"> push_front()&nbsp;&nbsp;&nbsp;&nbsp; </td> 
 <td style="vertical-align:top;width:308.25pt;"> 在头部添加一个elem副本 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.05pt;"> pop_front()&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </td> 
 <td style="vertical-align:top;width:308.25pt;"> 移除第一个元素，但不返回 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.05pt;"> remove(val) </td> 
 <td style="vertical-align:top;width:308.25pt;"> 移除所有其值为val的元素 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.05pt;"> remove_if() </td> 
 <td style="vertical-align:top;width:308.25pt;"> 删除一个链表中所有满足条件的元素 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.05pt;"> erase(pos) </td> 
 <td style="vertical-align:top;width:308.25pt;"> 移除pos位置上的元素，返回下一个元素的位置 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.05pt;"> erase(beg, end) </td> 
 <td style="vertical-align:top;width:308.25pt;"> 移除[beg, end)区间内的所有元素，返回下一个元素的位置 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.05pt;"> resize(num) </td> 
 <td style="vertical-align:top;width:308.25pt;"> 将元素数量改为num(如果size()变大了，多出来的新元素都需以default构造函数完成) </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.05pt;"> resize(num,elem)&nbsp;&nbsp;&nbsp; </td> 
 <td style="vertical-align:top;width:308.25pt;"> 将元素数量改为num(如果size()变大了，多出来的新元素都elem的副本) </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.05pt;"> clear()&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </td> 
 <td style="vertical-align:top;width:308.25pt;"> 移除所有元素，将容器清空 </td> 
 </tr> 
 <tr> 
 <td colspan="2" style="vertical-align:top;width:414.3pt;"> 备注：安插和移除元素，都会使“作用点”之后的各个元素的iterator等失效，若发生内存重新分配，该容器身上的所有iterator等都会失效 </td> 
 </tr> 
 <tr> 
 <td colspan="2" style="vertical-align:top;width:414.3pt;"> List的特殊变动性操作 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.1pt;"> unique() </td> 
 <td style="vertical-align:top;width:308.2pt;"> 如果存在若干相邻而数值相等的元素，就移除重复元素， 之留下一个&nbsp;&nbsp;&nbsp;&nbsp; </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.1pt;"> unique(op)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </td> 
 <td style="vertical-align:top;width:308.2pt;"> 如果存在若干相邻元素，都使op()的结果为ture， 则移除重复元素，只留下一个。 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.1pt;"> c1.splice(pos, c2) </td> 
 <td style="vertical-align:top;width:308.2pt;"> 将c2内的所有元素转移到c1之内，迭代器pos之前 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.1pt;"> c1.splice(pos, c2, c2pos)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </td> 
 <td style="vertical-align:top;width:308.2pt;"> 将c2内的c2pos所指元素转移到c1之内的pos所指位置上 (c1,c2可相同) </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.1pt;"> c1.splice(pos, c2,c2beg，c2end)&nbsp;&nbsp; </td> 
 <td style="vertical-align:top;width:308.2pt;"> 将c2内的[c2beg，c2end）区间内所有元素转移到 c1内的pos之前(c1,c2可相同) </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.1pt;"> sort() </td> 
 <td style="vertical-align:top;width:308.2pt;"> 以operator&lt;为准则，对所有元素排序 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.1pt;"> sort(op) </td> 
 <td style="vertical-align:top;width:308.2pt;"> 以op()为准则，对所有元素排序 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.1pt;"> c1.merge(c2)&nbsp;&nbsp; </td> 
 <td style="vertical-align:top;width:308.2pt;"> 假设c1和c2容器都包含已序(相同的排序方式)元素，将c2的全部元素转移到c1，并保证合并后的list还是已序。 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.1pt;"> c1.merge(c2，op) </td> 
 <td style="vertical-align:top;width:308.2pt;"> 假设c1和c2容器都包含op()原则下的已序(相同的排序方式)元素，将c2的全部元素转移到c1，并保证合并后的list在op（）原则仍是已序。 &nbsp; </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.1pt;"> reverse() </td> 
 <td style="vertical-align:top;width:308.2pt;"> 将所有元素反序 </td> 
 </tr> 
 </tbody> 
</table>

# **函数使用举例** #

## **创建list并赋值** ##

\#include <iostream>

\#include <list>

using namespace std;

int main() \{

//第一种，通过构造函数

int myints\[\] = \{ 44,77,22,11,12 \};

list<int> mylist1(myints, myints + 5);

list<int> mylist2(2, 100);         // 2个值为100的元素

//第二种，用push\_back，或push\_front

for (int i = 1; i <= 5; ++i) mylist1.push\_back(i);

mylist2.push\_front(20);

mylist2.push\_front(30);

//第三种,用assign

list<int> first;

list<int> second;

first.assign(7, 10);                       // 给first添加7个值为10的元素

second.assign(first.begin(), first.end()); // 复制first给second

int myints1\[\] = \{ 32, 8, 4 \};

first.assign(myints1, myints1 + 3);         // 将数组myints的内容添加给first

return 0;

## **遍历和查找** ##

\#include <iostream>

\#include <list>

using namespace std;

int main() \{

//第一种，通过构造函数

int myints\[\] = \{ 44,77,22,11,12\};

list<int> myList(myints, myints + 5);

cout << "mylist contains:";

//遍历

for (list<int>::iterator it = myList.begin(); it != myList.end(); \++it)

cout << " " << \*it;

cout << "\\n";

//查找

for (list<int>::iterator it = myList.begin(); it != myList.end(); \++it)

if (\*it == 22)

cout << "存在22";

cout << "\\n";

//追加

for (int i = 1; i <= 5; ++i)

myList.push\_back(i);

//逆序遍历

for (list<int>::reverse\_iterator rit = myList.rbegin(); rit != myList.rend(); \++rit)

cout << ' ' << \*rit;

return 0;

## **删除元素** ##

// 创建实例以及赋值

\#include <iostream>

\#include <list>

using namespace std;

bool single\_digit(const int& value) \{ return (value < 20); \}

struct is\_odd \{

//重载操作符 ()

bool operator() (const int& value) \{ return (value % 2) == 1; \}

\};

int main() \{

//第一种，通过构造函数

int myints\[\] = \{ 44,77,22,11,12 \};

list<int> myList(myints, myints + 5);

cout << "mylist contains:";

//遍历

for (list<int>::iterator it = myList.begin(); it != myList.end(); \++it)

cout << " " << \*it;

cout << "\\n";

//remove和remove\_if删除元素

myList.remove(22);

myList.remove\_if(single\_digit);

myList.remove\_if(is\_odd());

//遍历

for (list<int>::iterator it = myList.begin(); it != myList.end(); it\++)

cout << " " << \*it;

cout << "\\n";

//追加

myList.push\_back(22);

for (list<int>::iterator it = myList.begin(); it != myList.end(); it\++) \{

cout << " " << \*it;

cout << "\\n";

//遍历删除，这是一种错误的写法。

/\*for (auto it = myList.begin(); it != myList.end(); it++)

if (\*it == 11) \{

myList.erase(it);

\}\*/

//第一种写法

for (auto it = myList.begin(); it != myList.end();)

if (\*it == 22) \{

myList.erase(it\++);

else

cout << " " << \*it;

it\++;

//第二种写法

for (auto it = myList.begin(); it != myList.end();)

if (\*it == 22) \{

it=myList.erase(it);

else

cout << " " << \*it;

it\++;

return 0;

## **清空列表** ##

\#include <iostream>

\#include <list>

using namespace std;

int main() \{

list<int> mylist;

list<int>::iterator it;

mylist.push\_back(10);

mylist.push\_back(20);

mylist.push\_back(30);

cout << "mylist contains:";

for (it = mylist.begin(); it != mylist.end(); \++it)

cout << ' ' << \*it;

cout << '\\n';

mylist.clear();

mylist.push\_back(2121);

mylist.push\_back(3232);

cout << "mylist contains:";

for (it = mylist.begin(); it != mylist.end(); \++it)

cout << ' ' << \*it;

cout << '\\n';

return 0;

## **向list中插入元素** ##

\#include <iostream>

\#include <list>

\#include <vector>

using namespace std;

int main() \{

list<int> mylist;

list<int>::iterator it;

// 初始化

for (int i = 1; i <= 5; ++i) mylist.push\_back(i); // 1 2 3 4 5

it = mylist.begin();

\++it;       // 迭代器it现在指向数字2                      ^

//在i0t指向的位置出插入元素10

mylist.insert(it, 10);  // 1 10 2 3 4 5

// "it" 仍然指向数字2                                   ^

//在it指向的位置出插入两个元素20

mylist.insert(it, 2, 20); // 1 10 20 20 2 3 4 5

\--it;       // 现在it指向数字20                             ^

vector<int> myvector(2, 30); //创建vector容器，并初始化为含有2个值为30的元素

//将vector容器的值插入list中

mylist.insert(it, myvector.begin(), myvector.end());

// 1 10 20 30 30 20 2 3 4 5

//it仍然指向数字20                            //               ^

cout << "mylist contains:";

for (it = mylist.begin(); it != mylist.end(); \++it)

cout << ' ' << \*it;

cout << '\\n';

return 0;

## **使用assign给容器增加新元素** ##

\#include <iostream>

\#include <list>

using namespace std;

int main() \{

list<int> first;

list<int> second;

first.assign(7, 10);// 给first添加7个值为10的元素

second.assign(first.begin(), first.end()); // 复制first给second

int myints\[\] = \{ 22, 33, 44 \};

first.assign(myints, myints + 3);  // 将数组myints的内容添加给first

cout << "Size of first: " << int(first.size()) << '\\n';

cout << "Size of second: " << int(second.size()) << '\\n';

return 0;

## **两个list交换** ##

// swap lists

\#include <iostream>

\#include <list>

using namespace std;

int main() \{

list<int> first(3, 100);   // 三个值为100的元素

list<int> second(5, 200);  // 五个值为200的元素

first.swap(second);

cout << "first contains:";

for (list<int>::iterator it = first.begin(); it != first.end(); it\++)

cout << ' ' << \*it;

cout << '\\n';

cout << "second contains:";

for (list<int>::iterator it = second.begin(); it != second.end(); it\++)

cout << ' ' << \*it;

cout << '\\n';

return 0;

## **使用resize改变list的大小。** ##

// resizing list

\#include <iostream>

\#include <list>

using namespace std;

int main() \{

list<int> mylist;

// 初始化

for (int i = 1; i < 10; ++i) mylist.push\_back(i);//list为0 1 2 3 4 5 6 7 8 9

mylist.resize(5);//list的长度变为5，元素为：0 1 2 3 4

mylist.resize(8, 100);//list的长度变为8，超过5的部分变为100，元素为：0 1 2 3 4 100 100 100

mylist.resize(12);//list的长度变为12，超过5的部分赋默认值0，元素为：0 1 2 3 4 100 100 100 0 0 0 0

cout << "mylist contains:";

for (list<int>::iterator it = mylist.begin(); it != mylist.end(); \++it)

cout << ' ' << \*it;

cout << '\\n';

return 0;

## **使用splice函数操作list** ##

// splicing lists

\#include <iostream>

\#include <list>

using namespace std;

int main() \{

list<int> mylist1, mylist2;

list<int>::iterator it;

// 初始化

for (int i = 1; i <= 10; ++i)

mylist1.push\_back(i);      // mylist1: 1 2 3 4 5 6 7 8 9

for (int i = 1; i <= 3; ++i)

mylist2.push\_back(i \* 10);   // mylist2: 10 20 30

it = mylist1.begin();

\++it;                         // 指向数字2

mylist1.splice(it, mylist2); // mylist1: 1 10 20 30 2 3 4

// mylist2 (empty)

// "it" 仍然指向数字2

mylist2.splice(mylist2.begin(), mylist1, it);

// mylist1: 1 10 20 30 3 4

// mylist2: 2

// "it" 此时已经无效了

it = mylist1.begin();

advance(it, 3);           // "it" 指向数字30

mylist1.splice(mylist1.begin(), mylist1, it, mylist1.end());

// mylist1: 30 3 4 1 10 20

cout << "mylist1 contains:";

for (it = mylist1.begin(); it != mylist1.end(); \++it)

cout << ' ' << \*it;

cout << '\\n';

cout << "mylist2 contains:";

for (it = mylist2.begin(); it != mylist2.end(); \++it)

cout << ' ' << \*it;

cout << '\\n';

return 0;

## **删除重复的元素** ##

// list::unique

\#include <iostream>

\#include <cmath>

\#include <list>

using namespace std;

// a binary predicate implemented as a function:

bool same\_integral\_part(double first, double second) \{ return (int(first) == int(second)); \}

// a binary predicate implemented as a class:

struct is\_near \{

bool operator() (double first, double second) \{ return (fabs(first \- second) < 5.0); \}

\};

int main() \{

double mydoubles\[\] = \{ 12.15, 2.72, 73.0, 12.77, 3.14,

12.77, 73.35, 72.25, 15.3, 72.25 \};

list<double> mylist(mydoubles, mydoubles + 10);

cout << "mylist contains:";

for (list<double>::iterator it = mylist.begin(); it != mylist.end(); \++it)

cout << ' ' << \*it;

cout << '\\n';

mylist.unique();

cout << "mylist contains:";

for (list<double>::iterator it = mylist.begin(); it != mylist.end(); \++it)

cout << ' ' << \*it;

cout << '\\n';

mylist.sort();             //  2.72,  3.14, 12.15, 12.77, 12.77,

// 15.3,  72.25, 72.25, 73.0,  73.35

mylist.unique();           //  2.72,  3.14, 12.15, 12.77

// 15.3,  72.25, 73.0,  73.35

cout << "mylist contains:";

for (list<double>::iterator it = mylist.begin(); it != mylist.end(); \++it)

cout << ' ' << \*it;

cout << '\\n';

mylist.unique(same\_integral\_part);  //  2.72,  3.14, 12.15                                 // 15.3,  72.25, 73.0

cout << "mylist contains:";

for (list<double>::iterator it = mylist.begin(); it != mylist.end(); \++it)

cout << ' ' << \*it;

cout << '\\n';

mylist.unique(is\_near());           //  2.72, 12.15, 72.25

cout << "mylist contains:";

for (list<double>::iterator it = mylist.begin(); it != mylist.end(); \++it)

cout << ' ' << \*it;

cout << '\\n';

return 0;

## **合并list** ##

\#include <iostream>

\#include <list>

using namespace std;

bool mycomparison(double first, double second) \{ return ((first) < (second)); \}

int main() \{

list<double> first, second;

first.push\_back(3.1);

first.push\_back(2.2);

first.push\_back(2.9);

second.push\_back(3.7);

second.push\_back(7.1);

second.push\_back(1.4);

first.sort();

second.sort();

first.merge(second);

cout << "first contains:";

for (list<double>::iterator it = first.begin(); it != first.end(); \++it)

cout << ' ' << \*it;

cout << '\\n';

// (second 现在为空)

second.push\_back(1.1);

second.push\_back(2.1);

second.push\_back(2.5);

first.merge(second, mycomparison);

cout << "first contains:";

for (list<double>::iterator it = first.begin(); it != first.end(); it\++)

cout << ' ' << \*it;

cout << '\\n';

return 0;

## **排序** ##

// list::sort

\#include <iostream>

\#include <list>

\#include <string>

\#include <cctype>

using namespace std;

// comparison, not case sensitive.

bool compare\_nocase(const string& first, const string& second) \{

unsigned int i = 0;

while ((i < first.length()) && (i < second.length())) \{

//将大写字母转为小写字母

if (tolower(first\[i\]) < tolower(second\[i\])) return true;

else if (tolower(first\[i\]) > tolower(second\[i\])) return false;

++i;

return (first.length() < second.length());

int main() \{

list<string> mylist;

list<string>::iterator it;

mylist.push\_back("one");

mylist.push\_back("two");

mylist.push\_back("Three");

mylist.push\_back("Four");

mylist.push\_back("Five");

mylist.push\_back("Six");

mylist.sort();

cout << "mylist contains:";

for (it = mylist.begin(); it != mylist.end(); \++it)

cout << ' ' << \*it;

cout << '\\n';

mylist.sort(compare\_nocase);

cout << "mylist contains:";

for (it = mylist.begin(); it != mylist.end(); \++it)

cout << ' ' << \*it;

cout << '\\n';

return 0;

# **list和vector的区别** #

1.  **vector****数据结构**  
    vector和数组类似，拥有一段连续的内存空间，并且起始地址不变。  
    因此能高效的进行随机存取，时间复杂度为o(1);  
    但因为内存空间是连续的，所以在进行插入和删除操作时，会造成内存块的拷贝，时间复杂度为o(n)。  
    另外，当数组中内存空间不够时，会重新申请一块内存空间并进行内存拷贝。

vector拥有一段连续的内存空间，能很好的支持随机存取， 
因此vector<int>::iterator支持“+”，“+=”，“<”等操作符。

1.  **list****数据结构**  
    list是由双向链表实现的，因此内存空间是不连续的。  
    只能通过指针访问数据，所以list的随机存取非常没有效率，时间复杂度为o(n);  
    但由于链表的特点，能高效地进行插入和删除。

list的内存空间可以是不连续，它不支持随机访问， 
因此list<int>::iterator则不支持“+”、“+=”、“<”等

vector<int>::iterator和list<int>::iterator都重载了“++”运算符。

总之，如果需要高效的随机存取，而不在乎插入和删除的效率，使用vector;  
如果需要大量的插入和删除，而不关心随机存取，则应使用list。

参考：

1、[https://www.cnblogs.com/wj0816/p/6568630.html][https_www.cnblogs.com_wj0816_p_6568630.html]

[https_images2015.cnblogs.com_blog_849009_201602_849009-20160203142350538-1403083351.png]: /images/20230208/a22221323ef94257970cdb77146d50ca.png
[https_www.cnblogs.com_wj0816_p_6568630.html]: https://www.cnblogs.com/wj0816/p/6568630.html