写在前面：大家好！我是【AI 菌】，一枚爱弹吉他的程序员。我
热爱AI、热爱分享、热爱开源！ 这博客是我对学习的一点总结与思考。如果您也对深度学习、机器视觉、算法、C++、Python感兴趣，可以关注我的动态，我们一起学习，一起进步~
我的博客地址为：【AI 菌】的博客
前言：
这一次，我整理了C++中 list类 的整套用法，结合数据结构链表：面试官：线性表、顺序表、链表的区别是什么？的知识学起来会更好。
相关文章：【C++21天养成计划】
1. List 类
list 是顺序容器，它允许在序列中任意位置进行常量时间的插入和擦除操作，并在两个方向上进行迭代。
list 容器是双向链表；双向链表可以将它们所包含的每个元素存储在不同的、不相关的存储位置。每个元素通过与前面元素链接和后面元素链接关联，在内部保持顺序。
它与 forward_list 非常相似：最大的不同在于 forward_list 是单向链表。单向链表仅能向前迭代，因此它更小更高效。
与其他基本标准顺序容器（array、vector、queue）相比较，list 通常在插入、删除和移动容器中已经获得迭代器的任何位置的元素方面表现得更好。
list 和 forward_list 相比于其他的顺序容器。主要缺点在于：它们无法通过索引直接得到元素。
2. 成员函数
(1) 构造函数
通过list类内部的多种重载构造函数，我们有多种方式初始化一个list，如下所示：
#include <iostream>
#include <list>
using namespace std;
int main ()
{
// 1.通过几种不同的（重载）构造函数初始化链表
list<int> first; // empty list of ints
list<int> second (4,100); // four ints with value 100
list<int> third (second.begin(),second.end()); // iterating through second
list<int> fourth (third); // a copy of third
// 2.迭代器可由数组创建，初始化链表
int array[] = {16,2,77,29};
list<int> fifth (array, array + sizeof(array) / sizeof(int) );
cout << "The contents of fifth are: ";
for (list<int>::iterator it = fifth.begin(); it != fifth.end(); it++)
cout << *it << ' ';
return 0;
}
运行结果：
The contents of fifth are: 16 2 77 29
(2) 重载运算符 =
使用重载运算符 = ，可向 list 容器分配新内容，替换其当前内容，并相应地修改其大小。如下所示：
#include <iostream>
#include <list>
using namespace std;
int main ()
{
list<int> first (3); // list of 3 zero-initialized ints
list<int> second (5); // list of 5 zero-initialized ints
second = first;
first = list<int>();
std::cout << "Size of first: " << int (first.size()) <<endl;
std::cout << "Size of second: " << int (second.size()) <<endl;
return 0;
运行结果：
Size of first: 0
Size of second: 3
(3) 迭代器
begin || end
begin()返回指向 list 容器中的第一个元素的迭代器。end()返回指向 list 容器中的最后一个元素的迭代器。如下所示：
#include <iostream>
#include <list>
using namespace std;
int main()
{
int array[] = {75,23,65,42,13};
list<int> mylist(array, array+5);
cout << "mylist contains:";
for (list<int>::iterator it=mylist.begin(); it != mylist.end(); ++it)
std::cout << ' ' << *it;
return 0;
}
运行结果：
mylist contains: 75 23 65 42 13
注：与返回元素的引用的成员 list::front 不同，此函数返回指向它的双向迭代器。
rbegin || rend
r表示reverse，即颠倒的。rbegin/rend表示list 容器的反向迭代器。
#include <iostream>
#include <list>
using namespace std;
int main ()
{
list<int> mylist;
for (int i=1; i<=5; ++i)
mylist.push_back(i);
cout << "mylist backwards:";
for (list<int>::reverse_iterator rit=mylist.rbegin(); rit!=mylist.rend(); ++rit)
cout << ' ' << *rit;
return 0;
}
运行结果：
mylist backwards: 5 4 3 2 1
(4) Capacity
empty
empty() 判断 list 容器是否为空。
#include <iostream>
#include <list>
using namespace std;
int main ()
{
list<int> mylist;
int sum (0);
for(int i=1;i<=10;++i)
mylist.push_back(i);
while (!mylist.empty())
{
sum += mylist.front();
mylist.pop_front();
}
std::cout << "total: " << sum ;
return 0;
}
运行结果：
total: 55
size || max_size
size() 返回 list 中元素的个数。
max_size 返回 list 可以容纳的最大元素数。
#include <iostream>
#include <list>
using namespace std;
int main ()
{
list<int> mylist;
for (int i=0; i<10; i++)
mylist.push_back(i);
cout << "size: " << mylist.size() << endl;
cout << "max_size: " << mylist.max_size() << endl;
return 0;
}
运行结果：
size: 10
max_size: 357913941
(5) 访问元素
front || back
front()返回list中的第一个元素，back()返回list中的最后一个元素。
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<int> mylist;
for(int i=1; i<=5; ++i)
mylist.push_back(i);
cout<<"第一个元素是："<<mylist.front()<<endl;
cout<<"最后一个元素是："<<mylist.back()<<endl;
return 0;
}
运行结果：
(6) 修改list
push_front || push_back
push_front()在原list第一个元素前添加一个数；push_back()在最后一个元素后添加一个数。
#include <iostream>
#include <list>
using namespace std;
int main ()
{
list<int> mylist(2,100); // two ints with a value of 100
cout << "原始的list中各元素：";
for (list<int>::iterator it=mylist.begin(); it!=mylist.end(); ++it)
cout << ' ' << *it;
cout<<endl;
mylist.push_front(200);
mylist.push_front(300);
cout << "在list前插入元素后：";
for (list<int>::iterator it=mylist.begin(); it!=mylist.end(); ++it)
cout << ' ' << *it;
cout <<endl;
mylist.push_back(600);
cout << "在list后插入元素后：";
for (list<int>::iterator it=mylist.begin(); it!=mylist.end(); ++it)
cout << ' ' << *it;
return 0;
}
运行结果：
原始的list中各元素： 100 100
在list前插入元素后： 300 200 100 100
在list后插入元素后： 300 200 100 100 600
pop_front || pop_back
pop_front()：删除list容器中的第一个元素，并将其size减1；
pop_back()：删除list容器中的最后一个元素，并将其size减1。
#include <iostream>
#include <list>
using namespace std;
int main ()
{
list<int> mylist;
for(int i=1;i<=5;i++)
mylist.push_back(i);
cout<<"原list中的元素：";
for(list<int>::iterator it=mylist.begin(); it!=mylist.end(); ++it )
cout<<*it<<" ";
cout<<endl;
mylist.pop_front();
cout << "删除list开头第一个元素后：";
for(list<int>::iterator it=mylist.begin(); it!=mylist.end(); ++it )
cout<<*it<<" ";
cout<<endl;
cout<<"list中元素个数："<<mylist.size()<<endl;
mylist.pop_back();
cout<<"删除list最后一个元素：";
for(list<int>::iterator it=mylist.begin(); it!=mylist.end(); ++it )
cout<<*it<<" ";
cout<<endl;
cout<<"list中元素个数："<<mylist.size()<<endl;
return 0;
}
运行结果：
原list中的元素：1 2 3 4 5
删除list开头第一个元素后：2 3 4 5
list中元素个数：4
删除list最后一个元素：2 3 4
list中元素个数：3
insert
insert 在指定位置的元素之前插入新元素。
#include <iostream>
#include <list>
#include <vector>
using namespace std;
int main ()
{
list<int> mylist;
list<int>::iterator it; //声明it为迭代器
for(int i=1; i<=5; ++i) mylist.push_back(i); // 1 2 3 4 5
it = mylist.begin();
++it; // it points now to number 2 ^
mylist.insert (it,10); // 1 10 2 3 4 5
// "it" still points to number 2 ^
mylist.insert (it,2,20); // 1 10 20 20 2 3 4 5
--it; // it points now to the second 20 ^
std::vector<int> myvector (2,30);
mylist.insert (it,myvector.begin(),myvector.end()); // 1 10 20 30 30 20 2 3 4 5
std::cout << "mylist contains:";
for (it=mylist.begin(); it!=mylist.end(); ++it)
cout << ' ' << *it;
return 0;
}
运行结果：
mylist contains: 1 10 20 30 30 20 2 3 4 5
erase
erase 从 list 容器中移除单个元素或元素范围。
#include <iostream>
#include <list>
using namespace std;
int main ()
{
list<int> mylist;
list<int>::iterator it1,it2;
// set some values:
for (int i=1; i<10; ++i) mylist.push_back(i*10);
// 10 20 30 40 50 60 70 80 90
it1 = it2 = mylist.begin(); // ^^
advance (it2,6); // ^ ^
++it1; // ^ ^
it1 = mylist.erase(it1); // 10 30 40 50 60 70 80 90
// ^ ^
it2 = mylist.erase(it2); // 10 30 40 50 60 80 90
// ^ ^
++it1; // ^ ^
--it2; // ^ ^
mylist.erase (it1,it2); // 10 30 60 80 90
// ^
cout << "mylist contains:";
for (it1=mylist.begin(); it1!=mylist.end(); ++it1)
cout << ' ' << *it1;
return 0;
}
运行结果：
mylist contains: 10 30 60 80 90
swap
list1.swap(list2)：list容器整体互换
#include <iostream>
#include <list>
int main ()
{
std::list<int> first (3,100); // three ints with a value of 100
std::list<int> second (5,200); // five ints with a value of 200
first.swap(second);
std::cout << "first contains:";
for (std::list<int>::iterator it=first.begin(); it!=first.end(); it++)
std::cout << ' ' << *it;
std::cout << '\n';
std::cout << "second contains:";
for (std::list<int>::iterator it=second.begin(); it!=second.end(); it++)
std::cout << ' ' << *it;
return 0;
}
运行结果：
first contains: 200 200 200 200 200
second contains: 100 100 100
resize
resize()：调整容器list的size大小，使其包含n个元素。
如果n小于当前容器的大小，则内容将减少到前n个元素，删除(并销毁它们)。
如果n大于当前容器的大小，则通过在末尾插入所需的元素来扩展内容，使其达到n的大小。如果指定了val，如list.resize(n, val) ，则将新元素初始化为val；否则初始化为0。
#include <iostream>
#include <list>
int main ()
{
std::list<int> mylist;
// set some initial content:
for (int i=1; i<10; ++i) mylist.push_back(i); //1 2 3 4 5 6 7 8 9
mylist.resize(5); //1 2 3 4 5
mylist.resize(8,100); //1 2 3 4 5 100 100 100
mylist.resize(12); //1 2 3 4 5 100 100 100 0 0 0 0
std::cout << "mylist contains:";
for (std::list<int>::iterator it=mylist.begin(); it!=mylist.end(); ++it)
std::cout << ' ' << *it;
return 0;
}
运行结果：
mylist contains: 1 2 3 4 5 100 100 100 0 0 0 0
clear
clear()：从list容器中删除所有元素，并将容器的size大小保留为0。
#include <iostream>
#include <list>
int main ()
{
std::list<int> mylist;
std::list<int>::iterator it;
mylist.push_back (100);
mylist.push_back (200);
mylist.push_back (300);
std::cout << "mylist contains:";
for (it=mylist.begin(); it!=mylist.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
mylist.clear(); //清空所有元素
mylist.push_back (1101);
mylist.push_back (2202);
std::cout << "mylist contains:";
for (it=mylist.begin(); it!=mylist.end(); ++it)
std::cout << ' ' << *it;
return 0;
}
运行结果：
mylist contains: 100 200 300
mylist contains: 1101 2202
(7) Operations
remove
list.remove(val)：从容器list中删除所有与val相同的元素。并相应的减小容器的size大小。
成员函数list::erase根据元素的位置(使用迭代器)删除元素，与之不同的是，这个函数(list::remove)根据元素的值删除元素。
#include <iostream>
#include <list>
int main ()
{
int myints[]= {5,6,8,8,9,45,8};
std::list<int> mylist (myints,myints+7);
mylist.remove(8); //删除链表中所有为8的元素
std::cout << "mylist contains:";
for (std::list<int>::iterator it=mylist.begin(); it!=mylist.end(); ++it)
std::cout << ' ' << *it;
return 0;
}
运行结果：
mylist contains: 5 6 9 45
remove_if
remove_if(condition)：按指定条件condition删除list容器中的部分元素。
#include <iostream>
#include <list>
// a predicate implemented as a function:
bool single_digit (const int& value) { return (value<10); }
// a predicate implemented as a class:
struct is_odd {
bool operator() (const int& value) { return (value%2)==1; }
};
int main ()
{
int myints[]= {15,36,7,17,20,39,4,1};
std::list<int> mylist (myints,myints+8); // 15 36 7 17 20 39 4 1
mylist.remove_if (single_digit); // 15 36 17 20 39
mylist.remove_if (is_odd()); // 36 20
std::cout << "mylist contains:";
for (std::list<int>::iterator it=mylist.begin(); it!=mylist.end(); ++it)
std::cout << ' ' << *it;
return 0;
}
运行结果：
mylist contains: 36 20
unique
版本1：list.unique()：删除容器list中相同的元素，只保留最前面的那个元素。
版本2：list.unique(condition)：删除容器list中不符合condition的元素。
#include <iostream>
#include <cmath>
#include <list>
// 判断元素整数部分相同
bool same_integral_part (double first, double second)
{ return ( int(first)==int(second) ); }
// 判断相邻元素距离是否小于5
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 };
std::list<double> mylist (mydoubles,mydoubles+10);
mylist.sort(); // 2.72, 3.14, 12.15, 12.77, 12.77,
// 15.3, 72.25, 72.25, 73.0, 73.35
//版本1
mylist.unique(); // 2.72, 3.14, 12.15, 12.77
// 15.3, 72.25, 73.0, 73.35
//版本2
mylist.unique (same_integral_part); // 2.72, 3.14, 12.15
// 15.3, 72.25, 73.0
mylist.unique (is_near()); // 2.72, 12.15, 72.25
std::cout << "mylist contains:";
for (std::list<double>::iterator it=mylist.begin(); it!=mylist.end(); ++it)
std::cout << ' ' << *it;
return 0;
}
运行结果：
mylist contains: 2.72 12.15 72.25
sort
版本1：list.sort()：默认按ASCII码排序
版本2：list.sort(comp)：按照自定义排序规则comp进行排序
#include <iostream>
#include <list>
#include <string>
#include <cctype>
// comparison, not case sensitive.
bool compare_nocase (const std::string& first, const std::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 ()
{
std::list<std::string> mylist;
std::list<std::string>::iterator it;
mylist.push_back ("one");
mylist.push_back ("two");
mylist.push_back ("Three");
mylist.sort();
std::cout << "mylist contains:";
for (it=mylist.begin(); it!=mylist.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
mylist.sort(compare_nocase);
std::cout << "mylist contains:";
for (it=mylist.begin(); it!=mylist.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
运行结果：
mylist contains: Three one two
mylist contains: one Three two
reverse
list.reverse()：颠倒list容器中元素的顺序
#include <iostream>
#include <list>
int main ()
{
std::list<int> mylist;
for (int i=1; i<10; ++i) mylist.push_back(i);
mylist.reverse();
std::cout << "mylist contains:";
for (std::list<int>::iterator it=mylist.begin(); it!=mylist.end(); ++it)
std::cout << ' ' << *it;
return 0;
}
运行结果：
mylist contains: 9 8 7 6 5 4 3 2 1
转载：https://blog.csdn.net/wjinjie/article/details/106557562
查看评论