往期汇总:
C++STL(1) vector容器汇总
C++STL(2) list容器汇总
C++STL(3) queue容器汇总
C++STL(4) stack容器汇总
C++STL(5) set容器汇总
C++STL(6) map容器汇总
C++STL(7) unordered_map容器汇总
C++STL(2) list容器汇总
一、概述
std::list
是C++标准库提供的双向链表容器。与std::vector
不同,std::list
不是基于连续内存存储元素的,而是通过指针链接各个元素。这使得std::list
在插入和删除元素时具有更好的性能,但在随机访问元素时性能较差。
下面是std::list
的一些特点:
-
双向链表:
std::list
的元素以双向链表的形式存储,每个元素都包含指向前一个元素和后一个元素的指针。 -
插入和删除:由于链表的特性,
std::list
在插入和删除元素时效率很高,不需要移动其他元素。插入和删除操作的时间复杂度为O(1)。 -
无需重新分配内存:与
std::vector
不同,std::list
不需要在插入和删除元素时重新分配内存,因为它使用指针链接元素。 -
没有随机访问:由于
std::list
不是基于连续内存,因此不能像std::vector
那样通过索引进行随机访问。要访问std::list
中的元素,需要从头或尾开始遍历链表。 -
迭代器稳定性:
std::list
的迭代器在插入和删除操作后保持有效,不会失效或指向无效的元素。 -
使用注意:由于
std::list
的元素不是在连续内存中存储的,因此它的存取速度相对较慢。在大多数情况下,如果需要频繁地进行随机访问或在尾部进行插入/删除操作,std::vector
可能更合适。
二、详细介绍及用法
当使用C++的std::list
容器时,可以通过多种方式进行初始化。下面是一些常见的初始化std::list
容器的方法:
- 默认初始化:创建一个空的
std::list
容器。
std::list<int> myList; // 默认构造函数创建一个空的list
- 使用元素范围初始化:使用其他容器中的元素范围初始化
std::list
容器。
std::vector<int> vec = {1, 2, 3, 4};
std::list<int> myList(vec.begin(), vec.end()); // 使用vec中的元素范围初始化list
- 使用重复元素初始化:使用相同的元素值初始化
std::list
容器。
std::list<int> myList(5, 42); // 初始化包含5个值为42的元素的list
- 使用初始化列表初始化:使用大括号初始化列表初始化
std::list
容器。
std::list<int> myList = {1, 2, 3, 4}; // 使用初始化列表初始化list
当使用C++的std::list
容器时,以下是一些常用函数的详细介绍:
push_back()
:在容器的末尾插入一个元素。
std::list<int> myList;
myList.push_back(42); // 在容器末尾插入元素42
push_front()
:在容器的开头插入一个元素。
std::list<int> myList;
myList.push_front(42); // 在容器开头插入元素42
pop_back()
:删除容器末尾的元素。
std::list<int> myList = {1, 2, 3, 4};
myList.pop_back(); // 删除容器末尾的元素,此时容器为 {1, 2, 3}
pop_front()
:删除容器开头的元素。
std::list<int> myList = {1, 2, 3, 4};
myList.pop_front(); // 删除容器开头的元素,此时容器为 {2, 3, 4}
size()
:返回容器中的元素数量。
std::list<int> myList = {1, 2, 3, 4};
std::cout << myList.size() << std::endl; // 输出:4
empty()
:检查容器是否为空。
std::list<int> myList;
if (myList.empty()) {
std::cout << "容器为空" << std::endl;
} else {
std::cout << "容器不为空" << std::endl;
}
clear()
:清空容器,删除所有的元素。
std::list<int> myList = {1, 2, 3, 4};
myList.clear(); // 清空容器,此时容器为空
begin()
和end()
:用于迭代器的起始和结束位置。
std::list<int> myList = {1, 2, 3, 4};
// 使用迭代器遍历容器
for (auto it = myList.begin(); it != myList.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl; // 输出:1 2 3 4
rbegin()
和rend()
:用于反向迭代器的起始和结束位置。
std::list<int> myList = {1, 2, 3, 4};
// 使用反向迭代器遍历容器
for (auto it = myList.rbegin(); it != myList.rend(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl; // 输出:4 3 2 1
insert()
:在指定位置插入一个或多个元素。
std::list<int> myList = {1, 2, 3, 4};
auto it = myList.begin();
++it; // 将迭代器移动到第二个位置
myList.insert(it, 42); // 在第二个位置插入元素42,此时容器为 {1, 42, 2, 3, 4}
// 在第二个位置插入元素范围
std::vector<int> vec = {5, 6};
myList.insert(it, vec.begin(), vec.end()); // 此时容器为 {1, 5, 6, 42, 2, 3, 4}
erase()
:从容器中删除指定位置或指定范围的元素。
std::list<int> myList = {1, 2, 3, 4, 5};
auto it = myList.begin();
++it; // 将迭代器移动到第二个位置
myList.erase(it); // 删除第二个位置的元素,此时容器为 {1, 3,4, 5}
// 删除指定范围的元素
auto first = myList.begin();
auto last = myList.end();
--last; // 将迭代器移动到最后一个位置
myList.erase(first, last); // 删除第一个位置到最后一个位置之前的元素,此时容器只剩下一个元素:{5}
front()
和back()
:分别返回容器的第一个元素和最后一个元素的引用。
std::list<int> myList = {1, 2, 3, 4};
int firstElement = myList.front(); // 获取第一个元素,值为1
int lastElement = myList.back(); // 获取最后一个元素,值为4
assign()
:用新的元素替换容器的内容。
std::list<int> myList = {1, 2, 3, 4};
// 用新的元素 {5, 6, 7} 替换容器的内容
myList.assign({5, 6, 7}); // 容器变为 {5, 6, 7}
resize()
:改变容器的大小。
std::list<int> myList = {1, 2, 3, 4};
myList.resize(6); // 将容器的大小调整为6,默认使用0填充剩余的位置,容器变为 {1, 2, 3, 4, 0, 0}
myList.resize(3); // 将容器的大小调整为3,多余的元素被删除,容器变为 {1, 2, 3}
remove()
:删除容器中所有与给定值相等的元素。
std::list<int> myList = {1, 2, 2, 3, 4, 2};
myList.remove(2); // 删除容器中所有值为2的元素,容器变为 {1, 3, 4}
reverse()
:反转容器中的元素顺序。
std::list<int> myList = {1, 2, 3, 4};
myList.reverse(); // 反转容器中的元素顺序,容器变为 {4, 3, 2, 1}
sort()
:对容器中的元素进行排序。
std::list<int> myList = {4, 2, 1, 3};
myList.sort(); // 对容器中的元素进行升序排序,容器变为 {1, 2, 3, 4}
merge()
:将两个已排序的容器合并成一个已排序的容器。
std::list<int> list1 = {1, 3, 5};
std::list<int> list2 = {2, 4, 6};
list1.merge(list2); // 将list2合并到list1中,list1和list2都必须是已排序的容器,合并后list1变为 {1, 2, 3, 4, 5, 6},list2变为空
splice()
:将一个容器的元素移动到另一个容器中的指定位置。
std::list<int> list1 = {1, 2, 3};
std::list<int> list2 = {4, 5};
auto it = list1.begin();
++it; // 将迭代器移动到第二个位置
list1.splice(it, list2); // 将list2中的所有元素移动到list1的第二个位置之前,list1变为 {1, 4, 5, 2, 3},list2变为空
unique()
:用于去除容器中相邻重复的元素,只保留一个副本。该函数会对容器进行就地修改,将重复的元素移除。
std::list<int> myList = {1, 1, 2, 2, 3, 3, 4, 4};
myList.unique(); // 去除相邻重复元素,容器变为 {1, 2, 3, 4}
注意,`unique()`函数只能去除相邻重复的元素。如果要去除所有重复的元素,可以先对容器进行排序,然后再使用`unique()`函数。
max_size()
:返回std::list
容器能够容纳的最大元素数量。该函数返回一个无符号整数,表示容器的最大容量。
std::list<int> myList;
std::cout << "最大容量:" << myList.max_size() << std::endl;
注意,`max_size()`返回的是理论上的最大容量,实际分配的容量可能会受到系统限制或可用内存的限制。
emplace_back()
:用于在容器的末尾直接构造一个新元素。与push_back()
函数相比,emplace_back()
可以直接在容器中构造对象,而不需要创建临时对象。
struct MyStruct {
int value1;
std::string value2;
MyStruct(int v1, std::string v2) : value1(v1), value2(v2) {}
};
std::list<MyStruct> myList;
myList.emplace_back(42, "Hello"); // 在容器末尾直接构造一个新元素
// 等效于
myList.push_back(MyStruct(42, "Hello"));
使用`emplace_back()`可以避免创建临时对象,提高效率。
三、结语
std::list
作为C++
标准库提供的一种双向链表容器,与其他容器(如std::vector
、std::deque
)相比,std::list
具有一些独特的特性:
-
插入和删除操作效率高: 由于
std::list
是基于链表实现的,插入和删除操作对于任意位置的元素都非常高效,不受容器大小的影响。这使得std::list
在需要频繁进行插入和删除操作的场景下具有优势。 -
不需要连续内存:
std::list
使用链表结构存储元素,不要求元素在内存中连续存储。这使得std::list
能够处理大量元素或者元素大小变化频繁的情况。 -
稳定的迭代器: 在对
std::list
进行插入和删除操作时,与被操作的元素无关的迭代器仍然保持有效,这是由于链表的特性所决定的。这使得std::list
在需要在迭代过程中进行插入和删除操作的场景下非常有用。
然而,std::list
也有一些限制和缺点:
-
随机访问效率低: 由于链表的特性,
std::list
不支持通过索引进行随机访问。如果需要经常通过索引来访问元素,使用std::vector
可能更合适。 -
额外的空间开销: 与其他容器相比,
std::list
在存储每个元素时需要额外的指针来维护链表结构,这会引入一定的空间开销。
综上所述,std::list
在某些特定的应用场景下非常有用,特别是对于频繁进行插入和删除操作、不需要随机访问、或者需要稳定迭代器的情况。然而,在其他情况下,其他容器可能更适合,具体选择取决于具体的需求和性能要求。在选择容器时,需要综合考虑数据结构的特性、操作的复杂度、内存占用和性能要求等因素。
最佳的容器选择取决于特定的用例和需求,没有一种容器适用于所有情况。因此,熟悉各种容器的特性和适用场景非常重要,以便根据具体需求做出正确的选择。
大佬好厉害