STL Containers | C++

/STL Containers | C++

The containers library is a collection of templates and algorithms that implement the common data structures that we work with as programmers. A container is an object that stores a collection of elements (i.e. other objects). Each of these containers manages the storage space for their elements and provides access to each element through iterators and/or member functions. The standard containers implement structures that are commonly used in our programs, such as:

  • Dynamic arrays
  • Queues
  • Stacks
  • Linked lists
  • Trees
  • Associative sets

 

The C++ container library categorizes containers into four types:

  1. Sequence containers
  2. Sequence container adapters
  3. Associative containers
  4. Unordered associative containers

 

Sequence containers

Sequence containers are used for data structures that store objects of the same type in a linear manner. The STL Sequence Container types are:

  • array : represents a static contiguous array
  • vector : represents a dynamic contiguous array
  • forward_list : represents a singly-linked list
  • list : represents a doubly-linked list
  • deque : represents a double-ended queue, where elements can be added to the front or back of the queue.

 

Sequence container adapters

Container adapters are a special type of container class. They are not full container classes on their own, but wrappers around other container types (such as a vector, deque, or list). These container adapters encapsulate the underlying container type and limit the user interfaces accordingly. The standard container adapters are:

  1. stack : provides an LIFO data structure
  2. queue : provides a FIFO data structure
  3. priority_queue : provides a priority queue, which allows for constant-time lookup of the largest element (by default)

 

Associative Container

Associative containers provide sorted data structures that provide a fast lookup using keys. The STL Associative Container types are can be divided in two ways: containers which require unique keys, and those which allow multiple entries using the same key.

  • Keys are unique
    • set : Collection of unique keys, sorted by keys
    • map :  Collection of key-value pairs, sorted by keys
  • Multiple entries for the same key are permitted
    • multiset : Collection of keys, sorted by keys
    • multimap : Collection of key-value pairs, sorted by keys

set and map are typically implemented using red-black trees.

 

Unordered Associative Container

Unordered associative containers provide unsorted data structures that can be accessed using a hash. For all STL Unordered Associative Container types, a hashed key is used to access the data. The standard types are split between those that require unique keys, and those that do not:

  • Keys are unique
    • unordered set : Collection of keys, hashed by keys
    • unordered_map : Collection of key-value pairs, hashed by keys
  • Multiple entires for the same key are permitted
    • unordered_multiset : Collection of keys, hashed by keys
    • unordered_multimap : Collection of key-value pairs, hashed by keys
September 18th, 2019|Categories: Programming|Tags: |
avatar
  Subscribe  
Notify of