C++ list类

目录

0.前言

1.list介绍

1.1优势

1.2劣势

1.3容器属性

2.list使用

2.1构造函数

2.1.1默认构造函数

2.1.2填充构造函数

2.1.3范围构造函数

2.1.4拷贝构造函数

2.1.5初始化列表构造函数 

2.2迭代器

2.2.1 begin()

2.2.2 end()

2.2.3 cbegin()

2.2.4 cend()

2.2.5 rbegin()

2.2.6 rend()

2.2.7 crbegin()

2.2.8 crend()

2.3容量获取及元素访问函数

2.3.1 empty()

2.3.2 size()

2.3.3 front()

2.3.4 back()

2.4修改函数

2.4.1 assign

2.4.2 push_front 和 pop_front

 2.4.3 push_back 和 pop_back

 2.4.4 insert

2.4.5 erase

2.4.6 swap

2.4.7 clear

2.5其他功能函数

2.5.1 splice

2.5.2 unique

3.list的模拟实现

3.1基本实现代码

3.2 list正/反向迭代器实现

3.2.1正向迭代器 (ListIterator)

3.2.2反向迭代器 (ListReverseIterator)

4.list与vector的比较

4.1 内部实现

4.2 存储方式

4.3 访问和遍历

4.4 插入和删除操作

4.5 内存管理

4.6 使用场景

5.结语

（图像由AI生成） 

0.前言

在前面的文章中，我们已经详细介绍了 C++ 标准模板库中的 string 和 vector 类的用法及实现。接下来，我们将深入探讨 list 类，这是一种双向链表结构，适合于频繁插入和删除操作的场景。通过这篇文章，我们将全面了解 list 的构造函数、迭代器、容量获取与元素访问函数、修改函数、以及其他功能函数，并比较 list 与 vector 的异同，帮助你在实际编程中做出更合适的数据结构选择。

1.list介绍

list 是 C++ 标准模板库中的一种序列容器，允许在序列中的任何位置进行常数时间的插入和删除操作，并且支持双向迭代。它的实现基于双向链表，这种结构允许元素存储在不同且不相关的内存位置，内部通过每个元素与前一个和后一个元素的链接来保持顺序。

双向链表与单向链表（如 forward_list）非常相似，主要区别在于单向链表只能向前迭代，而双向链表可以在两个方向上迭代。尽管单向链表在内存占用和效率上略优，但双向链表提供了更灵活的迭代和操作方式。

1.1优势

与其他基本标准序列容器（如 array、vector 和 deque）相比，list 在以下方面通常表现更好：

  • 插入和删除操作：在任意位置插入、提取和移动元素的性能更优，特别是在已获得迭代器的位置。
  • 排序算法：在需要频繁插入和删除操作的排序算法中表现更佳。

1.2劣势

list 和 forward_list 与其他序列容器相比存在一些缺点：

  • 缺乏直接访问：无法通过位置直接访问元素。例如，要访问 list 中的第六个元素，需要从已知位置（如开头或结尾）迭代到该位置，这需要线性时间。
  • 额外的内存开销：为了维护元素之间的链接信息，list 需要额外的内存，这在处理大量小元素时可能是一个重要因素。

1.3容器属性

  • 序列：序列容器中的元素按严格的线性顺序排列。可以通过其在序列中的位置访问单个元素。
  • 双向链表：每个元素都包含信息以定位下一个和前一个元素，从而允许在特定元素之前或之后（甚至是整个范围）进行常数时间的插入和删除操作，但不支持直接随机访问。
  • 分配器感知：容器使用分配器对象来动态管理其存储需求。

2.list使用

2.1构造函数

default (1) 
explicit list (const allocator_type& alloc = allocator_type());
fill (2) 
explicit list (size_type n);list (size_type n, const value_type& val,const allocator_type& alloc = allocator_type());
range (3) 
template <class InputIterator>list (InputIterator first, InputIterator last,const allocator_type& alloc = allocator_type());
copy (4) 
list (const list& x);
list (const list& x, const allocator_type& alloc);
initializer list (5) 
list (initializer_list<value_type> il,const allocator_type& alloc = allocator_type());

C++ 中的 list 提供了多种构造函数，用于不同的初始化需求。下面我们详细介绍每种构造函数，并提供示例代码来说明它们的使用。

2.1.1默认构造函数

explicit list (const allocator_type& alloc = allocator_type());

创建一个空链表，可以指定一个分配器。

示例代码：

#include <iostream>
#include <list>int main() {std::list<int> mylist;std::cout << "Size of mylist: " << mylist.size() << std::endl;return 0;
}
//输出：Size of mylist: 0

2.1.2填充构造函数

explicit list (size_type n);
list (size_type n, const value_type& val, const allocator_type& alloc = allocator_type());

创建一个包含 n 个默认值元素的链表，或创建一个包含 n 个指定值 val 的链表。

示例代码：

#include <iostream>
#include <list>int main() {std::list<int> mylist1(5); // 创建一个包含5个默认值元素的链表std::list<int> mylist2(5, 100); // 创建一个包含5个值为100的元素的链表std::cout << "mylist1 contains:";for (int& x : mylist1) std::cout << ' ' << x;std::cout << '\n';std::cout << "mylist2 contains:";for (int& x : mylist2) std::cout << ' ' << x;std::cout << '\n';return 0;
}
//输出：
//mylist1 contains: 0 0 0 0 0
//mylist2 contains: 100 100 100 100 100

