Skip to content

Introduction to STL Containers

Classification

Sequence Containers

  • Vector (vector): A sequence container that supports efficient insertion at the back.
  • Array (array) C++11: A fixed-size sequence container, a simple wrapper around C-style arrays.
  • Deque (deque): A double-ended queue that supports efficient insertion at both ends.
  • List (list): A doubly linked list that can be traversed in both directions.
  • Forward List (forward_list): A singly linked list that can only be traversed in one direction.

Associative Containers

  • Set (set): A container that stores unique elements in a sorted order. It is implemented as a red-black tree of nodes, each containing an element, with nodes ordered by a predicate comparing element values.
  • Multiset (multiset): A container that stores elements in a sorted order. Allows duplicate elements.
  • Map (map): A collection of {key, value} pairs, ordered by a predicate comparing keys.
  • Multimap (multimap): A multiset of {key, value} pairs, i.e., a map that allows duplicate keys.
What is a Predicate (Predicate)?

A predicate is a function that returns true or false. STL containers often use predicates as template parameters.

Unordered (Associative) Containers

  • Unordered (Multi)set (unordered_set/unordered_multiset) C++11: Unlike set/multiset, elements are unordered. It only cares about "whether an element exists" and is implemented using hashing.
  • Unordered (Multi)map (unordered_map/unordered_multimap) C++11: Unlike map/multimap, keys are unordered. It only cares about "the correspondence between keys and values" and is implemented using hashing.

Container Adapters

Container adapters are not actually containers. They lack some container features (e.g., iterators, clear() function, ...).

"An adapter is a mechanism that makes one thing behave like another." Adapters wrap containers to make them exhibit different behavior.

  • Stack (stack): A Last-In-First-Out (LIFO) container, by default a wrapper around a deque (deque).
  • Queue (queue): A First-In-First-Out (FIFO) container, by default a wrapper around a deque (deque).
  • Priority Queue (priority_queue): A queue where the order of elements is determined by a predicate applied to the stored value pairs, by default a wrapper around a vector (vector).

Common Features

Container Declaration

All follow the form containerName<typeName,...> name, but the number and form of template parameters (inside <>) vary depending on the specific container.

The fundamental reason: STL stands for "Standard Template Library," so containers are template classes.

Iterators

Please refer to Iterators.

Common Functions

=: Has assignment operator and copy constructor.

begin(): Returns an iterator pointing to the first element.

end(): Returns an iterator pointing to the position one past the last element. end() does not point to an element but is the successor of the last element.

size(): Returns the number of elements in the container.

max_size(): Returns the theoretical maximum number of elements the container can hold. Depends on the container type and the type of stored variables.

empty(): Returns whether the container is empty.

swap(): Swaps two containers.

clear(): Clears the container.

==/!=/</>/<=/>=: Compare two containers lexicographically. (When comparing elements, each element of a map is treated as set<pair<key, value>>. Unordered containers do not support </>/<=/>=.)

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用