C++的标准容器及其应用

数组（array）

数组的特征

数组是固定大小的序列容器：它按严格线性序列，保存排序的特定数量的元素。

在内部，数组除了它包含的元素之外，不保留任何数据（甚至不保留其大小，这是一个模板参数，在编译时固定）。就存储大小而言，它与使用语言的括号语法 ([]) 声明的普通数组一样高效。这个类只是添加了一层成员函数和全局函数，这样数组就可以作为标准容器使用了。

与其他标准容器不同，数组具有固定大小，并且不能通过分配器管理其元素的分配：它们是封装固定大小元素数组的聚合类型。因此，它们不能动态扩展或收缩。

零大小的数组是有效的，但不能调用它的成员函数（比如front, back和data）。

与标准库中的其他容器不同，交换两个数组容器是一种线性操作，涉及单独交换范围中的所有元素，这通常是效率相当低的操作。另一方面，这允许两个容器中的元素的迭代器保持其原始容器关联。

数组容器的另一个独特功能是，它们可以被视为元组（tuple）对象： array 能重载 get 函数以访问数组的元素，就好像它是元组一样，拥有专门的 tuple_size 和 tuple_element 类型。

应用实列

成员函数，size()。

#include <iostream>
#include <array>using namespace  std;int main ()
{array<int,5> arr_int = {0};cout << "size of arr_int: " << arr_int.size() << endl;cout << "sizeof(arr_int): " << sizeof(arr_int) << endl;return 0;
}

size of arr_int: 5
sizeof(arr_int): 20

成员函数，data()。

#include <iostream>
#include <cstring>
#include <array>using namespace  std;int main ()
{const char* cstr = "Test string";array<char,12> charr;memcpy (charr.data(),cstr,12);cout << charr.data() << '\n';return 0;
}

// output
Test string

前向列表（forward_list）

前向列表的特征

前向列表是序列容器，可以用不变的时间，在序列中任何位置进行插入和删除。

前向列表作为单链表实现；单链表可以将它们包含的每个元素存储在不同，且不相关的存储位置。通过与序列中下一个元素的链接的每个元素的关联来保持顺序。

forward_list 容器和列表容器之间的主要设计区别在于，第一个容器仅在内部保留到下一个元素的链接，而后者为每个元素保留两个链接：一个指向下一个元素，一个指向前一个元素，从而实现高效双向迭代，但每个元素消耗额外的存储空间，并且插入和删除元素的时间开销稍高。因此，forward_list 对象比 list 对象更有效，尽管它们只能向前迭代。

与其他基本标准序列容器（数组、向量和双向队列）相比，在容器内任何位置插入、提取和移动元素，forward_list 通常表现更好，因此在密集使用这些元素的算法（如排序算法）中也表现得更好。

与其他序列容器相比，forward_lists 和list的主要缺点是它们无法通过位置直接访问元素；例如，要访问forward_list中的第六个元素，必须从开头迭代到该位置，这需要这些元素之间的距离呈线性时间。它们还消耗一些额外的内存来保存与每个元素关联的链接信息（这对于小型元素的大型列表可能是一个重要因素）。

forward_list 类模板在设计时就考虑到了效率：根据设计，它与简单的手写 C 风格单链表一样高效，事实上，它是唯一出于效率考虑,而故意缺少 size 成员函数的标准容器：由于其作为链表的性质，具有需要恒定时间的大小成员将需要它为其大小保留一个内部计数器（如列表那样）。这会消耗一些额外的存储空间，并使插入和删除操作的效率稍微降低。如果需要获取forward_list对象的大小，可以使用距离算法，加上开始和结束参数，这需要线性操作时间。

应用实列

插入元素

#include <iostream>
#include <forward_list>using namespace std;int main ()
{forward_list<int> mylist;forward_list<int>::iterator it;it = mylist.insert_after ( mylist.before_begin(), 10 );it = mylist.insert_after ( it, 2, 20 );                          it = mylist.begin();                                             it = mylist.insert_after ( it, {1,5,3} );                        cout << "mylist contains:";for (auto x: mylist) cout << ' ' << x;cout << endl;return 0;
}

// output
mylist contains: 10 1 5 3 20 20

列表（list）

列表的特征

list是序列容器，在list中的任何位置，进行插入和擦除操作，只需要恒定时间。list可以双向迭代。

list容器是用双向链表实现的；双向链表可以将它们包含的每个元素存储在不同且不相关的存储位置。通过与每个元素的关联在内部保持顺序。

它们与forward_list非常相似：主要区别在于forward_list对象是单向链表，因此它们只能向前迭代，以换取更小和更高效的代价。

