Reference C Library IOstream Library Strings library STL Containers STL Algorithms Miscellaneous STL Containers bitset deque list map multimap multiset priority_queue queue set stack vector

STL Containers library Standard Template Library: Containers A container is a holder object that stores a collection other objects (its elements). They are implemented as class templates, which allows a great flexibility in the types supported as elements. The container manages the storage space for its elements and provides member functions to access them, either directly or through iterators (reference objects with similar properties to pointers). Containers replicate structures very commonly used in programming: dynamic arrays (vector), queues (queue), stacks (stack), heaps (priority_queue), linked lists (list), trees (set), associative arrays (map)... Many containers have several member functions in common, and share functionalities. The decision of which type of container to use for a specific need does not generally depend only on the functionality offered by the container, but also on the efficiency of some of its members (complexity). This is especially true for sequence containers, which offer different trade-offs in complexity between inserting/removing elements and accessing them. stack, queue and priority_queue are implemented as container adaptors. Container adaptors are not full container classes, but classes that provide a specific interface relying on an object of one of the container classes (such as deque or list) to handle the elements. The underlying container is encapsulated in such a way that its elements are accessed by the members of the container class independently of the underlying container class used. Container class templates Sequence containers: vector Vector (class template) deque Double ended queue (class template) list List (class template) Container adaptors: stack LIFO stack (class template) queue FIFO queue (class template) priority_queue Priority queue (class template) Associative containers: set Set (class template) multiset Multiple-key set (class template) map Map (class template) multimap Multiple-key map (class template) bitset Bitset (class template) Member map This is a comparison chart with the different member functions present on each of the different containers: Sequence containers Associative containers Headers <vector> <deque> <list> <set> <bitset> Members complex vector deque list set multiset map multimap bitset constructor * constructor constructor constructor constructor constructor constructor constructor constructor destructor O(n) destructor destructor destructor destructor destructor destructor destructor operator= O(n) operator= operator= operator= operator= operator= operator= operator= operators iterators begin O(1) begin begin begin begin begin begin begin end O(1) end end end end end end end rbegin O(1) rbegin rbegin rbegin rbegin rbegin rbegin rbegin rend O(1) rend rend rend rend rend rend rend capacity 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 empty O(1) empty empty empty empty empty empty empty resize O(n) resize resize resize element access front O(1) front front front back O(1) back back back operator[] * operator[] operator[] operator[] operator[] at O(1) at at modifiers assign O(n) assign assign assign insert * insert insert insert insert insert insert insert erase * erase erase erase erase erase erase erase swap O(1) swap swap swap swap swap swap swap clear O(n) clear clear clear clear clear clear clear push_front O(1) push_front push_front pop_front O(1) pop_front pop_front push_back O(1) push_back push_back push_back pop_back O(1) pop_back pop_back pop_back observers key_comp O(1) key_comp key_comp key_comp key_comp value_comp O(1) value_comp value_comp value_comp value_comp operations find O(log n) find find find find count O(log n) count count count count count lower_bound O(log n) lower_bound lower_bound lower_bound lower_bound upper_bound O(log n) upper_bound upper_bound upper_bound upper_bound equal_range O(log n) equal_range equal_range equal_range equal_range unique members capacity reserve splice remove remove_if unique merge sort reverse set reset flip to_ulong to_string test any none Amortized complexity shown. Legend: O(1) constant < O(log n) logarithmic < O(n) linear; *=depends on container Container adaptors: Container Adaptors Headers <stack> <queue> Members stack queue priority_queue constructor * constructor constructor constructor capacity size O(1) size size size empty O(1) empty empty empty element access front O(1) front back O(1) back top O(1) top top modifiers push O(1) push push push pop O(1) pop pop pop

Home page | Privacy policy
© cplusplus.com, 2000-2011 - All rights reserved - v2.9
Spotted an error? contact us