马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
x
1. list的先容和利用
1.1 list的先容
- list是可以在常数范围内涵任意位置进行插入和删除的序列式容器，而且该容器可从前后双向迭代。
- list底层是双向链表布局，双向链表中每个元素存储在互不相干的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
- 与其他序列式容器相比，list通常在任意位置插入、移除元素的效率更好。
- 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问。好比：要访问list的第6个元素，必须从已知的位置（头和尾）一步步走到该位置；list还必要一些额外空间，以生存每个节点的相干联信息。
1.2 list的利用
1.2.1 list的构造
- #include <list>
- // 默认构造函数
- std::list<int> defaultList;
- // 通过值初始化列表
- std::list<int> valueList = {1, 2, 3, 4, 5};
- // 通过大小和默认值初始化列表
- std::list<int> sizeValueList(3, 1); // 包含三个元素，每个元素的值都是1
- // 通过范围初始化列表
- int arr[] = {10, 20, 30, 40, 50};
- std::list<int> rangeList(arr, arr + sizeof(arr) / sizeof(arr[0]));
- // 复制构造函数
- std::list<int> copyList = valueList;
- // 移动构造函数（C++11及以后）
- std::list<int> moveList = std::move(valueList);
1. front()：返回对列表第一个元素的引用
- std::list<int> myList = {1, 2, 3, 4, 5};
- int firstElement = myList.front(); // firstElement is 1
- int lastElement = myList.back(); // lastElement is 5
- int elementAtTwo = myList[2]; // elementAtTwo is 3
push_front(const T& value) ：在列表的开头添加一个新元素。
push_back(const T& value) ：在列表的末端添加一个新元素。
pop_front() ：移除列表的第一个元素。
pop_back() ：移除列表的最后一个元素。
insert(iterator pos, const T& value) ：在指定位置插入一个新元素。
- auto it = myList.begin();
- advance(it, 2); // 移动到第三个元素的位置
- myList.insert(it, 15); // 在第三个元素的位置插入 15
- myList.insert(myList.begin() + 3, 15);
erase(iterator pos) ：移除指定位置的元素。
- auto it = myList.begin();
- advance(it, 2); // 移动到第三个元素的位置
- myList.erase(it); // 移除第三个元素
好比说size()，capacity()等。
在C++尺度库中，std::merge 是一个用于归并两个已排序范围的算法。它位于 <algorithm> 头文件中，而且可以用于各种容器（如 vector, list, deque 等）。std::merge 的主要作用是将两个已排序的序列归并成一个新的已排序序列。
输入必须是已排序的：std::merge 假设输入的两个范围已经按升序或降序分列。假如输入未排序，则结果将是未界说的。
std::remove 和 std::remove_if 是用于从序列中移除元素的算法。它们并不直接删除元素，而是将不必要的元素移动到序列的末端，并返回一个指向新序列末端（即最后一个未被移除的元素之后的位置）的迭代器。实际的删除操纵通常必要结合容器的 erase 方法来完成。
- #include <iostream>
- #include <list>
- #include <algorithm> // 包含 std::remove
- using namespace std;
- void test_remove()
- {
- int array[] = {1, 2, 3, 4, 5, 3, 6};
- list<int> l(array, array + 7);
- cout << "Original list: ";
- for (const auto& elem : l)
- {
- cout << elem << " ";
- }
- cout << endl;
- // 使用 std::remove 将值为 3 的元素移到末尾
- l.erase(std::remove(l.begin(), l.end(), 3), l.end());
- cout << "List after removing 3: ";
- for (const auto& elem : l)
- {
- cout << elem << " ";
- }
- cout << endl;
- }
- int main()
- {
- test2();
- test_remove();
- return 0;
- }
利用 erase 删除从 new_end 到列表末端的所有元素，即删除所有 3。
这样，只需调用一次 erase 就能删除所有 3。
1.2.5 迭代器失效
因为list的底层布局为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在被删除时才会失效，而且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
- #include <iostream>
- #include <list>
- void test()
- {
- int array[] = {1, 2, 3, 4, 5};
- std::list<int> l(array, array + 5);
- auto it = l.begin();
- while (it != l.end())
- {
- std::cout << "Deleting element: " << *it << std::endl;
- auto next_it = l.erase(it); // erase 返回下一个有效的迭代器
- std::cout << "Iterator after erase: " << (next_it == l.end() ? "end" : std::to_string(*next_it)) << std::endl;
- it = next_it;
- }
- std::cout << "List after deletion: ";
- for (const auto& elem : l)
- {
- std::cout << elem << " ";
- }
- std::cout << std::endl;
- }
- int main()
- {
- test();
- return 0;
- }
- Deleting element: 1
- Iterator after erase: 2
- Deleting element: 2
- Iterator after erase: 3
- Deleting element: 3
- Iterator after erase: 4
- Deleting element: 4
- Iterator after erase: 5
- Deleting element: 5
- Iterator after erase: end
- List after deletion:
- void test()
- {
- int array[] = {1, 2, 3, 4, 5};
- list<int> l(array, array + 5);
- auto it = l.begin();
- while (it != l.end())
- {
- l.erase(it);
- ++it；
- }
- }
- void test()
- {
- int array[] = {1, 2, 3, 4, 5};
- list<int> l(array, array + 5);
- auto it = l.begin();
- while (it != l.end())
- {
- it = l.erase(it); // erase 返回下一个有效的迭代器
- }
- }
迭代器按性子分类，由容器底层布局决定。
可以读取和写入数据，支持多次遍历，但只能单向进步。
支持的操纵：输入迭代器和输出迭代器的所有操纵，以及多次遍历。
- 双向迭代器（Bidirectional Iterator）
在前向迭代器的基础上增加了反向遍历的本领。
支持的操纵：前向迭代器的所有操纵，以及--（前缀和后缀）。
- 随机访问迭代器（Random Access Iterator）
支持任意位置的访问，可以进行算术运算（如+, -），而且可以比力巨细。
支持的操纵：双向迭代器的所有操纵，以及[]，+, -，<, >, <=, >=。
按功能从弱到强分列如下：
- 输入迭代器（Input Iterator）
- 输出迭代器（Output Iterator）
- 前向迭代器（Forward Iterator）
- 双向迭代器（Bidirectional Iterator）
- 随机访问迭代器（Random Access Iterator）
好比说 sort 函数利用的就是随机迭代器，我们这节讲的 list 就不能调用它，因为list利用的是双向迭代器。
在C++尺度库中，不同容器支持不同范例的迭代器：
- std::list：利用双向迭代器，支持前向和后向遍历。
- std::vector 和 std::deque、std::string：利用随机访问迭代器，支持任意位置的访问和高效的算术运算。
- std::forward_list：利用前向迭代器，仅支持单向遍历。
- std::set, std::map, std::multiset, std::multimap：利用双向迭代器。
- std::unordered_set, std::unordered_map, std::unordered_multiset, std::unordered_multimap：利用前向迭代器。
层级低的容器不能访问层级高的函数。层级高的容器可以访问层级低的函数。好比：vector和string就可以调用reverse（双向）。
详细的函数属于什么层级可以在文档中查找。
2. list的模仿实现
2.1 开端实现
- namespace zzy
- {
- template<class T>
- struct list_node//为什么这里写它？
- {
- list_node<T>* _next;
- list_node<T>* _prev;
- T _val;
- explicit list_node(const T& val = T())
- :_next(nullptr)
- ,_prev(nullptr)
- ,_val(val)
- {}
- };
-
- template<class T>
- class list
- {
- typedef list_node<T> Node;
- public:
- list()
- {
- _head = new Node;
- _head->_prev = _head;
- _head->_next = _head;
- _size = 0;
- }
- void push_back(const T& x)
- {
- Node* tail = _head->_prev;
- Node* newnode = new Node(x);
- tail->_next = newnode;
- newnode->_prev = tail;
-
- newnode->_next = _head;
- _head->_prev = newnode;
- }
- private:
- Node* _head;
- size_t _size;
- };
- }
- list_node，为什么这里写它？后面再 typedef 成 Node：
因为在zzy的定名空间下，别的容器的结点也要用 Node 这个名字，假如这里列表的结点写成了Node，别的容器利用时会有定名冲突。以是在后面的list类中再typedef成Node，便于区分的同时也更方便。
2.2 list迭代器
在namespace中还要加上list迭代器：
- template<class T>
- struct _list_iterator
- {
- typedef list_node<T> Node;
- Node* _node;
- explicit _list_iterator(Node* node)
- :_node(node)
- {}
- T& operator*()
- {
- return _node->_val;
- }
- _list_iterator<T>& operator++()
- {
- _node = _node->_next;
- return *this;
- }
- bool operator!=(const _list_iterator<T>& it) const
- {
- return _node != it._node;
- }
- };
- 构造函数：初始化迭代器，指向给定的节点。
- 解引用操纵符 operator*：返回当前节点存储的值。
- 前缀自增操纵符 operator++：将迭代器移动到下一个节点，并返回自身。
- 不等比力操纵符 operator!=：比力两个迭代器是否指向不同的节点。
- 为什么 const _list_iterator<T>& it 要写const
不加const会报错，因为end() 函数通常返回一个表现链表末端的迭代器，这个迭代器是一个临时对象（具有常性）。假如你倒霉用 const 修饰符，编译器将不允许你将这个临时对象绑定到非 const 引用上。
与此同时，list类中public更新为：
- public:
- typedef _list_iterator<T> iterator;
- iterator begin()
- {
- return iterator(_head->_next);
- }
- iterator end()
- {
- return iterator(_head);
- }
我们期望的是指向的内容不能修改，不是指针本身不能修改，指针本身还得++才能遍历列表。
上面这种是允许修改返回值的，很少用。
这个是以const T& 返回，返回值范例是 const T&，返回值不能修改。
假如我们只是复制一下普通迭代器的实现，只是修改成上面这种*重载，其余都稳固，未免太过冗余，于是我们想到了可以在模板中增加参数，一种只用来控制返回范例不同的参数
- public:
- typedef _list_iterator<T, T&> iterator;
- typedef _list_iterator<T, const T&> const_iterator;
- template<class T, class Ref>
- struct _list_iterator
- {
- typedef list_node<T> Node;
- typedef _list_iterator<T, Ref> self;
- Node* _node;
- explicit _list_iterator(Node* node)
- :_node(node)
- {}
- Ref operator*()
- {
- return _node->_val;
- }
- 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;
- }
- };
Ref 的作用：
Ref 用于界说解引用操纵符 operator*() 返回的范例。详细来说：
- 假如 Ref 是 T&（即 T 的引用），那么 operator*() 将返回当前节点存储的值的引用。
- 假如 Ref 是 T（即 T 的值），那么 operator*() 将返回当前节点存储的值的副本。
通过这种方式，_list_iterator 可以支持不同范例的迭代器，例如：
- 普通迭代器：返回引用 (T&)，允许修改元素。
- 常量迭代器：返回常量引用 (const T&)，不允许修改元素。
- void test_list()
- {
- list<A> lt;
- lt.push_back(A(1));
- lt.push_back(A(2));
- lt.push_back(A(3));
- list<A>::iterator it = lt.begin();
- while (it != lt.end())
- {
- cout << (*it)._a << endl;
- cout << it->_val._a << endl;
- ++it;
- }
- cout << endl;
- }
由于普通和const迭代器各必要一个不同的返回范例的-> 的重载：
- template<class T, class Ref = T&, class Ptr>
- struct _list_iterator
- {
- typedef list_node<T> Node;
- typedef _list_iterator<T, Ref, Ptr> self;
- Node* _node;
-
- ...
- Ptr operator->() const
- {
- return &_node->_val;
- }
- };
- public:
- typedef _list_iterator<T, T&, T*> iterator;
- typedef _list_iterator<T, const T&, const T*> const_iterator;
- iterator insert(iterator pos, const T& x)
- {
- Node* cur = pos._node;
- Node* prev = cur->_prev;
- Node* newnode = new Node(x);
- prev->_next = newnode;
- newnode->_next = cur;
- cur->_prev = newnode;
- newnode->_prev = prev;
- ++size;
- return newnode;
- }
- iterator erase(iterator pos)
- {
- assert(pos != end());
-
- Node* cur = pos._node;
- Node* prev = cur->_prev;
- Node* next = cur->_next;
-
- prev->_next = next;
- next->_prev = prev;
-
- delete cur;
- --size;
- return next;
- }
- void clear()
- {
- iterator it = begin();
- while (it != end())
- {
- it = erase(it);
- }
- _size = 0;
- }
- size_t size() const
- {
- return _size;
- }
- ~list()
- {
- clear();
- delete _head;
- _head = nullptr;
- }
- list(const list<T>& lt)
- {
- _head = new Node;
- _head->_prev = _head;
- _head->_next = _head;
- _size = 0;
- for(auto& e : lt)
- {
- push_back(e);
- }
- }
- void swap(list<T>& lt)
- {
- std::swap(_head, lt._head);
- std::swap(_size, lt._size);
- }
- list<T>& operator=(const list<T>& lt)
- {
- swap(lt);
- return *this;
- }
3. list与vector的对比
| vector | list | | 底层布局 | 动态次序表，一段连续空间 | 带头结点的双向循环链表 | | 随机访问 | 支持，访问效率为O(1) | 不支持，访问某个效率为O(N) | | 插入删除 | 任意位置插删效率低 | 效率高，不必要搬移元素，O(1) | | 空间利用率 | 不易造成内存碎片，空间利用率高 | 小结点易造成内存碎片 | | 迭代器 | 原生指针 | 对指针进行封装 | | 迭代器失效 | 插入可能导致扩容，导致失效
删除时需重新赋值否则失效
| 插入时不会导致迭代器失效
删除时，只会导致当前迭代器失效
| | 利用场景 | 必要高效存储，支持随机访问
不关心插入删除效率
| 大量删除和插入操纵
不关心随机访问
|
3.1 容器与迭代器
假如我们想在3前面插入一个值，但是我们发现list和vector都没有提供find，该怎么考虑呢？
首先我们应该意识到：C++通过迭代器将容器与算法连接起来了。迭代器提供了统一的方法访问容器，却不必要关注容器的底层实现。
在vector中，begin指向第一个元素，end指向最后一个数据的下一个位置。在list中，由于list是带头双向循环链表，begin指向的是第一个数据（头节点的下一个节点），而end则指向头结点。在list中，不能用 it < c.end()，在遍历 std::list 时，应该利用 != 来比力迭代器是否到达容器的末端，因为在list中地点巨细关系是不一定的。
在 C++ 尺度库中， std::list 和 std::vector 都没有直接提供 find 成员函数。原因在于：
- 通用算法与容器分离：C++ 尺度库接纳了一种设计哲学，将算法与容器分离。算法被设计为独立于容器的函数，这样可以提高算法的复用性。例如， std::find 是一个通用算法，可以应用于任何支持迭代器的容器，包罗 std::list、std::vector、std::array 等。
- 克制重复：假如每个容器都提供自己的 find 方法，那么就会有很多重复的代码。通过将算法作为独立的函数，可以克制这种重复，同时保持代码的简洁性和划一性。
3.2 排序效率
在C++中，选择合适的容器对于步伐的性能和效率至关重要。std::list 和 std::vector 是两种常用的容器，但它们在不同操纵上的表现差别很大。以下是为什么在必要排序时，std::list 不如 std::vector 合适的原因：
1. 排序算法的实现
std::vector 支持随机访问迭代器，这意味着可以高效地进行索引访问和算术运算。尺度库中的排序算法（如 std::sort）依靠于随机访问迭代器来实现高效的排序算法（通常是快速排序或归并排序），这些算法的时间复杂度为 O(n log n)。
std::list 只支持双向迭代器，不支持随机访问迭代器。
因此，尺度库中的 std::sort 不能直接用于 std::list。虽然 std::list 提供了 std::list::sort 成员函数，但它的时间复杂度通常较高（O(n log n)，但在某些环境下可能更差），而且由于 std::list 的链表布局，元素之间的比力和交换操纵也较为低效。
2. 内存布局与缓存友好性
std::vector 是连续内存分配的，这使得它在现代CPU上具有更好的缓存局部性，从而提高了访问速度。
连续内存布局也有助于减少页面错误和提高内存带宽利用率。
std::list 是由节点组成的链表，每个节点都可能分散在不同的内存位置。
这种非连续的内存布局导致较差的缓存局部性，增加了内存访问的延迟。
4. 实际应用场景
假如你必要对大量数据进行排序，而且不必要频仍的插入和删除操纵，std::vector 是更好的选择。
它提供了更好的性能和更高的代码可读性。
假如你必要频仍地在列表中心插入和删除元素，而且不必要高效的排序操纵，std::list 可能更得当。
但在必要排序的环境下，std::list 的性能劣势明显。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
