目录
C++:list的介绍及使用
list的介绍
list的使用
list的定义方式
list的插入和删除
push_front 和 pop_front
push_back 和 pop_back
insert和erase
list的迭代器使用
begin和end
rbegin和rend
list的迭代器失效问题
list的元素获取
front和back
list的大小控制
size
resize
empty
clear
list的操作函数
sort
splice
remove
remove_if
unique
merge
reverse
assign
swap
list与vector的对比
C++:list的介绍及使用
list的介绍
1.list是一种可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代.
2.list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立结点当中,在结点中通过指针指向其前一个元素和后一个元素.
3.list与forward_list非常相似,最主要的不同在于forward_list是单链表,只能进行单方向迭代.
4.与其他容器相比,list通常在任意位置进行插入、删除元素的执行效率更高.
5.list和forward_list最大的缺陷是不支持在任意位置的随机访问,其次,list还需要一些额外的空间,以保存每个结点之间的关联信息(对于存储的类型较小元素来说这可能是一个重要的因素)
list的使用
list的定义方式
void TestList1()
{
list<int> lt1;
list<int> lt2(4, 100);
list<int> lt3(lt2.begin(), lt2.end());
list<int> lt4(lt3);
// 以数组为迭代器区间构造l5
int arr[] = { 16,2,77,29 };
list<int> lt5(arr, arr + sizeof(arr) / sizeof(int));
// 列表格式初始化C++11
list<int> lt6{ 1,2,3,4,5 };
// 用迭代器方式打印l5中的元素
list<int>::iterator it = lt5.begin();
while (it != lt5.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
list的插入和删除
push_front 和 pop_front
void PrintList(const list<int>& lt)
{
list<int>::const_iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
//*it = 10; 编译不通过
++it;
}
cout << endl;
}
void TestList2()
{
int arr[] = { 1, 2, 3 };
list<int> lt(arr, arr + sizeof(arr) / sizeof(arr[0]));
lt.push_front(0);
PrintList(lt);
lt.pop_front();
PrintList(lt);
}
int main()
{
TestList2();
return 0;
}
push_back 和 pop_back
void PrintList(const list<int>& lt)
{
list<int>::const_iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
void TestList3()
{
int arr[] = { 1, 2, 3 };
list<int> lt(arr, arr + sizeof(arr) / sizeof(arr[0]));
lt.push_back(4);
PrintList(lt);
lt.pop_back();
PrintList(lt);
}
insert和erase
void TestList4()
{
int arr[] = { 1, 2, 3 };
list<int> lt(arr, arr + sizeof(arr) / sizeof(arr[0]));
list<int>::iterator pos = ++lt.begin();
cout << *pos << endl;
lt.insert(pos, 4);
PrintList(lt);
lt.insert(pos, 5, 5);
PrintList(lt);
vector<int> v{ 7, 8, 9 };
lt.insert(pos, v.begin(), v.end());
PrintList(lt);
lt.erase(pos);
PrintList(lt);
lt.erase(lt.begin(), lt.end());
PrintList(lt);
}
list的迭代器使用
begin和end
void TestList5()
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> lt(arr, arr + sizeof(arr) / sizeof(arr[0]));
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
rbegin和rend
void TestList6()
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> lt(arr, arr + sizeof(arr) / sizeof(arr[0]));
list<int>::iterator it = lt.begin();
list<int>::reverse_iterator rit = lt.rbegin();
while (rit != lt.rend())
{
cout << *rit << " ";
++rit;
}
cout << endl;
}
list的迭代器失效问题
前面说过,此处大家可将迭代器暂时理解成类似于指针,迭代器失效即迭代器所指向的结点失效,即该结点被删除了,因为list的底层结构为带哨兵位的双向循环链表,因此在list中进行插入时是不会导致list的迭代器失效的,只有在删除时才会失效,并且失效的只是指向被删除节点的迭代器,其他迭代器不会受到影响.
list的元素获取
front和back
void TestList9()
{
list<int> lt;
lt.push_back(0);
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
cout << lt.front() << endl;
cout << lt.back() << endl;
}
list的大小控制
size
void TestList10()
{
list<int> lt;
lt.push_back(0);
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
cout << lt.size() << endl;
}
int main()
{
TestList10();
return 0;
}
resize
resize的两种情况:
1.当所给值大于当前的size时,将size扩大到该值,扩大的数据为第二个所给值,若未给出,则默认为容器所存储类型的默认构造函数所构造出来的值.
2.当所给值小于当前的size时,将size缩小到该值.
void TestList11()
{
list<int> lt(5, 3);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
lt.resize(7, 6);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
lt.resize(2);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
}
empty
void TestList12()
{
list<int> lt;
cout << lt.empty() << endl;
}
clear
void TestList13()
{
list<int> lt(5, 2);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
cout << lt.size() << endl;
lt.clear();
for (auto e : lt)
{
cout << e << " ";
}
cout << lt.size() << endl;
}
list的操作函数
sort
void TestOP1()
{
srand(time(0));
const int N = 1000000;
vector<int> v;
v.reserve(N);
list<int> lt1;
for (int i = 0; i < N; ++i)
{
int e = rand();
v.push_back(e);
lt1.push_back(e);
}
int begin1 = clock();
sort(v.begin(), v.end());
int end1 = clock();
int begin2 = clock();
lt1.sort();
int end2 = clock();
printf("vector sort:%d\n", end1 - begin1);
printf("list sort:%d\n", end2 - begin2);
}
void TestOP2()
{
srand(time(0));
const int N = 100000;
vector<int> v;
v.reserve(N);
list<int> lt1;
list<int> lt2;
for (int i = 0; i < N; ++i)
{
auto e = rand();
lt1.push_back(e);
lt2.push_back(e);
}
int begin1 = clock();
for (auto e : lt1)
{
v.push_back(e);
}
sort(v.begin(), v.end());
size_t i = 0;
for (auto& e : lt1)
{
e = v[i++];
}
int end1 = clock();
int begin2 = clock();
lt2.sort();
int end2 = clock();
printf("copy vector sort:%d\n", end1 - begin1);
printf("list sort:%d\n", end2 - begin2);
}
splice
splice函数用于两个list容器之间的拼接,其有三种拼接方式:
1.将整个容器拼接到另一个容器的指定迭代器位置
2.将容器当中的某一个数据拼接到另一个容器的指定迭代器位置
3.将容器指定迭代器区间的数据拼接到另一个容器的指定迭代器位置
void TestList14()
{
list<int> lt1(4, 2);
list<int> lt2(4, 6);
lt1.splice(lt1.begin(), lt2);
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
list<int> lt3(4, 2);
list<int> lt4(4, 6);
lt3.splice(lt3.begin(), lt4, lt4.begin());
for (auto e : lt3)
{
cout << e << " ";
}
cout << endl;
list<int> lt5(4, 2);
list<int> lt6(4, 6);
lt5.splice(lt5.begin(), lt6, lt6.begin(), lt6.end());
for (auto e : lt5)
{
cout << e << " ";
}
cout << endl;
}
注意:容器当中被拼接到另一个容器的数据在原容器当中就不存在了,实际上就是将链表中的指定结点拼接到了另一个容器中
remove
void TestList15()
{
list<int> lt;
lt.push_back(1);
lt.push_back(4);
lt.push_back(3);
lt.push_back(3);
lt.push_back(2);
lt.push_back(3);
lt.push_back(2);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
lt.remove(3);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
}
remove_if
bool Odd(const int& val)
{
return val % 2 == 0;
}
void TestList16()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
lt.push_back(6);
lt.push_back(7);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
lt.remove_if(Odd);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
}
unique
void TestList17()
{
list<int> lt;
lt.push_back(1);
lt.push_back(4);
lt.push_back(3);
lt.push_back(3);
lt.push_back(2);
lt.push_back(2);
lt.push_back(3);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
lt.sort();
lt.unique();
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
}
merge
void TestList18()
{
list<int> lt1;
lt1.push_back(3);
lt1.push_back(8);
lt1.push_back(1);
list<int> lt2;
lt2.push_back(6);
lt2.push_back(2);
lt2.push_back(9);
lt2.push_back(5);
lt1.sort();
lt2.sort();
lt1.merge(lt2);
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
}
reverse
void TestList19()
{
list<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(3);
lt1.push_back(4);
lt1.push_back(5);
lt1.reverse();
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
}
assign
void TestList20()
{
list<char> lt(3, 'a');
lt.assign(3, 'b');
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
string s("hello world");
lt.assign(s.begin(), s.end());
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
}
文章来源:https://www.toymoban.com/news/detail-739744.html
swap
void TestList8()
{
int arr[] = { 1, 2, 3 };
list<int> lt1(arr, arr + sizeof(arr) / sizeof(arr[0]));
list<int> lt2{ 4,5,6 };
lt1.swap(lt2);
PrintList(lt1);
PrintList(lt2);
}
文章来源地址https://www.toymoban.com/news/detail-739744.html
list与vector的对比:
vector | list | |
底层结构 | 动态顺序表,一段连续空间 | 带头结点的双向循环链表 |
随机访问 | 支持随机访问,访问某个元素效率O(1) | 不支持随机访问,访问某个元素效率O(N) |
插入和删除 | 头部和中间插入和删除效率低,需要搬移元素,时间复杂度为O(N),插入时可能需要增容,增容:开辟新空间,拷贝元素,释放旧空间,导致效率更低 | 任意位置插入和删除效率高,不需要搬移元素,时间复杂度为O(1) |
迭代器 | SGI版本下为原生态指针 | 对结点指针进行封装 |
迭代器失效 | 在插入元素时,要给迭代器重新赋值,因为插入元素有可能会导致重新扩容,致使原来迭代器失效,删除时,当前迭代器需要重新赋值否则一定会失效 | 插入元素不会导致迭代器失效,删除元素时,只会导致当前迭代器失效,其他迭代器不受影响 |
空间利用率 | 底层为连续空间,不容易造成内存碎片,空间利用率高,缓存利用率高 | 底层结点动态开辟,小结点容易造成内存碎片,空间利用率低,缓存利用率低,容易造成缓存污染 |
使用场景 | 需要高效存储,支持随机访问,插入删除多为尾插尾删 | 大量头部中部插入删除 |
到了这里,关于[C++]list的介绍及使用的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!