C++的顺序容器类型和相关操作总结

顺序容器类型

C++ 标准库提供了一组顺序容器，用于存储和管理元素的集合。以下是 C++ 中常用的顺序容器：

vector (向量)

• std::vector 是一个动态数组，支持快速随机访问。
• 元素存储在连续的内存位置中，支持动态增长和缩减大小。
• 常用于需要频繁访问元素，但较少进行插入和删除操作的场景。

deque (双端队列)

• std::deque 支持在两端快速插入和删除元素。
• 可能不是连续存储的，但仍然支持快速随机访问。
• 适合于需要在两端添加或移除元素的场景。

list (双向链表)

• std::list 是一个双向链表，支持在任何位置快速插入和删除元素。
• 不支持快速随机访问，适合于元素经常在中间插入或删除的场景。

forward_list (单向链表)

• std::forward_list 是一个单向链表，每个元素只有一个指向下一个元素的指针。
• 占用空间少，但只能向前遍历。
• 适合于只需要单向遍历且关注内存使用的场景。

array (固定大小数组)

• std::array 是一个固定大小的数组，大小在编译时确定。
• 支持快速随机访问，元素存储在连续内存位置中。
• 适合于已知元素数量且数量不变的场景。

string (字符串)

• std::string 专门用于存储和操作字符串的容器。
• 提供了丰富的成员函数来处理字符串，如拼接、查找、替换等操作。
• 实际上是 std::basic_string<char> 的特化版本，可以动态增长和缩减。

顺序容器操作

添加元素的操作

push_back

• 在容器的末尾添加一个元素。
• 适用于 vector, deque, list, 和 forward_list。

push_front

• 在容器的开头添加一个元素。
• 适用于 deque 和 list。

emplace_back

• 在容器的末尾直接构造一个元素。
• 适用于 vector, deque, 和 list。

emplace_front

• 在容器的开头直接构造一个元素。
• 适用于 deque 和 list。

insert

• 在容器的指定位置插入一个或多个元素。
• 适用于 vector, deque, 和 list。

emplace

• 在指定位置直接构造一个元素。
• 适用于 vector, deque, 和 list。

其他操作与迭代器

• at(index)：返回指定位置的元素引用，带边界检查。
• operator[]：返回指定位置的元素引用，不带边界检查。
• erase(iterator)：移除迭代器指向的元素或一段元素区间。
• clear()：移除容器中的所有元素。
• resize(n)：改变容器大小，适应新的元素数量。
• swap(container)：交换两个同类型容器的内容。
• begin() / end()：返回指向容器第一个/尾后元素的迭代器。
• rbegin() / rend()：返回指向容器最后一个/尾前元素的逆向迭代器。
• cbegin() / cend()：返回指向容器第一个/尾后元素的常量迭代器。
• capacity()：返回容器不重新分配内存时的最大容量。

迭代器与反向迭代器的例子

list<string> lst;
auto iter = lst.begin();
while (cin >> word)
    iter = lst.insert(iter, word); // 等价于调用 push_front

vector<int> vi = {0,1,2,3,4,5,6,7,8,9};
auto iter = vi.begin();
while (iter != vi.end()) {
    if (*iter % 2) {
        iter = vi.insert(iter, *iter);
        iter += 2;
    } else
        iter = vi.erase(iter);
}

补充：vector 对象的增长模式

当向 vector 添加新元素，而当前的存储空间不足以容纳更多元素时，vector 将执行以下步骤来增长其容量：

• 分配新的更大的内存空间：vector 会分配一个新的内存块，其大小通常是当前容量的两倍（这个增长因子可能因库实现而异，但通常是 1.5 到 2 倍之间）。这样做是为了平衡内存使用和性能。如果增长因子太小，vector 将频繁重新分配内存，导致性能下降；如果增长因子太大，可能会浪费内存。
• 复制或移动现有元素：现有元素将从旧内存空间复制（或移动，如果元素类型支持移动语义）到新分配的内存空间。
• 释放旧内存空间：一旦所有元素都被复制或移动到新的内存空间，vector 将释放旧的内存块。
• 更新容器的元数据：vector 更新其内部数据结构，如指向元素的指针、大小和容量，以反映新的内存布局。