09.list
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));
// 复制构造函数
std::list<int> copyList = valueList;
// 移动构造函数（C++11及以后）
std::list<int> moveList = std::move(valueList);
1.2.2 list 访问元素
1. front()：返回对列表第一个元素的引用
std::list<int> myList = {1, 2, 3, 4, 5};
int firstElement = myList.front(); // firstElement is 1
2. back()：返回对列表最后一个元素的引用
int lastElement = myList.back(); // lastElement is 5
3. operator[]：通过索引访问元素，但请留意，std::list 不像 std::vector 或 std::array 那样提供随机访问。这个操纵实际上会从 begin() 开始遍历列表直到到达指定位置，因此效率较低。
int elementAtTwo = myList; // elementAtTwo is 3
1.2.3 list增删查改
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
留意：头插头删，尾插尾删的效率都很高。string以后插入开始利用迭代器位置，string用的是下标。list假如想在第3个位置插入元素，不能写成：
myList.insert(myList.begin() + 3, 15);
因为空间不是连续的。
erase(iterator pos) ：移除指定位置的元素。
auto it = myList.begin();
advance(it, 2); // 移动到第三个元素的位置
myList.erase(it); // 移除第三个元素
1.2.4 其他
好比说size()，capacity()等。
[*]merge()
在C++尺度库中，std::merge 是一个用于归并两个已排序范围的算法。它位于 <algorithm> 头文件中，而且可以用于各种容器（如 vector, list, deque 等）。std::merge 的主要作用是将两个已排序的序列归并成一个新的已排序序列。
输入必须是已排序的：std::merge 假设输入的两个范围已经按升序或降序分列。假如输入未排序，则结果将是未界说的。
[*]remove
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;
}
利用 std::remove 将所有 3 移动到列表末端，并返回新的末端迭代器 new_end。
利用 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；
}
} erase函数实行后，it所指向的节点已经被删除，因此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 返回下一个有效的迭代器
}
} 1.3 迭代器的分类
迭代器按性子分类，由容器底层布局决定。
[*]前向迭代器（Forward Iterator）
可以读取和写入数据，支持多次遍历，但只能单向进步。
支持的操纵：输入迭代器和输出迭代器的所有操纵，以及多次遍历。
[*]双向迭代器（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;
}
}; 这段C++代码界说了一个模板类 _list_iterator，用于实现双向链表的迭代器。主要功能如下：
[*]构造函数：初始化迭代器，指向给定的节点。
[*]解引用操纵符 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);
} 2.3 const迭代器
我们期望的是指向的内容不能修改，不是指针本身不能修改，指针本身还得++才能遍历列表。
T& operator*() const 上面这种是允许修改返回值的，很少用。
const T& operator*() 这个是以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 是 _list_iterator 模板类的第二个模板参数。
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;
} C语言中的scanf和printf可以针对内置范例，但是自界说范例打印仍必要流插入重载。
由于普通和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; 2.4 其他成员函数
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的对比
vectorlist底层布局动态次序表，一段连续空间带头结点的双向循环链表随机访问支持，访问效率为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::vector 支持随机访问迭代器，这意味着可以高效地进行索引访问和算术运算。尺度库中的排序算法（如 std::sort）依靠于随机访问迭代器来实现高效的排序算法（通常是快速排序或归并排序），这些算法的时间复杂度为 O(n log n)。
[*]std::list：
std::list 只支持双向迭代器，不支持随机访问迭代器。
因此，尺度库中的 std::sort 不能直接用于 std::list。虽然 std::list 提供了 std::list::sort 成员函数，但它的时间复杂度通常较高（O(n log n)，但在某些环境下可能更差），而且由于 std::list 的链表布局，元素之间的比力和交换操纵也较为低效。
2. 内存布局与缓存友好性
[*]std::vector：
std::vector 是连续内存分配的，这使得它在现代CPU上具有更好的缓存局部性，从而提高了访问速度。
连续内存布局也有助于减少页面错误和提高内存带宽利用率。
[*]std::list：
std::list 是由节点组成的链表，每个节点都可能分散在不同的内存位置。
这种非连续的内存布局导致较差的缓存局部性，增加了内存访问的延迟。
4. 实际应用场景
[*]std::vector：
假如你必要对大量数据进行排序，而且不必要频仍的插入和删除操纵，std::vector 是更好的选择。
它提供了更好的性能和更高的代码可读性。
[*]std::list：
假如你必要频仍地在列表中心插入和删除元素，而且不必要高效的排序操纵，std::list 可能更得当。
但在必要排序的环境下，std::list 的性能劣势明显。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]