容器库

来自cppreference.com
< cpp

容器库是类模板与算法的汇集,允许程序员简单地访问常见数据结构,例如队列、链表和栈。有三类容器——顺序容器、关联容器和无序关联容器——每种都被设计为支持不同组的操作。

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

大多数容器拥有至少几个常见的成员函数,并共享功能。特定应用的最佳容器不仅依赖于提供的功能,还依赖于对于不同工作量的效率。

目录

[编辑] 顺序容器

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

(C++11 起)
静态的连续数组
(类模板) [编辑]
动态的连续数组
(类模板) [编辑]
双向队列
(类模板) [编辑]
(C++11 起)
单向链表
(类模板) [编辑]
双向链表
原文:
doubly-linked list
文本通过谷歌翻译机器翻译。
你可以帮忙校正和验证翻译。点击此处查看指示。

(类模板) [编辑]

[编辑] 关联容器

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

唯一键的集合,按照键排序
(类模板) [编辑]
键值对的集合,按照键排序,键是唯一的
(类模板) [编辑]
键的集合,按照键排序
(类模板) [编辑]
键值对的集合,按照键排序
(类模板) [编辑]

[编辑] 无序关联容器

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

(C++11 起)
唯一键的集合,按照键生成散列
(类模板) [编辑]
(C++11 起)
键值对的集合,按照键生成散列,键是唯一的
(类模板) [编辑]
键的集合,按照键生成散列
(类模板) [编辑]
键值对的集合,按照键生成散列
(类模板) [编辑]

[编辑] 容器适配器

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

堆栈适配器(LIFO)
(类模板) [编辑]
改写容器来提供队列(FIFO数据结构)
(类模板) [编辑]
改写容器来提供优先级队列
(类模板) [编辑]

[编辑] 迭代器非法化

线程安全

  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<bool> 的元素(例如, std::future 对象的 vector 能从多个线程接收值)。
  4. 迭代器操作(例如自增迭代器)读但不修改底层容器,而且能与同一容器上的其他迭代器操作同时由 const 成员函数执行。非法化任何迭代器的容器操作修改容器,且不能与任何在既存迭代器上的操作同时执行,即使这些迭代器未被非法化。
  5. 同一容器上的元素可以同时由不指定为访问这些元素的函数修改。更广泛而言, C++ 标准库函数不间接读取能从其参数访问的对象(包含容器的其他对象),除非其规定要求如此。
  6. 任何情况下,容器操作(还有算法,或其他 C++ 标准库函数)可于内部并行化,只要不更改用户可见的结果(例如 std::transform 可并行化,但指定了按顺序观览序列的每个元素的 std::for_each 不行)
(C++11 起)

[编辑] 成员函数表

