目录
介绍
常用函数
函数使用举例
创建list并赋值
遍历和查找
删除元素
清空列表
向list中插入元素
使用assign给容器增加新元素
两个list交换
使用resize改变list的大小。
使用splice函数操作list
删除重复的元素
合并list
排序
list和vector的区别
介绍
list是线性双向链表结构，它的数据由若干个节点构成，每一个节点都包括一个信息块（即实际存储的数据）、一个前驱指针和一个后驱指针。它无需分配指定的内存大小且可以任意伸缩，这是因为它存储在非连续的内存空间中，并且由指针将有序的元素链接起来。由于其结构的原因，list 随机检索的性能非常的不好，因为它不像vector 那样直接找到元素的地址，而是要从头一个一个的顺序查找，这样目标元素越靠后，它的检索时间就越长。检索时间与目标元素的位置成正比。虽然随机检索的速度不够快，但是它可以迅速地在任何节点进行插入和删除操作。因为list 的每个节点保存着它在链表中的位置，插入或删除一个元素仅对最多三个元素有所影响，不像vector 会对操作点之后的所有元素的存储地址都有所影响，这一点是vector 不可比拟的。
t 的特点：
(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