2.1.3范围构造函数

template <class InputIterator>
list (InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());

使用迭代器范围 [first, last) 构造链表。

#include <iostream>
#include <list>int main() {std::list<int> original = {1, 2, 3, 4, 5};std::list<int> copy(original); // 使用拷贝构造函数std::cout << "copy contains:";for (int& x : copy) std::cout << ' ' << x;std::cout << '\n';return 0;
}

示例代码：

#include <iostream>
#include <list>
#include <vector>int main() {std::vector<int> vec = {1, 2, 3, 4, 5};std::list<int> mylist(vec.begin(), vec.end()); // 使用vector的迭代器范围构造链表std::cout << "mylist contains:";for (int& x : mylist) std::cout << ' ' << x;std::cout << '\n';return 0;
}
//输出：mylist contains: 1 2 3 4 5

2.1.4拷贝构造函数

list (const list& x);
list (const list& x, const allocator_type& alloc);

创建一个与现有链表 x 相同的新链表。

示例代码：

#include <iostream>
#include <list>int main() {std::list<int> original = {1, 2, 3, 4, 5};std::list<int> copy(original); // 使用拷贝构造函数std::cout << "copy contains:";for (int& x : copy) std::cout << ' ' << x;std::cout << '\n';return 0;
}
//输出：copy contains: 1 2 3 4 5

2.1.5初始化列表构造函数 

list (initializer_list<value_type> il, const allocator_type& alloc = allocator_type());

使用初始化列表 il 构造链表。

示例代码：

#include <iostream>
#include <list>int main() {std::list<int> mylist = {10, 20, 30, 40, 50}; // 使用初始化列表构造链表std::cout << "mylist contains:";for (int& x : mylist) std::cout << ' ' << x;std::cout << '\n';return 0;
}
//输出：mylist contains: 10 20 30 40 50

2.2迭代器

2.2.1 begin()

begin() 返回指向容器中第一个元素的迭代器。

2.2.2 end()

end() 返回指向容器末尾后一个位置的迭代器，这个位置不包含任何元素。

2.2.3 cbegin()

cbegin() 返回指向容器中第一个元素的常量迭代器，不能用于修改元素。

2.2.4 cend()

cend() 返回指向容器末尾后一个位置的常量迭代器，这个位置不包含任何元素，不能用于修改元素。

2.2.5 rbegin()

rbegin() 返回指向容器中最后一个元素的反向迭代器。

2.2.6 rend()

rend() 返回指向容器第一个元素前一个位置的反向迭代器，这个位置不包含任何元素。

2.2.7 crbegin()

crbegin() 返回指向容器中最后一个元素的常量反向迭代器，不能用于修改元素。

2.2.8 crend()

crend() 返回指向容器第一个元素前一个位置的常量反向迭代器，这个位置不包含任何元素，不能用于修改元素。

下面是一个示例代码，展示了这些迭代器的使用：

#include <iostream>
#include <list>int main() {std::list<int> mylist = {10, 20, 30, 40, 50};// 使用 begin() 和 end() 迭代器std::cout << "Elements using begin() and end(): ";for (auto it = mylist.begin(); it != mylist.end(); ++it) {std::cout << *it << " ";}std::cout << std::endl;// 使用 cbegin() 和 cend() 迭代器std::cout << "Elements using cbegin() and cend(): ";for (auto it = mylist.cbegin(); it != mylist.cend(); ++it) {std::cout << *it << " ";}std::cout << std::endl;// 使用 rbegin() 和 rend() 迭代器std::cout << "Elements using rbegin() and rend(): ";for (auto it = mylist.rbegin(); it != mylist.rend(); ++it) {std::cout << *it << " ";}std::cout << std::endl;// 使用 crbegin() 和 crend() 迭代器std::cout << "Elements using crbegin() and crend(): ";for (auto it = mylist.crbegin(); it != mylist.crend(); ++it) {std::cout << *it << " ";}std::cout << std::endl;return 0;
}

代码解析

  • begin() 和 end()：用于从前向后遍历并访问列表中的元素。
  • cbegin() 和 cend()：常量迭代器，用于从前向后遍历但不允许修改元素。
  • rbegin() 和 rend()：反向迭代器，用于从后向前遍历并访问列表中的元素。
  • crbegin() 和 crend()：常量反向迭代器，用于从后向前遍历但不允许修改元素。

2.3容量获取及元素访问函数

在使用 C++ 的 list 类时，容量获取和元素访问函数是非常重要的，它们可以帮助我们了解和操作容器中的元素。主要包括以下几个函数。

2.3.1 empty()

empty() 函数用于检查容器是否为空。如果容器中没有元素，则返回 true，否则返回 false。

示例代码：

#include <iostream>
#include <list>int main() {std::list<int> mylist;if (mylist.empty()) {std::cout << "The list is empty." << std::endl;} else {std::cout << "The list is not empty." << std::endl;}mylist.push_back(10);if (mylist.empty()) {std::cout << "The list is empty." << std::endl;} else {std::cout << "The list is not empty." << std::endl;}return 0;
}
//输出：
//The list is empty.
//The list is not empty.

