STL容器

简介

容器库是类模板与算法的汇集，允许程序员简单地访问常见数据结构，例如队列、链表和栈。

有三类容器——顺序容器、关联容器和无序关联容器——每种都被设计为支持不同组的操作。

容器管理为其元素分配的存储空间，并提供直接或间接地通过迭代器（拥有类似指针属性的对象）访问它们的函数。

大多数容器拥有至少几个常见的成员函数，并共享功能。

特定应用的最佳容器不仅依赖于提供的功能，还依赖于对于不同工作量的效率。

顺序容器

顺序容器是实现能按顺序访问的数据结构。

array(静态数组)

vector(动态数组)

• vector为动态数组；

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include<unordered_map>

using namespace std;

// vector 初始化
vector<int> v = {7, 5, 16, 8};

// C++11 初始化器列表语法：
vector<std::string> words1 {"the", "frogurt", "is", "also", "cursed"};
cout << "words1: " << words1 << '\n';

// words2 == words1
vector<std::string> words2(words1.begin(), words1.end());
std::cout << "words2: " << words2 << '\n';

// words3 == words1
std::vector<std::string> words3(words1);
std::cout << "words3: " << words3 << '\n';

// words4 为 {"Mo", "Mo", "Mo", "Mo", "Mo"}
std::vector<std::string> words4(5, "Mo");
std::cout << "words4: " << words4 << '\n';

list(双向链表)

• list为双向链表；

1

deque

• deque为双端队列；

1

关联容器

关联容器实现能快速查找（ O(log n) 复杂度）的数据结构。

set

• set

map

• map

无序关联容器

无序关联容器提供能快速查找（均摊 O(1) ，最坏情况 O(n) 的复杂度）的无序（哈希）数据结构。

容器适配器

容器适配器提供顺序容器的不同接口。

span

span 是相接的对象序列上的非占有视图，某个其他对象占有序列的存储。

迭代器非法化

只读方法决不非法化迭代器或引用。修改容器内容的方法可能非法化迭代器和/或引用，总结于此表格。

此处插入指代任何添加一或多个元素到容器的方法，而擦除指代任何从容器移除一或多个元素的方法。

• 插入方法的例子是 std::set::insert 、 std::map::emplace 、 std::vector::push_back 和 std::deque::push_front 。

  • 注意 std::unordered_map::operator[] 也算，因为它可能插入元素到 map 中。

• 擦除方法的例子是 std::set::erase 、 std::vector::pop_back 、 std::deque::pop_front 和 std::map::clear 。

  • clear 非法化所有迭代器和引用。因为它擦除所有元素，这在技术上遵照上述规则。

尾后迭代器需要特别留意。通常像指向未被擦除元素的正常迭代器一般非法化此迭代器。故 std::set::end 决不被非法化， std::unordered_set::end 仅在重哈希时被非法化， std::vector::end 始终被非法化（因为它始终出现在被修改元素后），以此类推。

• 例外：删除 std::deque 末元素的擦除操作会非法化尾后迭代器，尽管它不是容器的被擦除元素（或者说根本不是元素）。与 std::deque 迭代器的通用规则结合后，最终结果是不非法化 std::deque::end 的唯一修改操作是删除首元素，而非末元素的擦除。

线程安全

1. 能同时在不同容器上由不同线程调用所有容器函数。更广泛而言， C++ 标准库函数不读取能通过其他线程访问的对象，除非这些对象能直接或间接地经由函数参数，包含 this 指针访问;

2. 能同时在同一容器上由不同线程调用 const 成员函数。而且，成员函数 begin() 、 end(), rbegin() 、 rend() 、 front() 、 back() 、 data() 、 find() 、 lower_bound() 、 upper_bound() 、 equal_range() 、 at() 和除了关联容器中的 operator[] 对于线程安全的目标表现如同 const （即它们亦能同时在同一容器上由不同线程调用）。更广泛而言， C++ 标准库函数不修改对象，除非这些对象能直接或间接地经由函数参数，包含 this 指针访问。
   

3. 同一容器中不同元素能由不同线程同时修改，除了 std::vector 的元素（例如， std::future 对象的 vector 能从多个线程接收值）;

4. 迭代器操作（例如自增迭代器）读但不修改底层容器，而且能与同一容器上的其他迭代器操作同时由 const 成员函数执行。非法化任何迭代器的容器操作修改容器，且不能与任何在既存迭代器上的操作同时执行，即使这些迭代器未被非法化;

5. 同一容器上的元素可以同时由不指定为访问这些元素的函数修改。更广泛而言， C++ 标准库函数不间接读取能从其参数访问的对象（包含容器的其他对象），除非其规定要求如此；

6. 任何情况下，容器操作（还有算法，或其他 C++ 标准库函数）可于内部并行化，只要不更改用户可见的结果（例如 std::transform 可并行化，但指定了按顺序观览序列的每个元素的 std::for_each 不行） | (C++11 起)

成员函数表格