std::list容器,顾名思义,实现了双向链表的数据结构。与基于数组的容器(如std::vector)不同,std::list中的元素并不是连续存储在内存中的,而是通过节点(Node)之间的指针相互连接。这种设计赋予了std::list在插入和删除操作上的巨大优势——无论元素位于何处,这些操作都可以在常数时间复杂度O(1)内完成,而无需像数组那样可能需要移动大量元素。
因此,让我们一起探索std::list的奥秘,领略其在C++编程中的独特魅力吧!
list容器,在C++标准模板库(STL)中,是一个非常重要的数据结构,它基于双向链表实现,提供了灵活的元素管理和操作功能。以下是对list容器的详细解析:
list<T> lst;
:默认构造函数,创建一个空的list。list(beg, end);
:将[beg, end)区间中的元素拷贝给list。list(n, elem);
:创建包含n个elem的list。list(const list &lst);
:拷贝构造函数。assign(beg, end);
:将[beg, end)区间中的数据拷贝赋值给list。assign(n, elem);
:将n个elem拷贝赋值给list。list& operator=(const list &lst);
:重载等号操作符,实现赋值操作。swap(lst);
:将lst与当前list的元素互换。size();
:返回容器中元素的个数。empty();
:判断容器是否为空。resize(num);
:重新指定容器的长度为num,若容器变长,则以默认值填充新位置;若容器变短,则末尾超出容器长度的元素被删除。resize(num, elem);
:重新指定容器的长度为num,若容器变长,则以elem值填充新位置;若容器变短,则末尾超出容器长度的元素被删除。push_back(elem);
:在容器尾部加入一个元素。pop_back();
:删除容器中最后一个元素。push_front(elem);
:在容器开头插入一个元素。pop_front();
:在容器开头移除第一个元素。insert(pos, elem);
:在pos位置插elem元素的拷贝,返回新数据的位置。insert(pos, n, elem);
:在pos位置插入n个elem数据,无返回值。insert(pos, beg, end);
:在pos位置插入[beg, end)区间的数据,无返回值。erase(beg, end);
:删除[beg, end)区间的数据,返回下一个数据的位置。erase(pos);
:删除pos位置的数据,返回下一个数据的位置。remove(elem);
:删除容器中所有与elem值匹配的元素。front();
:返回第一个元素。back();
:返回最后一个元素。reverse();
:反转链表。sort();
:对链表中的元素进行排序。在C++中,std::list
是一个序列容器,它允许在常数时间内从容器的前端或后端插入和删除元素。std::list
的初始化方法有多种,以下是一些常见的初始化方法:
std::list<int> myList; // 创建一个空的int类型的list
std::list<int> myList1 = {1, 2, 3, 4};
std::list<int> myList2(myList1); // 复制myList1到myList2
或者使用std::list
的赋值运算符:
std::list<int> myList2 = myList1; // 赋值操作,效果同复制构造函数
如果你有两个迭代器,指向一个范围的开始和结束,你可以使用这个范围来初始化list
:
std::vector<int> myVec = {1, 2, 3, 4};
std::list<int> myList(myVec.begin(), myVec.end()); // 使用vector的范围初始化list
C++11及以后的版本支持使用初始化列表来初始化list
:
std::list<int> myList = {1, 2, 3, 4, 5}; // 直接使用初始化列表
在C++中,std::list
的迭代器提供了对链表元素进行遍历的能力,但由于std::list
是双向链表,其迭代器是双向迭代器,不支持随机访问。这意味着你不能像访问数组或std::vector
那样通过下标直接访问元素,但你可以使用迭代器向前或向后遍历链表。
it + n
或list[i]
这样的表达式来访问元素。std::list
中,除了删除迭代器所指向的元素外,其他元素的插入或删除通常不会使迭代器失效。++it
):将迭代器向前移动到下一个元素。--it
):将迭代器向后移动到前一个元素。\*it
):获取迭代器当前指向的元素的值。it1 == it2
、it1 != it2
):比较两个迭代器是否相等或不相等。以下是一个使用std::list
迭代器的详细代码示例,包括正向遍历、反向遍历以及使用迭代器修改元素值的操作。
#include <iostream>
#include <list>
int main() {
// 创建一个std::list并初始化
std::list<int> myList = {1, 2, 3, 4, 5};
// 正向遍历std::list
std::cout << "正向遍历: ";
for (std::list<int>::iterator it = myList.begin(); it != myList.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
// 使用迭代器修改元素值
// 将第一个元素设置为100
if (!myList.empty()) {
std::list<int>::iterator firstIt = myList.begin();
*firstIt = 100;
}
// 再次正向遍历以显示修改后的结果
std::cout << "修改后正向遍历: ";
for (std::list<int>::iterator it = myList.begin(); it != myList.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
// 反向遍历std::list
std::cout << "反向遍历: ";
for (std::list<int>::reverse_iterator rit = myList.rbegin(); rit != myList.rend(); ++rit) {
std::cout << *rit << " ";
}
std::cout << std::endl;
// 注意:这里没有展示插入或删除元素后迭代器有效性的变化,
// 因为这通常依赖于具体的操作位置。但请记住,删除迭代器所指向的元素后,该迭代器将变为无效。
return 0;
}
end()
返回的迭代器是未定义行为。std::list
的迭代器在大多数情况下能够保持有效,但在删除迭代器所指向的元素后,该迭代器将不再有效。在C++的std::list
容器中,元素的访问方式与数组或std::vector
等序列容器有所不同,因为std::list
是一个双向链表。它不支持通过下标(索引)直接访问元素,因为链表中的元素在内存中并不是连续存储的。相反,你需要使用迭代器或C++11引入的范围for循环来访问std::list
中的元素。
迭代器提供了一种访问容器中元素的方法,同时允许你在容器上进行遍历。对于std::list
,你可以使用begin()
成员函数获取指向第一个元素的迭代器,使用end()
成员函数获取一个特殊的“尾后迭代器”,它并不指向任何元素,而是用作遍历的结束标记。
#include <iostream>
#include <list>
int main() {
std::list<int> myList = {10, 20, 30, 40, 50};
// 使用迭代器访问第一个元素
if (!myList.empty()) {
std::list<int>::iterator it = myList.begin();
std::cout << "第一个元素是: " << *it << std::endl;
// 向前移动到下一个元素并访问
++it;
std::cout << "第二个元素是: " << *it << std::endl;
// 反向移动(如果需要的话,需要先将迭代器保存到另一个变量)
// 注意:这里只是演示如何移动迭代器,实际反向遍历应使用reverse_iterator
}
// 使用迭代器遍历整个list
for (std::list<int>::iterator it = myList.begin(); it != myList.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
return 0;
}
从C++11开始,你可以使用基于范围的for循环来简化对容器的遍历,而无需显式使用迭代器。范围for循环内部使用迭代器来遍历容器,但提供了更简洁的语法。
#include <iostream>
#include <list>
int main() {
std::list<int> myList = {10, 20, 30, 40, 50};
// 使用范围for循环遍历list
for (int elem : myList) {
std::cout << elem << " ";
}
std::cout << std::endl;
return 0;
}
在这个例子中,elem
变量在每次迭代中都会被赋予myList
中当前元素的拷贝(对于基本数据类型如int
,这是通过值传递实现的)。因此,你不能通过elem
来修改myList
中的元素,除非elem
是一个引用类型(但范围for循环默认不支持直接使用引用类型,你需要使用迭代器或C++17引入的结构化绑定等技巧来实现)。
注意
std::list
的元素不是连续存储的,因此你不能像访问数组或std::vector
那样使用下标来访问元素。在C++中,std::list
是一个双向链表容器,它提供了丰富的成员函数来支持插入、删除和修改操作。由于C语言本身不直接支持STL(Standard Template Library)中的std::list
或类似的高级容器,我将基于C++的std::list
来分析和解释这些操作。
以下是对std::list
中一些常见的插入、删除和修改操作的分析,以及对应的代码示例:
push_back(const T& value)
:在列表的末尾插入一个元素。
std::list<int> myList;
myList.push_back(10); // 在myList的末尾插入10
push_front(const T& value)
:在列表的开头插入一个元素。
myList.push_front(5); // 在myList的开头插入5
insert(iterator position, const T& value)
:在指定位置前插入一个元素。
auto it = myList.begin(); // 获取指向第一个元素的迭代器
myList.insert(it, 7); // 在第一个元素之前插入7
emplace(iterator position, Args&&... args)
(C++11及以后):在指定位置前原地构造一个元素。
myList.emplace(myList.begin(), 3); // 在第一个元素之前原地构造一个值为3的元素
pop_back()
:删除列表的最后一个元素。
if (!myList.empty()) {
myList.pop_back(); // 删除myList的最后一个元素
}
pop_front()
(C++11及以后):删除列表的第一个元素。
if (!myList.empty()) {
myList.pop_front(); // 删除myList的第一个元素
}
erase(iterator position)
或 erase(iterator first, iterator last)
:删除指定位置的元素或删除一个范围内的元素。
auto it = myList.begin();
std::advance(it, 2); // 向前移动两个位置
myList.erase(it); // 删除当前迭代器指向的元素
// 或者删除一个范围内的元素
auto range_start = myList.begin();
std::advance(range_start, 1);
auto range_end = myList.begin();
std::advance(range_end, 3); // 注意:range_end不会包括在内
myList.erase(range_start, range_end); // 删除从range_start到range_end之前的元素
clear()
:删除列表中的所有元素。
myList.clear(); // 删除myList中的所有元素
对于std::list
,修改操作通常不涉及到容器的特定成员函数,因为你可以直接通过迭代器或引用来修改元素的值。
auto it = myList.begin();
if (it != myList.end()) {
*it = 20; // 修改第一个元素的值为20
}
// 或者如果你有一个元素的引用
int& firstElement = myList.front(); // 假设myList不为空
firstElement = 30; // 修改第一个元素的值为30
请注意,由于std::list
中的元素不是连续存储的,因此你不能像访问数组那样通过索引来直接修改元素。相反,你需要使用迭代器或特定的成员函数(如front()
和back()
)来获取对元素的引用,然后才能修改它。
在C++中,std::list
的迭代器失效情况与其他容器(如std::vector
)有所不同,主要是因为std::list
是一个双向链表,其元素在内存中的位置不是连续的。这意呀着,当在std::list
中进行插入或删除操作时,不会导致其他元素的内存位置发生变化(与std::vector
不同,后者在插入或删除元素时可能需要重新分配内存并移动其他元素)。
然而,尽管std::list
的插入和删除操作不会直接影响其他元素的内存位置,但迭代器失效的情况仍然可能发生,特别是在以下几种情况下:
erase
方法,并且它返回了一个指向被删除元素之后元素的迭代器,那么这个返回的迭代器是有效的(前提是它不等于end()
迭代器)。auto it = myList.begin();
if (it != myList.end()) {
it = myList.erase(it); // it现在指向被删除元素之后的元素,或者如果它是最后一个元素,则it等于end()
}
end()
之后的位置,或者通过某种方式(比如错误的递增或递减操作)使迭代器超出了其有效范围,那么迭代器将失效。
std::list
对象被销毁,那么其所有迭代器都将失效。
std::list
通常不需要重新分配内存(与std::vector
不同),但如果你以某种方式(尽管这在标准库中不是直接支持的)复制或移动了std::list
对象,并且源对象在操作后不再存在,那么原对象的迭代器将失效。然而,这种情况更常见于std::vector
等需要连续存储的容器。
std::list
的迭代器在某些操作后可能仍然指向某个位置,但如果那个位置已经不再属于std::list
(比如因为它被删除了),那么使用那个迭代器就是未定义行为。因此,总是要在修改容器后立即检查你的迭代器是否仍然有效,并在必要时更新它们。对于std::list
来说,只要你不删除迭代器当前指向的元素,或者没有让迭代器超出其有效范围,你就可以安全地使用它进行遍历或其他操作。但是,在删除元素时,务必小心处理迭代器,以避免使用已失效的迭代器。
在C++中,std::list
容器支持排序操作,但它不提供像std::sort
这样的通用排序函数(因为std::sort
需要随机访问迭代器,而std::list
只提供双向迭代器)。相反,std::list
有自己的成员函数sort()
来进行排序。
排序函数:
void sort();
void sort(Compare comp);
(其中Compare
是一个函数对象或lambda表达式,用于定义排序准则)排序示例:
#include <iostream>
#include <list>
#include <algorithm> // 虽然此处不需要,但为了完整性包含
int main() {
std::list<int> myList = {4, 1, 3, 5, 2};
myList.sort(); // 默认升序排序
for (int elem : myList) {
std::cout << elem << ' ';
}
// 输出: 1 2 3 4 5
return 0;
}
std::list
没有直接的成员函数来去除重复元素,但可以通过结合sort()
和unique()
成员函数来实现去重。需要注意的是,unique()
函数将相邻的重复元素合并为单个元素,并返回指向新逻辑序列末尾的迭代器,但它不实际删除多余的元素。因此,在调用unique()
之后,通常需要调用erase()
来删除多余的元素。
去重步骤:
sort()
对列表进行排序。unique()
将相邻的重复元素合并。erase()
删除多余的元素。去重示例:
#include <iostream>
#include <list>
#include <algorithm> // std::unique需要此头文件,尽管直接用于list时不需要算法头文件
int main() {
std::list<int> myList = {1, 2, 2, 3, 4, 4, 4, 5};
myList.sort(); // 首先排序
auto last = std::unique(myList.begin(), myList.end()); // 去重,last指向新逻辑序列的末尾
myList.erase(last, myList.end()); // 删除多余的元素
for (int elem : myList) {
std::cout << elem << ' ';
}
// 输出: 1 2 3 4 5
return 0;
}
优点:
std::list
中的任何位置进行插入和删除操作都是常数时间复杂度O(1),因为它基于链表结构,不需要像数组或向量那样移动大量元素。std::list
可以动态地增长和缩小,不需要预先知道其大小。std::list
的迭代器可以双向移动,这意味着可以向前或向后遍历列表。缺点:
std::list
中的元素不如访问数组或向量中的元素快。std::list
的随机访问时间复杂度是O(n),因为需要从头或尾开始遍历列表来找到元素。std::list
通常会使用更多的内存,因为它需要存储额外的指针来维护链表结构。std::list
的元素不是连续存储的,这可能会导致缓存不友好,因为访问相邻的元素可能会跨越很大的内存区域。std::list
的迭代器不支持使用+或-运算符进行随机访问,只能逐个移动。std::list
中插入和删除元素可能会导致内存碎片。综上所述,std::list
在需要频繁插入和删除元素的场景下非常有用,但在需要高效随机访问元素的场景中则可能不是最佳选择。
在本文中,我们深入探讨了C++标准库中的std::list容器。std::list以其双向链表的数据结构提供了灵活的序列操作,允许在常数时间内进行元素的插入和删除。我们详细讨论了其各种成员函数,包括迭代器、容量管理、元素访问、修改器以及一系列非成员函数操作,这些功能使得std::list在特定场景下成为一种非常强大的工具。
今天的分享到这里就结束啦!如果觉得文章还不错的话,可以三连支持一下,17的主页还有很多有趣的文章,欢迎小伙伴们前去点评,您的支持就是17前进的动力!