2.3.2 size()

size() 函数返回容器中元素的数量。

示例代码：

#include <iostream>
#include <list>int main() {std::list<int> mylist = {10, 20, 30, 40, 50};std::cout << "The size of the list is: " << mylist.size() << std::endl;mylist.push_back(60);std::cout << "After adding an element, the size of the list is: " << mylist.size() << std::endl;return 0;
}
//输出：
//The size of the list is: 5
//After adding an element, the size of the list is: 6

2.3.3 front()

front() 函数返回容器中第一个元素的引用。注意，front() 不能用于空容器，否则行为是未定义的。

示例代码：

#include <iostream>
#include <list>int main() {std::list<int> mylist = {10, 20, 30};std::cout << "The first element is: " << mylist.front() << std::endl;mylist.front() = 100; // 修改第一个元素的值std::cout << "After modification, the first element is: " << mylist.front() << std::endl;return 0;
}
//输出：
//The first element is: 10
//After modification, the first element is: 100

2.3.4 back()

back() 函数返回容器中最后一个元素的引用。注意，back() 不能用于空容器，否则行为是未定义的。

示例代码：

#include <iostream>
#include <list>int main() {std::list<int> mylist = {10, 20, 30};std::cout << "The last element is: " << mylist.back() << std::endl;mylist.back() = 300; // 修改最后一个元素的值std::cout << "After modification, the last element is: " << mylist.back() << std::endl;return 0;
}
//输出：
//The last element is: 30
//After modification, the last element is: 300

2.4修改函数

C++ list 类提供了多种修改容器内容的函数。这些函数允许我们在列表中插入、删除和替换元素。下面我们将详细介绍以下修改函数，并提供示例代码展示它们的使用：

2.4.1 assign

assign 函数用于替换当前容器内容，接受多个重载版本，可以使用指定的元素、范围或初始化列表。

示例代码：

#include <iostream>
#include <list>int main() {std::list<int> mylist;mylist.assign(5, 100); // 使用5个100替换当前内容std::cout << "List after assign(5, 100): ";for (const int& x : mylist) {std::cout << x << " ";}std::cout << std::endl;std::list<int> another_list = {1, 2, 3};mylist.assign(another_list.begin(), another_list.end()); // 使用另一个list的范围替换当前内容std::cout << "List after assign from another list: ";for (const int& x : mylist) {std::cout << x << " ";}std::cout << std::endl;mylist.assign({10, 20, 30}); // 使用初始化列表替换当前内容std::cout << "List after assign({10, 20, 30}): ";for (const int& x : mylist) {std::cout << x << " ";}std::cout << std::endl;return 0;
}
// 输出：
// List after assign(5, 100): 100 100 100 100 100 
// List after assign from another list: 1 2 3 
// List after assign({10, 20, 30}): 10 20 30

2.4.2 push_front 和 pop_front

  • push_front 函数在容器开头插入一个元素。
  • pop_front 函数移除容器开头的元素。

示例代码：

#include <iostream>
#include <list>int main() {std::list<int> mylist = {20, 30};mylist.push_front(10); // 在开头插入元素10std::cout << "List after push_front(10): ";for (const int& x : mylist) {std::cout << x << " ";}std::cout << std::endl;mylist.pop_front(); // 移除开头的元素std::cout << "List after pop_front(): ";for (const int& x : mylist) {std::cout << x << " ";}std::cout << std::endl;return 0;
}
// 输出：
// List after push_front(10): 10 20 30 
// List after pop_front(): 20 30

 2.4.3 push_back 和 pop_back

  • push_back 函数在容器末尾插入一个元素。
  • pop_back 函数移除容器末尾的元素。

示例代码：

#include <iostream>
#include <list>int main() {std::list<int> mylist = {10, 20};mylist.push_back(30); // 在末尾插入元素30std::cout << "List after push_back(30): ";for (const int& x : mylist) {std::cout << x << " ";}std::cout << std::endl;mylist.pop_back(); // 移除末尾的元素std::cout << "List after pop_back(): ";for (const int& x : mylist) {std::cout << x << " ";}std::cout << std::endl;return 0;
}
// 输出：
// List after push_back(30): 10 20 30 
// List after pop_back(): 10 20

 2.4.4 insert

insert 函数用于在指定位置插入一个或多个元素，可以通过单个元素、初始化列表或迭代器范围进行插入。

示例代码：

#include <iostream>
#include <list>int main() {std::list<int> mylist = {10, 20, 30};auto it = mylist.begin();++it; // 指向第二个元素mylist.insert(it, 15); // 在第二个元素前插入15std::cout << "List after insert(15): ";for (const int& x : mylist) {std::cout << x << " ";}std::cout << std::endl;mylist.insert(it, 2, 25); // 在第二个元素前插入两个25std::cout << "List after insert(2, 25): ";for (const int& x : mylist) {std::cout << x << " ";}std::cout << std::endl;std::list<int> another_list = {1, 2, 3};mylist.insert(it, another_list.begin(), another_list.end()); // 在第二个元素前插入另一个list的范围std::cout << "List after insert from another list: ";for (const int& x : mylist) {std::cout << x << " ";}std::cout << std::endl;return 0;
}
// 输出：
// List after insert(15): 10 15 20 30 
// List after insert(2, 25): 10 25 25 15 20 30 
// List after insert from another list: 10 1 2 3 25 25 15 20 30