与其他基本标准序列容器（数组、向量和双端队列）相比，list在已获得迭代器的容器内的任何位置插入、提取和移动元素方面通常表现更好，因此经常出现在密集使用元素操作的算法中，例如排序算法。

与其他序列容器相比，list和前向列表的主要缺点是，它们无法通过位置直接访问元素；例如，要访问列表中的第六个元素，必须从已知位置（例如开头或结尾）迭代到该位置，这需要这些位置之间的距离呈线性时间。它们还消耗一些额外的内存来保存与每个元素关联的链接信息。

应用实列

在表头插入操作

#include <iostream>
#include <list>using namespace std;int main ()
{list<int> mylist = {2,100};         // two ints with a value of 100mylist.push_front (200);mylist.push_front (300);cout << "mylist contains:";for (list<int>::iterator it=mylist.begin(); it!=mylist.end(); ++it)std::cout << ' ' << *it;cout << '\n';return 0;
}

// output
mylist contains: 300 200 2 100

有序映射（map）

有序映射的特征

map是关联容器，它按照特定的顺序，存储由键值和映射值组合形成的元素。

在map中，键值通常用于对元素进行排序和唯一标识，而映射值则存储与该键关联的内容。键和映射值的类型可能不同，按照成员类型 value_type，组合在一起。

typedef pair<const Key, T> value_type;

在内部，map 中的元素始终按其键排序，遵循其内部比较对象（Compare 类型）指示的特定严格弱排序标准。

通过键访问各个元素时，map 容器通常比 unordered_map 容器慢，但它们允许根据子集的顺序，直接迭代。