- C++03 起存在的函数
- C++11 起存在的函数
- C++17 起存在的函数
顺序容器 关联容器 无序关联容器 容器适配器
头文件 <array> <vector> <deque> <forward_list> <list> <set> <map> <unordered_set> <unordered_map> <stack> <queue>
容器
array
vector
deque
forward_list
list
set
multiset
map
multimap
unordered_set
unordered_multiset
unordered_map
unordered_multimap
stack
queue
priority_queue
(构造函数)
(隐式)
vector
deque
forward_list
list
set
multiset
map
multimap
unordered_set
unordered_multiset
unordered_map
unordered_multimap
stack
queue
priority_queue
(析构函数)
(隐式)
~vector
~deque
~forward_list
~list
~set
~multiset
~map
~multimap
~unordered_set
~unordered_multiset
~unordered_map
~unordered_multimap
~stack
~queue
~priority_queue
operator=
(隐式)
operator=
operator=
operator=
operator=
operator=
operator=
operator=
operator=
operator=
operator=
operator=
operator=
operator=
operator=
operator=
assign
assign
assign
assign
assign
迭代器
begin
cbegin
begin
cbegin
begin
cbegin
begin
cbegin
begin
cbegin
begin
cbegin
begin
cbegin
begin
cbegin
begin
cbegin
begin
cbegin
begin
cbegin
begin
cbegin
begin
cbegin
begin
cbegin
end
cend
end
cend
end
cend
end
cend
end
cend
end
cend
end
cend
end
cend
end
cend
end
cend
end
cend
end
cend
end
cend
end
cend
rbegin
crbegin
rbegin
crbegin
rbegin
crbegin
rbegin
crbegin
rbegin
crbegin
rbegin
crbegin
rbegin
crbegin
rbegin
crbegin
rbegin
crbegin
rend
crend
rend
crend
rend
crend
rend
crend
rend
crend
rend
crend
rend
crend
rend
crend
rend
crend
元素访问
at
at
at
at
at
at
operator[]
operator[]
operator[]
operator[]
operator[]
operator[]
front
front
front
front
front
front
front
top
back
back
back
back
back
top
back
容量
empty
empty
empty
empty
empty
empty
empty
empty
empty
empty
empty
empty
empty
empty
empty
empty
empty
size
size
size
size
size
size
size
size
size
size
size
size
size
size
size
size
max_size
max_size
max_size
max_size
max_size
max_size
max_size
max_size
max_size
max_size
max_size
max_size
max_size
max_size
resize
resize
resize
resize
resize
capacity
capacity
bucket_count
bucket_count
bucket_count
bucket_count
reserve
reserve
reserve
reserve
reserve
reserve
shrink_to_fit
shrink_to_fit
shrink_to_fit
修改器
clear
clear
clear
clear
clear
clear
clear
clear
clear
clear
clear
clear
clear
insert
insert
insert
insert_after
insert
insert
insert
insert
insert
insert
insert
insert
insert
emplace
emplace
emplace
emplace_after
emplace
emplace
emplace
emplace
emplace
emplace
emplace
emplace
emplace
emplace_hint
emplace_hint
emplace_hint
emplace_hint
emplace_hint
emplace_hint
emplace_hint
emplace_hint
emplace_hint
erase
erase
erase
erase_after
erase
erase
erase
erase
erase
erase
erase
erase
erase
push_front
push_front
push_front
push_front
emplace_front
emplace_front
emplace_front
emplace_front
pop_front
pop_front
pop_front
pop_front
pop
pop
push_back
push_back
push_back
push_back
push
push
push
emplace_back
emplace_back
emplace_back
emplace_back
emplace
emplace
emplace
pop_back
pop_back
pop_back
pop_back
pop
swap
swap
swap
swap
swap
swap
swap
swap
swap
swap
swap
swap
swap
swap
swap
swap
swap
merge
merge
merge
merge
merge
merge
merge
merge
merge
merge
merge
extract
extract
extract
extract
extract
extract
extract
extract
extract
链表操作
splice
splice_after
splice
remove
remove
remove
remove_if
remove_if
remove_if
reverse
reverse
reverse
unique
unique
unique
sort
sort
sort
查找
count
count
count
count
count
count
count
count
count
find
find
find
find
find
find
find
find
find
lower_bound
lower_bound
lower_bound
lower_bound
lower_bound
upper_bound
upper_bound
upper_bound
upper_bound
upper_bound
equal_range
equal_range
equal_range
equal_range
equal_range
equal_range
equal_range
equal_range
equal_range
观察器
key_comp
key_comp
key_comp
key_comp
key_comp
value_comp
value_comp
value_comp
value_comp
value_comp
hash_function
hash_function
hash_function
hash_function
hash_function
key_eq
key_eq
key_eq
key_eq
key_eq
分配器
get_allocator
get_allocator
get_allocator
get_allocator
get_allocator
get_allocator
get_allocator
get_allocator
get_allocator
get_allocator
get_allocator
get_allocator
get_allocator
容器
array
vector
deque
forward_list
list
set
multiset
map
multimap
unordered_set
unordered_multiset
unordered_map
unordered_multimap
stack
queue
priority_queue
顺序容器 关联容器 无序关联容器 容器适配器

(此表的 PDF 版本可用于 File:container-library-overview-2012-12-27.pdf 。)