2.4.5 erase

erase 函数用于移除一个或多个元素，可以通过单个迭代器或迭代器范围进行删除。

示例代码：

#include <iostream>
#include <list>int main() {std::list<int> mylist = {10, 20, 30, 40, 50};auto it = mylist.begin();++it; // 指向第二个元素mylist.erase(it); // 移除第二个元素std::cout << "List after erase second element: ";for (const int& x : mylist) {std::cout << x << " ";}std::cout << std::endl;auto it1 = mylist.begin();auto it2 = mylist.end();--it2; // 指向最后一个元素mylist.erase(it1, it2); // 移除范围 [it1, it2)std::cout << "List after erase range [begin, end-1): ";for (const int& x : mylist) {std::cout << x << " ";}std::cout << std::endl;return 0;
}
// 输出：
// List after erase second element: 10 30 40 50 
// List after erase range [begin, end-1): 50

2.4.6 swap

swap 函数用于交换两个容器的内容。

示例代码：

#include <iostream>
#include <list>int main() {std::list<int> list1 = {1, 2, 3};std::list<int> list2 = {10, 20, 30};list1.swap(list2); // 交换list1和list2的内容std::cout << "List1 after swap: ";for (const int& x : list1) {std::cout << x << " ";}std::cout << std::endl;std::cout << "List2 after swap: ";for (const int& x : list2) {std::cout << x << " ";}std::cout << std::endl;return 0;
}
// 输出：
// List1 after swap: 10 20 30 
// List2 after swap: 1 2 3

2.4.7 clear

clear 函数用于移除容器中的所有元素，使其变为空容器。

示例代码：

#include <iostream>
#include <list>int main() {std::list<int> mylist = {10, 20, 30};mylist.clear(); // 清空list中的所有元素std::cout << "List after clear: ";if (mylist.empty()) {std::cout << "The list is empty." << std::endl;} else {for (const int& x : mylist) {std::cout << x << " ";}std::cout << std::endl;}return 0;
}
// 输出：
// List after clear: The list is empty.

2.5其他功能函数

除了基本的修改函数，C++ 的 list 类还提供了一些其他功能函数，这些函数可以更高效地操作链表中的元素。

2.5.1 splice

splice 函数用于将另一个 list 中的元素移到当前 list 的指定位置。splice 函数有三个重载版本：

  1. splice(iterator position, list& x)：将 x 的所有元素移动到当前 list 中 position 之前的位置。
  2. splice(iterator position, list& x, iterator i)：将 x 中的元素 i 移动到当前 list 中 position 之前的位置。
  3. splice(iterator position, list& x, iterator first, iterator last)：将 x 中 [first, last) 范围内的元素移动到当前 list 中 position 之前的位置。

示例代码：

#include <iostream>
#include <list>int main() {std::list<int> list1 = {1, 2, 3, 4, 5};std::list<int> list2 = {10, 20, 30};auto it = list1.begin();++it; // 指向第二个元素// 将list2的所有元素移动到list1中第二个元素之前list1.splice(it, list2);std::cout << "List1 after splice all elements from List2: ";for (const int& x : list1) {std::cout << x << " ";}std::cout << std::endl;std::cout << "List2 after splice all elements to List1: ";for (const int& x : list2) {std::cout << x << " ";}std::cout << std::endl;// 初始化list2list2 = {10, 20, 30};it = list1.begin();++it; // 指向第二个元素auto it2 = list2.begin();++it2; // 指向list2中的第二个元素// 将list2中的第二个元素移动到list1中第二个元素之前list1.splice(it, list2, it2);std::cout << "List1 after splice one element from List2: ";for (const int& x : list1) {std::cout << x << " ";}std::cout << std::endl;std::cout << "List2 after splice one element to List1: ";for (const int& x : list2) {std::cout << x << " ";}std::cout << std::endl;// 初始化list2list2 = {10, 20, 30};it = list1.begin();++it; // 指向第二个元素// 将list2中的第一个和第二个元素移动到list1中第二个元素之前list1.splice(it, list2, list2.begin(), ++(++list2.begin()));std::cout << "List1 after splice range from List2: ";for (const int& x : list1) {std::cout << x << " ";}std::cout << std::endl;std::cout << "List2 after splice range to List1: ";for (const int& x : list2) {std::cout << x << " ";}std::cout << std::endl;return 0;
}
// 输出：
// List1 after splice all elements from List2: 1 10 20 30 2 3 4 5
// List2 after splice all elements to List1:
// List1 after splice one element from List2: 1 20 10 20 30 2 3 4 5
// List2 after splice one element to List1: 10 30
// List1 after splice range from List2: 1 10 20 20 10 20 30 2 3 4 5
// List2 after splice range to List1: 30

2.5.2 unique

unique 函数用于移除容器中相邻的重复元素，只保留一个。它有两个重载版本：

  1. unique()：移除相邻重复的元素。
  2. unique(BinaryPredicate pred)：使用自定义的二元谓词函数来判断元素是否相邻重复。

示例代码：