可以使用括号运算符 ((operator[]) 通过相应的键，直接访问映射中的映射值。

通常使用二叉搜索树实现map 。

应用实列

使用key_comp排序。

#include  <iostream>
#include  <map>
#include  <string>
#include  <functional>
#include  <algorithm>using namespace std;void print_map(const map<string, int, greater<string>>& m)
{for (const auto v : m)std::cout << '[' << v.first << "] = " << v.second << "; ";std::cout << '\n';
}int main()
{map<string, int, greater<string>> m{{"CPU", 10}, {"GPU", 15}, {"RAM", 20}};print_map(m);m["CPU"] = 25; m["SSD"] = 30;print_map(m);m.erase("GPU");print_map( m);
}

// output
[RAM] = 20; [GPU] = 15; [CPU] = 10;
[SSD] = 30; [RAM] = 20; [GPU] = 15; [CPU] = 25;
[SSD] = 30; [RAM] = 20; [CPU] = 25;

队列（queue）

队列的特征

queue是一种容器适配器，专门设计用于在 FIFO 上下文（先进先出）中操作，其中元素被插入到容器的一端并从另一端提取。

queue被实现为容器适配器，它们是使用特定容器类的封装对象作为其底层容器的类，提供一组特定的成员函数来访问其元素。元素被推入特定容器的“后面”并从其“前面”弹出。

底层容器可以是标准容器类模板之一或一些其他专门设计的容器类。该底层容器至少应支持以下操作：

empty
size
front
back
push_back
pop_front

标准容器类 deque 和 list 满足这些要求。默认情况下，如果没有为特定队列类实例化指定容器类，则使用标准容器 deque。

应用实列

#include <iostream>       
#include <array>
#include <queue>      using namespace std;int main ()
{array<int, 5> arr = {1,2,3,4,5};queue<int> myqueue;int myint;for (auto x : arr)myqueue.push (x);cout << "myqueue contains: ";while (!myqueue.empty()){cout << ' ' << myqueue.front();myqueue.pop();}cout << '\n';return 0;
}

myqueue contains:  1 2 3 4 5

priority_queue

priority_queue是一种容器适配器，经过专门设计，根据某些严格的弱排序标准，其第一个元素始终是其包含的最大元素。

此上下文类似于堆，可以随时插入元素，并且只能检索最大堆元素（优先级队列中位于顶部的元素）。

priority_queue被实现为容器适配器，它们是使用特定容器类的封装对象作为其底层容器的类，提供一组特定的成员函数来访问其元素。元素从特定容器的“后面”弹出，即优先级队列的顶部。

底层容器可以是任何标准容器类模板或一些其他专门设计的容器类。容器应可通过随机访问迭代器进行访问并支持以下操作：

empty()
size()
front()
push_back()
pop_back()

标准容器类vector和deque满足这些要求。默认情况下，如果没有为特定priority_queue类实例化指定容器类，则使用标准容器vector。

需要随机访问迭代器的支持才能始终在内部保留堆结构。这是由容器适配器通过在需要时自动调用算法函数 make_heap、push_heap 和 pop_heap 自动完成的。

应用实列

下面展示一些 内联代码片。

#include <iostream>       
#include <array>
#include <queue>      using namespace std;template<typename T>
void pop_println(string rem, T& pq)
{cout << rem << ": ";for (; !pq.empty(); pq.pop())cout << pq.top() << ' ';cout << endl;
}int main()
{const auto data = {1, 8, 5, 6, 3, 4, 0, 9, 7, 2};priority_queue<int> max_priority_queue;for (int n : data)max_priority_queue.push(n);pop_println("max_priority_queue", max_priority_queue);priority_queue<int, vector<int>, greater<int>>min_priority_queue1(data.begin(), data.end());pop_println("min_priority_queue1", min_priority_queue1);struct customLess{bool operator()(int l, int r) const { return l > r; }};priority_queue<int, vector<int>, customLess> custom_priority_queue;for (int n : data)custom_priority_queue.push(n);	  pop_println("custom_priority_queue", custom_priority_queue);priority_queue<int, vector<int>, greater<int>> priority_queue;for (int n : data)priority_queue.push(n); pop_println("priority_queue", priority_queue);
}

// output
max_priority_queue: 9 8 7 6 5 4 3 2 1 0
min_priority_queue1: 0 1 2 3 4 5 6 7 8 9
custom_priority_queue: 0 1 2 3 4 5 6 7 8 9
priority_queue: 0 1 2 3 4 5 6 7 8 9

集合（set）

集合的特征

set是按照特定顺序存储唯一元素的容器。

在set中，元素的值也标识它（值本身就是键），并且每个值必须是唯一的。集合中元素的值一旦在容器中就无法修改（元素始终是常量），但可以将它们插入容器或从容器中删除。

在内部，set中的元素始终按照其内部比较对象（Compare 类型）指示的特定严格弱排序标准进行排序。

通过键访问元素，set 容器通常比 unordered_set 慢，但set允许根据子集的顺序直接迭代。

通常使用二叉搜索树实现set。

应用实列

#include  <iostream>
#include  <set>using namespace std;struct FatKey
{int x;int data[1000];
};struct customComp
{bool operator()(FatKey r, FatKey l){return (r.x > l.x);}
};int main()
{set<int> example{1, 2, 3, 4};for ( auto x : example)cout << x << ", ";cout<<endl;auto search = example.find(2);if (search != example.end())cout << "Found " << (*search) << '\n';elsecout << "Not found\n";set<FatKey, customComp> example2{{1, {}}, {2, {}}, {3, {}}, {4, {}}};for ( auto x : example2)cout << x.x << ", ";cout<<endl;FatKey lk = {3};auto s2 = example2.find(lk); if (s2 != example2.end())std::cout << "Found " << s2->x << '\n';elsestd::cout << "Not found\n";
}

// output
1, 2, 3, 4,
Found 2
4, 3, 2, 1,
Found 3

堆栈（stack）

堆栈的特征

stack是一种容器适配器，专门设计用于在 LIFO 上下文（后进先出）中操作，其中仅从容器的一端插入和提取元素。

stack被实现为容器适配器，它们是使用特定容器类的封装对象作为其底层容器的类，提供一组特定的成员函数来访问其元素。元素从特定容器的“后面”（称为堆栈顶部）推送/弹出。

底层容器可以是任何标准容器类模板或一些其他专门设计的容器类。容器应支持以下操作：

empty
size
back
push_back
pop_back

标准容器类向量、双端队列和列表满足这些要求。默认情况下，如果没有为特定堆栈类实例化指定容器类，则使用标准容器双端队列。

应用实列

#include <iostream>       // std::cout
#include <stack>          // std::stackusing namespace std;int main ()
{stack<int> mystack;for (int i=0; i<5; ++i) mystack.push(i);cout << "Popping out elements...";while (!mystack.empty()){cout << ' ' << mystack.top();mystack.pop();}cout << endl;return 0;
}

// output
Popping out elements... 4 3 2 1 0

无序映射（unordered_map）

无序映射的特征

无序映射是关联容器，用于存储由键值和映射值组合形成的元素，并且允许基于键快速检索各个元素。

在unordered_map中，键值通常用于唯一标识元素，而映射值是一个对象，其内容与该键相关联。键和映射值的类型可能不同。

在内部，unordered_map 中的元素不会按照其键或映射值以任何特定顺序排序，而是根据其哈希值组织到存储桶中，以允许直接通过其键值（使用常量）快速访问各个元素平均时间复杂度）。

unordered_map 容器通过键访问各个元素比 map 容器更快，尽管它们通常在通过其元素子集进行范围迭代时效率较低。

无序映射实现直接访问运算符（operator[]），它允许使用其键值作为参数直接访问映射值。

容器中的迭代器至少是前向迭代器。

应用实列

#include <iostream>
#include <string>
#include <unordered_map>using namespace std;int main()
{// Create an unordered_map of three strings (that map to strings)unordered_map<string, string> u ={{"RED", "#FF0000"},{"GREEN", "#00FF00"},{"BLUE", "#0000FF"}};// Helper lambda function to print key-value pairsauto print_key_value = [](const auto& key, const auto& value){cout << "Key:[" << key << "] Value:[" << value << "]\n";};for (const pair<const string, string>& n : u)print_key_value(n.first, n.second);cout << "\n";// Add two new entries to the unordered_mapu["BLACK"] = "#000000";u["WHITE"] = "#FFFFFF";for (const auto& n : u)print_key_value(n.first, n.second);
}

// output
Key:[BLUE] Value:[#0000FF]
Key:[GREEN] Value:[#00FF00]
Key:[RED] Value:[#FF0000]Key:[WHITE] Value:[#FFFFFF]
Key:[BLACK] Value:[#000000]
Key:[RED] Value:[#FF0000]
Key:[GREEN] Value:[#00FF00]
Key:[BLUE] Value:[#0000FF]

无序集合（unordered_set）

无序集合的特征

无序集是不按特定顺序存储唯一元素的容器，并且允许根据单个元素的值快速检索各个元素。

在 unordered_set 中，元素的值同时也是其唯一标识它的键。键是不可变的，因此，unordered_set 中的元素一旦进入容器就无法修改, 但它们可以插入和删除。

在内部，unordered_set 中的元素不按任何特定顺序排序，而是根据其哈希值组织到存储桶中，以允许直接通过其值快速访问各个元素（平均时间复杂度恒定）。

通过键访问各个元素, unordered_set 容器比 set 容器更快，尽管它们通常在通过其元素子集进行范围迭代时效率较低。

容器中的迭代器至少是前向迭代器。

应用实列

#include <iostream>
#include <unordered_set>using namespace std;void print(const unordered_set<int> set)
{for (const auto& elem : set)cout << elem << ' ';cout << '\n';
}int main()
{unordered_set<int> mySet{2, 7, 1, 8, 2, 8}; // initializingprint(mySet);mySet.insert(5); // puts an element 5 in the setprint(mySet);auto iter = mySet.find(5); if (iter != mySet.end())mySet.erase(iter); // removes an element pointed to by iterprint(mySet);mySet.erase(7); // removes an element 7print(mySet);
}

// ourput
8 1 7 2
5 8 1 7 2
8 1 7 2
8 1 2

向量（vector）

向量的特征

向量是表示大小可以更改的数组的序列容器。

就像数组一样，向量对其元素使用连续的存储位置，这意味着, 可以使用指向其元素的常规指针上的偏移量来访问其元素，并且与数组中一样高效。但与数组不同的是，它们的大小可以动态变化，其存储由容器自动处理。

在内部，向量使用动态分配的数组来存储其元素。当插入新元素时，可能需要重新分配该数组, 以便增加大小，这意味着分配一个新数组, 并将所有元素移动到其中。就处理时间而言，这是一项相对昂贵的任务，因此，每次将元素添加到容器时，向量不会重新分配。

相反，向量容器可以分配一些额外的存储, 来适应可能的增长，因此容器的实际容量可能大于包含其元素严格需要的存储（即，其大小）。库可以实施不同的增长策略，以平衡内存使用和重新分配之间的平衡，但在任何情况下，重新分配只能以对数增长的大小间隔进行，以便可以为向量末尾的各个元素的插入提供常量时间复杂性。

因此，与数组相比，向量消耗更多的内存来换取管理存储和以高效方式动态增长的能力。

与其他动态序列容器（双端队列、列表和前向列表）相比，向量可以非常高效地访问其元素（就像数组一样），并且从其末尾添加或删除元素也相对高效。对于涉及在末尾以外的位置插入或删除元素的操作，它们的性能比其他操作更差，并且迭代器和引用的一致性不如列表和前向列表。

应用实列

#include <iostream>
#include <vector>using namespace std;int main()
{vector<int> v = {8, 4, 5, 9};v.push_back(6);v.push_back(9);v[2] = -1;for (int n : v)cout << n << ' ';cout << endl;
}

// output
8 4 -1 9 6 9