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

list 的特点：

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

常用函数

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

函数使用举例

创建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的区别

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

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

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

文章来源: wanghao.blog.csdn.net，作者：AI浩，版权归原作者所有，如需转载，请联系作者。

原文链接：wanghao.blog.csdn.net/article/details/107721284

点赞
收藏
关注作者

0/1000

抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认取消

加入云驻计划，成为创作者

华为云周边好礼
免费体验产品
特殊身份标识
线下官方门票
内部专家零距离
与10000+优质创作者共同成长

立即加入

C++ list总结

介绍

常用函数

函数使用举例

创建list并赋值

遍历和查找

删除元素

清空列表

向list中插入元素

使用assign给容器增加新元素

两个list交换

使用resize改变list的大小。

使用splice函数操作list

删除重复的元素

合并list

排序

list和vector的区别

全部回复

设置昵称

关于作者

目录

加入云驻计划，成为创作者

推荐阅读

相关产品