#include <iostream>
#include <list>int main() {std::list<int> mylist = {10, 20, 20, 30, 30, 30, 40, 40, 50};mylist.unique(); // 移除相邻重复的元素std::cout << "List after unique(): ";for (const int& x : mylist) {std::cout << x << " ";}std::cout << std::endl;mylist = {10, 20, 21, 30, 31, 32, 40, 41, 50};// 自定义二元谓词函数，移除相邻差值小于等于1的元素mylist.unique([](int a, int b) { return std::abs(a - b) <= 1; });std::cout << "List after unique with custom predicate: ";for (const int& x : mylist) {std::cout << x << " ";}std::cout << std::endl;return 0;
}
// 输出：
// List after unique(): 10 20 30 40 50 
// List after unique with custom predicate: 10 20 30 32 40 50

3.list的模拟实现

3.1基本实现代码

#pragma once
#include <cstddef> // for size_ttemplate<class T>
struct ListNode
{T data;ListNode<T>* _next;ListNode<T>* _prev;ListNode(const T& d = T()): data(d), _next(nullptr), _prev(nullptr){}
};template<class T, class Ref, class Ptr>
struct ListIterator
{typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> Self;Node* _node;ListIterator(Node* node): _node(node){}Ref operator*(){return _node->data;}Ptr operator->(){return &_node->data;}Self& operator++(){_node = _node->_next;return *this;}Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self& operator--(){_node = _node->_prev;return *this;}Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& it) const{return _node != it._node;}bool operator==(const Self& it) const{return _node == it._node;}
};template<class T, class Ref, class Ptr>
struct ListReverseIterator
{typedef ListNode<T> Node;typedef ListReverseIterator<T, Ref, Ptr> Self;Node* _node;ListReverseIterator(Node* node): _node(node){}Ref operator*(){return _node->data;}Ptr operator->(){return &_node->data;}Self& operator++(){_node = _node->_prev;return *this;}Self operator++(int){Self tmp(*this);_node = _node->_prev;return tmp;}Self& operator--(){_node = _node->_next;return *this;}Self operator--(int){Self tmp(*this);_node = _node->_next;return tmp;}bool operator!=(const Self& it) const{return _node != it._node;}bool operator==(const Self& it) const{return _node == it._node;}
};template<class T>
class list
{
public:typedef ListNode<T> Node;typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T*> const_iterator;typedef ListReverseIterator<T, T&, T*> reverse_iterator;typedef ListReverseIterator<T, const T&, const T*> const_reverse_iterator;typedef T& reference;typedef const T& const_reference;private:Node* _head;public:list(){_head = new Node;_head->_next = _head;_head->_prev = _head;}~list(){clear();delete _head;_head = nullptr;}list(const list<T>& l){_head = new Node;_head->_next = _head;_head->_prev = _head;for (const auto& e : l){push_back(e);}}list(size_t n, const T& data = T()){_head = new Node;_head->_next = _head;_head->_prev = _head;while (n--){push_back(data);}}list<T>& operator=(const list<T>& l){if (this != &l){list<T> tmp(l);swap(tmp);}return *this;}bool empty() const{return _head->_next == _head;}size_t size() const{size_t count = 0;Node* cur = _head->_next;while (cur != _head){++count;cur = cur->_next;}return count;}reference front(){return _head->_next->data;}const_reference front() const{return _head->_next->data;}reference back(){return _head->_prev->data;}const_reference back() const{return _head->_prev->data;}iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}reverse_iterator rbegin(){return reverse_iterator(_head->_prev);}reverse_iterator rend(){return reverse_iterator(_head);}const_reverse_iterator crbegin() const{return const_reverse_iterator(_head->_prev);}const_reverse_iterator crend() const{return const_reverse_iterator(_head);}iterator insert(iterator pos, const T& data){Node* newNode = new Node(data);Node* cur = pos._node;Node* prev = cur->_prev;prev->_next = newNode;newNode->_prev = prev;newNode->_next = cur;cur->_prev = newNode;return iterator(newNode);}void push_back(const T& data){insert(end(), data);}void push_front(const T& data){insert(begin(), data);}iterator erase(iterator pos){Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;return iterator(next);}iterator erase(iterator first, iterator last){while (first != last){first = erase(first);}return last;}void pop_front(){erase(begin());}void pop_back(){erase(--end());}void swap(list<T>& l){std::swap(_head, l._head);}void clear(){Node* cur = _head->_next;while (cur != _head){Node* next = cur->_next;delete cur;cur = next;}_head->_next = _head;_head->_prev = _head;}
};

3.2 list正/反向迭代器实现

在 list 容器的模拟实现中，迭代器是一个非常重要的部分。迭代器允许我们遍历、访问和修改链表中的元素。为了支持标准库中 list 的功能，我们需要实现正向迭代器和反向迭代器。下面是对正向迭代器和反向迭代器实现的详细介绍。

3.2.1正向迭代器 (ListIterator)

ListIterator 是一个模板结构体，用于表示 list 容器的正向迭代器。它支持常见的迭代器操作，如解引用、前进、后退和比较。

定义和成员

