介绍

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

list 的特点：

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

常用函数

函数使用举例

创建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;

}

修改

#include <iostream>

#include <list>

using namespace std;

int main()

{

list<string> strList;

strList.clear();

strList.push_back("Hello");

strList.push_back(" ");

strList.push_back("World");

strList.push_back("!");

list<string>::iterator iter = strList.begin();

for(;iter != strList.end();iter++)

{

std::cout << *iter;

if(*iter == "World")

{

*iter = "csdn";

}

}

std::cout << std::endl;

std::cout << "************changed************" << std::endl;

iter = strList.begin();

while (iter != strList.end()) {

std::cout << *iter;

++iter;

}

std::cout << std::endl;

return 0;

}

list和vector的区别

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

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

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

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

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

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

参考：

1、