C++容器的一般用途

Question

C ++标准库容器 的一般用途是什么？

• bitset
• deque
• list
• map
• multimap
• multiset
• priority_queue
• queue
• set
• stack
• vector

例如，对于成对搜索，通常使用map更好。

- Elpezmuerto

---

这是 在哪种情况下使用特定的STL容器？ 的重复 - 两个答案都使用了完全相同的图像，并且那个答案更早，而且有更多的答案，所以...似乎没有必要有2个。 - underscore_d

Answer 1

一张图片胜过千言万语。

你可以通过在Freenode的##C++频道使用“container choice”或“containerchoice”命令来获得该图片，它是由##C++频道中的信息机器人nolyc提供的。你会在回复中收到指向adrinael.net的链接，我们应该感谢Freenode的##C++社区成员Adrinael提供了这个托管链接。

- Tomasz Łazarowicz

---

非常有用的图片，几乎完全符合我的要求。 - Elpezmuerto

你有更新过的版本来反映新的C++11容器吗？ - Arbalest

@Arbalest 这个问题的另一个版本，应该被标记为重复，它在这个答案中有所涉及：https://dev59.com/TXRB5IYBdhLWcg3w6LV2#22671607 - underscore_d

除了有一个被接受的答案发布了与这个完全相同的图片，尽管声称来源不同，我认为为机器人托管图像并不能证明作者身份。因此，我要冒险说，真正的来源/值得感谢的人是David J Moore，在这里：http://homepages.e3.net.nz/~djm/cppcontainers.html - underscore_d

这个图并不能回答所有的情况。比如第一个问题“顺序重要吗”？是的，但我还需要通过关键字查找元素。那我该去哪里呢？ - KansaiRobot

Answer 2

bitset - 用于存储位(bit)。通常用来存储一些标志(flag)值，因为只需要一个比特(bit)就能够表示。

deque - 双端队列，支持push_back、push_front、pop_back 和 pop_front等基本类方法。它是一个“无序”(unordered)的容器。

list - 链表。此容器不是内存连续的。添加和删除元素的时间复杂度为O(1)，但查找特定元素的时间复杂度为O(n)。这也是一个无序容器。

map - 存储键值对(std::pair)的容器。第一个元素是键(key)，每个元素必须具有唯一的键。该容器的底层数据结构是树(tree)，因此在map中查找元素的时间复杂度为n*log(n)。由于树(tree)是二叉且平衡的，因此添加和删除元素可能需要更多的时间，而且此容器始终保持有序。

multimap - 与std::map几乎相同，但可以允许具有相同键的元素对。例如，multimap可以包含元素：(666, "alabala")、(666, "asdfg")，而标准std::map则不行。此容器也是有序的。

multiset - 与set相同，但可包含重复元素。set也是一个始终保持有序的STL容器。例如，集合{ 1, 2, 3 }中如果你尝试将'1'添加到此集合中，它将不会被添加，因为已经存在这样的元素(类比数学集合)。因此，multiset允许具有相同值的多个元素，例如{ 1, 1, 1, 2, 3, 4, 4, 4, 4 }是一个正确的multiset，而它不是set。将元素添加和删除到std::set中仍然是对数时间，因为它表示为二叉、有序和平衡的树(tree)。

priority_queue是一个基于严格弱排序条件的容器，它的第一个元素总是包含元素中最大的。其基本功能是push_back和pop_back操作。

queue是一种FIFO（先进先出）结构，与标准队列相似，当你去商店等待排队时，先到达的人将是第一个离开的。可以使用push_back和pop_front来进行操作。无序容器。

set - 我已经在multiset部分进行了描述。

stack是一种LIFO（后进先出）堆栈，其基本功能是push_back和pop_back。无序容器。

vector类似于标准C++数组，被视为常规数组，具有内存连续性，可传递给C程序（传递第一个元素的地址）。无序容器。

重要提示：我只描述了基本功能而非全部功能，更多信息请参考CPlusPlus.com。

- Kiril Kirov

---

我不知道2010年的情况，但现在我看到人们建议使用cppreference.com而不是cplusplus.com，因为他们感觉_cppreference_的质量更好。_cppreference_上的等效链接是：容器库 顺便说一句，我可以保证这个帖子中没有人使用STL；他们正在使用标准库，它恰好从STL中适应了很多内容。请参见https://dev59.com/UG435IYBdhLWcg3wyzaa#5205571 - underscore_d

@underscore_d - 是的，cppreference.com 绝对是更好的资源。我不再使用 cplusplus.com，这样说吧 - 我不建议使用它。我也同意关于 STL 和标准库的看法。 - Kiril Kirov