template<class T, class Ref, class Ptr>
struct ListIterator
{typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> Self;Node* _node; // 指向当前节点的指针// 构造函数ListIterator(Node* node): _node(node){}// 解引用运算符，返回当前节点的数据Ref operator*(){return _node->data;}// 指针访问运算符，返回指向当前节点数据的指针Ptr operator->(){return &_node->data;}// 前置递增运算符，移动到下一个节点Self& operator++(){_node = _node->_next;return *this;}// 后置递增运算符，移动到下一个节点，返回旧值Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}// 前置递减运算符，移动到前一个节点Self& operator--(){_node = _node->_prev;return *this;}// 后置递减运算符，移动到前一个节点，返回旧值Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}// 不等比较运算符bool operator!=(const Self& it) const{return _node != it._node;}// 相等比较运算符bool operator==(const Self& it) const{return _node == it._node;}
};

3.2.2反向迭代器 (ListReverseIterator)

ListReverseIterator 是一个模板结构体，用于表示 list 容器的反向迭代器。反向迭代器允许我们从后向前遍历容器。

定义和成员

template<class T, class Ref, class Ptr>
struct ListReverseIterator
{typedef ListNode<T> Node;typedef ListReverseIterator<T, Ref, Ptr> Self;Node* _node; // 指向当前节点的指针// 构造函数ListReverseIterator(Node* node): _node(node){}// 解引用运算符，返回当前节点的数据Ref operator*(){return _node->data;}// 指针访问运算符，返回指向当前节点数据的指针Ptr operator->(){return &_node->data;}// 前置递增运算符，移动到前一个节点Self& operator++(){_node = _node->_prev;return *this;}// 后置递增运算符，移动到前一个节点，返回旧值Self operator++(int){Self tmp(*this);_node = _node->_prev;return tmp;}// 前置递减运算符，移动到下一个节点Self& operator--(){_node = _node->_next;return *this;}// 后置递减运算符，移动到下一个节点，返回旧值Self operator--(int){Self tmp(*this);_node = _node->_next;return tmp;}// 不等比较运算符bool operator!=(const Self& it) const{return _node != it._node;}// 相等比较运算符bool operator==(const Self& it) const{return _node == it._node;}
};

4.list与vector的比较

list 和 vector 是 C++ 标准模板库（STL）中两个常用的序列容器，它们在内部实现、使用场景和性能方面都有显著差异。下面将详细介绍 list 和 vector 的比较，从以下几个方面进行探讨：

4.1 内部实现

  • list：list 是一种双向链表，每个节点包含一个数据元素以及指向前一个和后一个节点的指针。它的实现基于动态分配的节点，节点通过指针相互连接。
  • vector：vector 是一种动态数组，底层实现为一个连续的内存块。它通过动态调整大小来适应插入和删除操作。

4.2 存储方式

  • list：存储的元素不连续，每个元素通过指针连接到前一个和后一个元素。由于链表节点是分散存储的，因此元素的物理位置在内存中不是连续的。
  • vector：存储的元素是连续的，这意味着 vector 的元素在内存中是紧挨着的。这样有利于缓存的利用，访问速度较快。

4.3 访问和遍历

  • list：访问任意位置的元素需要线性时间复杂度 (O(n))，因为必须从链表的头部或尾部开始遍历到目标位置。list 支持双向迭代。
  • vector：可以在常数时间内 (O(1)) 通过索引直接访问任意位置的元素。vector 支持随机访问和双向迭代。

4.4 插入和删除操作

  • list：在任意位置插入或删除元素的时间复杂度为常数时间 (O(1))，只需调整指针。然而，找到插入或删除位置可能需要线性时间。
  • vector：在末尾插入或删除元素的时间复杂度为常数时间 (O(1))，但是在中间位置插入或删除元素的时间复杂度为线性时间 (O(n))，因为需要移动其他元素以保持连续性。

4.5 内存管理

  • list：每个元素都需要额外的内存来存储前后指针，因此内存开销较大。链表节点是分散分配的，适合频繁的插入和删除操作。
  • vector：当需要增加容量时，vector 会重新分配一块更大的内存，并将现有元素复制到新位置，这可能涉及大量的元素移动。为了减少内存重新分配的频率，vector 通常会预留比实际需要更多的内存。

4.6 使用场景

  • list：

    • 适用于频繁在中间插入或删除元素的场景。
    • 不需要随机访问，只需顺序访问的场景。
    • 内存管理分散，不需要连续内存的场景。

  • vector：

    • 适用于需要频繁随机访问元素的场景。
    • 在末尾进行插入或删除操作较多的场景。
    • 数据量较小，不需要频繁调整大小的场景。

示例代码比较

下面的代码展示了 list 和 vector 在插入、删除和访问操作上的不同：

#include <iostream>
#include <list>
#include <vector>int main() {// list 示例std::list<int> myList = {10, 20, 30, 40, 50};auto it = myList.begin();++it;myList.insert(it, 15); // 在第二个位置插入15myList.erase(it);      // 删除第二个位置元素std::cout << "List elements: ";for (auto elem : myList) {std::cout << elem << " ";}std::cout << std::endl;// vector 示例std::vector<int> myVector = {10, 20, 30, 40, 50};myVector.insert(myVector.begin() + 1, 15); // 在第二个位置插入15myVector.erase(myVector.begin() + 1);      // 删除第二个位置元素std::cout << "Vector elements: ";for (auto elem : myVector) {std::cout << elem << " ";}std::cout << std::endl;// 访问元素std::cout << "List element at position 2: " << *std::next(myList.begin(), 2) << std::endl;std::cout << "Vector element at position 2: " << myVector[2] << std::endl;return 0;
}
// 输出：
// List elements: 10 15 30 40 50
// Vector elements: 10 20 30 40 50
// List element at position 2: 30
// Vector element at position 2: 30

