General use cases for C++ containers

What are the general use cases for the C++ standard library containers?

• bitset
• deque
• list
• map
• multimap
开发者_如何学JAVA
• multiset
• priority_queue
• queue
• set
• stack
• vector

For example, a map is generally better for a paired search.

A picture is worth a thousand words.

It's available from nolyc, the informative bot of ##C++ on Freenode, using the command "container choice" or "containerchoice". The link to this picture you receive in response is hosted at adrinael.net, which suggests we should thank Adrinael, member of Freenode's ##C++ community.

bitset - used to store bits. General purpose - store some flags' values. You don't need more that 1 bit for that.

deque - double ended queue - push_back, push_front, pop_back and pop_front - basic class' methods. "Not sorted" (unordered) container.

list - linked list. This container is not memory-continuous. Its time for adding and deleting elements is O(1), but looking for a specific element is O(n). Unordered container.

map - container, stores pairs (std::pair). The first one is the key - every element from the map must be with unique key. The map is represented as tree, so the searching for an element in the map is n*log(n). This container is always sorted, that's why adding and removing elements could cause more time - the tree(the data structure) is binary and balanced.

multimap - almost the same as std::map, but allows pairs with the same keys. For example, a multimap could contain elements: (666, "alabala"), (666, "asdfg"), while the standard std::map can't. This container is also sorted.

multiset - again - the same as set, but with repeatable elements. set - well, this is also always sorted STL container. For example, a set is { 1, 2, 3 } and when you try to add '1' into this set, it will not be added, as already there's such element. (it's analogical to the mathematical's set). So, multiset allows several elements with the same value, for example { 1, 1, 1, 2, 3, 4, 4, 4, 4 } is a correct multiset, while it's not a set. Adding and removing element into std::set is still logarithmic time, as it's represented as a binary, sorted and balanced tree.

priority_queue - its first element is always the greatest of the elements it contains, according to some strict weak ordering condition. Basic functionality - push_back and pop_back.

queue - FIFO structure - First in, first out. (or the same as LILO - Last In - Last Out). It's analogue to a standard queue - when you go to a shop and start waiting on the queue, the first one there will be the first one to go. You can just push_back and pop_front. Unordered container.

set - I already described it in the multiset section.

stack - LIFO - Last In - First Out - stack. Basic functionality - push_back, pop_back. Unordered container.

vector - analogue to a standard c++ array. It's treated as regular array, it's memory-continuous, could be passed to a C program(passing the address of the first element). Unordered container.

IMPORTANT NOTE: I described the basic functionality, not the whole one. Read CPlusPlus.com for more information.