5.结语

通过这篇文章，我们深入探讨了 C++ 标准模板库中的 list 类，包括其构造函数、迭代器、容量获取与元素访问函数、修改函数及其他功能函数。我们还实现了一个简单的 list 模拟，并详细比较了 list 与 vector 的异同。希望通过这些内容，读者能够更全面地理解 list 的使用场景和实现原理，从而在实际编程中做出更加合理的数据结构选择，提高代码的效率和性能。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/335930.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

100个 Unity小游戏系列四 -Unity 抽奖游戏专题二 水果机游戏

100个 Unity小游戏系列四 -Unity 抽奖游戏专题二 水果机游戏

一、演示效果 二、知识点 2.1 布局 private void CreateItems(){for (int i 0; i < rewardDatas.Length; i){var reward_data rewardDatas[i];GameObject fruitOjb;if (i < itemRoot.childCount){fruitOjb itemRoot.GetChild(i).gameObject;}else{fruitOjb Instant…
阅读更多...
MATLAB分类与判别模型算法： 快速近邻法（FastNN）分类程序【含Matlab源码 MX_005期】

MATLAB分类与判别模型算法： 快速近邻法（FastNN）分类程序【含Matlab源码 MX_005期】

算法思路介绍&#xff1a; 1. 数据准备阶段&#xff1a; 生成一个合成数据集 X&#xff0c;其中包含三个簇&#xff0c;每个簇分布在不同的区域。 定义聚类层数 L 和每个层次的子集数量 l。 2. 聚类阶段&#xff1a; 使用K均值聚类算法将初始数据集 X 分成 l 个簇。…
阅读更多...
mac m1安装homebrew管理工具（brew命令）完整流程

mac m1安装homebrew管理工具（brew命令）完整流程

背景 因为mac上的brew很久没用了&#xff0c;版本非常旧&#xff0c;随着mac os的更新&#xff0c;本机的homebrew大部分的功能都无法使用&#xff0c;幸好过去通过brew安装的工具比较少&#xff0c;于是决定重新安装一遍brew。 卸载旧版brew 法一&#xff1a;通过使用线上…
阅读更多...
【PB案例学习笔记】-13 徒手做个电子时钟

【PB案例学习笔记】-13 徒手做个电子时钟

写在前面 这是PB案例学习笔记系列文章的第11篇&#xff0c;该系列文章适合具有一定PB基础的读者。 通过一个个由浅入深的编程实战案例学习&#xff0c;提高编程技巧&#xff0c;以保证小伙伴们能应付公司的各种开发需求。 文章中设计到的源码&#xff0c;小凡都上传到了gite…
阅读更多...
渗透测试工具Cobalt strike-2.CS基础使用

渗透测试工具Cobalt strike-2.CS基础使用

三、结合metasploit,反弹shell 在kali中开启使用命令开启metasploit msfconsole ┌──(root㉿oldboy)-[~] └─# msfconsole --- msf6 > use exploit/multi/handler [*] Using configured payload generic/shell_reverse_tcp --- msf6 exploit(multi/handler) > show …
阅读更多...
【5.基础知识和程序编译及调试】

【5.基础知识和程序编译及调试】

一、GCC概述&#xff1a;是GUN推出的多平台编译器&#xff0c;可将C/C源程序编译成可执行文件。编译流程分为以下四个步骤&#xff1a; 1、预处理 2、编译 3、汇编 4、链接 注&#xff1a;编译器根据程序的扩展名来分辨编写源程序所用的语言。根据不同的后缀名对他们进行相…
阅读更多...
058.最后一个单词的长度

058.最后一个单词的长度

题意 给你一个字符串 s&#xff0c;由若干单词组成&#xff0c;单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。 单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。 难度 简单 示例 1&#xff1a; 输入&#xff1a;s "Hello World" 输…
阅读更多...
excel表格里怎样不删除0，又不显示0呢？

excel表格里怎样不删除0，又不显示0呢？

在单元格里不显示0&#xff0c;大体上有这么几种方法&#xff1a; 1.设置单元格自定义格式 选中数据区域&#xff0c;鼠标右键&#xff0c;点一下设置单元格格式&#xff0c;选中数字&#xff0c;自定义&#xff0c;在右侧的类型栏&#xff0c;设置格式&#xff1a; [0]&quo…
阅读更多...
android11禁止进入屏保和自动休眠

android11禁止进入屏保和自动休眠

应某些客户要求&#xff0c;关闭了开机进入屏保&#xff0c;一段时间会休眠的问题。以下diff可供参考&#xff1a; diff --git a/overlay/frameworks/base/packages/SettingsProvider/res/values/defaults.xml b/overlay/frameworks/base/packages/SettingsProvider/res/value…
阅读更多...
《微服务王国的守护者：Spring Cloud Dubbo的奇幻冒险》

《微服务王国的守护者：Spring Cloud Dubbo的奇幻冒险》

5. 经典问题与解决方案 5.3 服务追踪与链路监控 在微服务架构的广袤宇宙中&#xff0c;服务间的调用关系错综复杂&#xff0c;如同一张庞大的星系网络。当一个请求穿越这个星系&#xff0c;经过多个服务节点时&#xff0c;如何追踪它的路径&#xff0c;如何监控整个链路的健康…
阅读更多...
ssm校园疫情防控管理系统-计算机毕业设计源码30796

ssm校园疫情防控管理系统-计算机毕业设计源码30796

目 录 摘要 1 绪论 1.1目的及意义 1.2开发现状 1.3ssm框架介绍 1.3论文结构与章节安排 2 校园疫情防控管理系统系统分析 2.1 可行性分析 2.2 系统流程分析 2.2.1 数据流程 3.3.2 业务流程 2.3 系统功能分析 2.3.1 功能性分析 2.3.2 非功能性分析 2.4 系统用例分…
阅读更多...
手摸手教你uniapp原生插件开发

手摸手教你uniapp原生插件开发

行有余力,心无恐惧 这篇技术文章写了得有两三个礼拜,虽然最近各种事情,工作上的生活上的,但是感觉还是有很多时间被浪费.还记得几年前曾经有一段时间7点多起床运动,然后工作学习,看书提升认知.现在我都要佩服那会儿的自己.如果想回到那种状态,我觉得需要有三个重要的条件. 其…
阅读更多...
[ C++ ] 深入理解模板( 初 阶 )

[ C++ ] 深入理解模板( 初 阶 )

函数模板 函数模板格式 template <typename T1, typename T2,......,typename Tn> 返回值类型 函数名(参数列表){} 注意&#xff1a; typename是用来定义模板参数关键字&#xff0c;也可以使用class(切记&#xff1a;不能使用struct代替class) 函数模板的实例化 模板参数…
阅读更多...
Simulink从0搭建模型07-P8for循环的使用

Simulink从0搭建模型07-P8for循环的使用

Simulink从0搭建模型07-P8for循环的使用 今日学习内容1. For Iterator Subsystem模块介绍1.1. 累加器1.2. For Iterator1.3.小结 2. states介绍3. Set next i&#xff08;相当break)学习心得 今日学习内容 b站视频 【Simulink 0基础入门教程 P8 for循环的使用 For Itrator Sub…
阅读更多...
前端中 dayjs 时间的插件使用(在vue 项目中)

前端中 dayjs 时间的插件使用(在vue 项目中)

Day.js中文网 这是dayjs的中文文档 里面包括了使用方法 下面我来详细介绍一下这个插件的使用 Day.js 可以运行在浏览器和 Node.js 中。 一般咱直接是 npm 安装 npm install dayjs 目前应该使用的是Es6 的语法 import dayjs from dayjs 当前时间 直接调用 dayjs() 将返回…
阅读更多...
组件的传参等

组件的传参等

一:组件的生命周期函数 组件的生命周期函数: created只是创建了组件内的实例对象 attached,给组件实例绑定了属性,绑定到页面节点树之后 ready准备好渲染之后,还未渲染之前 moved组件实例被移动到另一个位置后执行 detached在整个组件被被移除执行 error执行的时候,组件内…
阅读更多...
乡村振兴的乡村产业创新发展：培育乡村新兴产业，打造乡村产业新名片，促进乡村经济多元化发展

乡村振兴的乡村产业创新发展：培育乡村新兴产业，打造乡村产业新名片，促进乡村经济多元化发展

目录 一、引言 二、乡村产业创新发展的必要性 &#xff08;一&#xff09;适应新时代发展要求 &#xff08;二&#xff09;满足消费升级需求 &#xff08;三&#xff09;促进农民增收致富 三、培育乡村新兴产业策略 &#xff08;一&#xff09;加强科技创新引领 &#…
阅读更多...
在WHM中如何调整max_upload_size 参数大小

在WHM中如何调整max_upload_size 参数大小

今日我们在搭建新网站时需要调整一下PHP参数max_upload_size 的大小&#xff0c;我们公司使用的Hostease的美国独立服务器产品默认5个IP地址&#xff0c;也购买了cPanel面板&#xff0c;因此联系Hostease的技术支持&#xff0c;寻求帮助了解到如何在WHM中调整PHP参数&#xff0…
阅读更多...
Go语言GoFly框架快速新增接口/上手写代码

Go语言GoFly框架快速新增接口/上手写代码

拿到一个新框架大家可能无从下手&#xff0c;因为你对框架设计思路、结构不了解&#xff0c;从而产生恐惧&#xff0c;所以我们框架是通过简单可视化界面安装&#xff0c;安装后即可看到效果&#xff0c;然后点击先点点看各个功能&#xff0c;看现有的功能是怎么写的&#xff0…
阅读更多...
云原生架构内涵_3.主要架构模式

云原生架构内涵_3.主要架构模式

云原生架构有非常多的架构模式&#xff0c;这里列举一些对应用收益更大的主要架构模式&#xff0c;如服务化架构模式、Mesh化架构模式、Serverless模式、存储计算分离模式、分布式事务模式、可观测架构、事件驱动架构等。 1.服务化架构模式 服务化架构是云时代构建云原生应用的…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023