Search

Language Selector

16.2 — STL containers overview

By far the most commonly used functionality of the STL library are the STL container classes. If you need a quick refresher on container classes, check out lesson 10.4 -- Container Classes.

The STL contains many different container classes that can be used in different situations. Generally speaking, the container classes fall into three basic categories: Sequence containers, Associative containers, and Container adapters. We’ll just do a quick overview of the containers here.

Sequence Containers

Sequence containerss are container classes that maintain the ordering of elements in the container. A defining characteristic of sequence containers is that you can choose where to insert your element by position. The most common example of a sequence container is the array: if you insert four elements into an array, the elements will be in the exact order you inserted them.

The STL contains 3 sequence containers: vector, deque, and list.

  • If you’ve ever taken physics, you probably are thinking of a vector as an entity with both magnitude and direction. The unfortunately named vector class in the STL is a dynamic array capable of growing as needed to contain its elements. The vector class allows random access to its elements via operator[], and inserting and removing elements from the end of the vector is generally fast.

    The following program inserts 6 numbers into a vector and uses the overloaded [] operator to access them in order to print them.

    This program produces the result:
    10 9 8 7 6 5

  • The deque class (pronounced “deck”) is a double-ended queue class, implemented as a dynamic array that can grow from both ends.

    This program produces the result:

    8 9 10 0 1 2

  • A list is a special type of sequence container called a doubly linked list where each element in the container contains pointers that point at the next and previous elements in the list. Lists only provide access to the start and end of the list -- there is no random access provided. If you want to find a value in the middle, you have to start at one end and “walk the list” until you reach the element you want to find. The advantage of lists is that inserting elements into a list is very fast if you already know where you want to insert them. Generally iterators are used to walk through the list.

    We’ll talk more about both linked lists and iterators in future lessons.

  • Although the STL string (and wstring) class aren’t generally included as a type of sequence container, they essentially are, as they can be thought of as a vector with data elements of type char (or wchar).

Associative Containers

Associative contains are containers that automatically sort their inputs when those inputs are inserted into the container. By default, associative containers compare elements using operator<.

  • A set is a container that stores unique elements, with duplicate elements disallowed. The elements are sorted according to their values.
  • A multiset is a set where duplicate elements are allowed.
  • A map (also called an associative array) is a set where each element is a pair, called a key/value pair. The key is used for sorting and indexing the data, and must be unique. The value is the actual data.
  • A multimap (also called a dictionary) is a map that allows duplicate keys. Real-life dictionaries are multimaps: the key is the word, and the value is the meaning of the word. All the keys are sorted in ascending order, and you can look up the value by key. Some words can have multiple meanings, which is why the dictionary is a multimap rather than a map.

Container Adapters

Container adapters are special predefined containers that are adapted to specific uses. The interesting part about container adapters is that you can choose which sequence container you want them to use.

  • A stack is a container where elements operate in a LIFO (Last In, First Out) context, where elements are inserted (pushed) and removed (popped) from the end of the container. Stacks default to using deque as their default sequence container (which seems odd, since vector seems like a more natural fit), but can use vector or list as well.
  • A queue is a container where elements operate in a FIFO (First In, First Out) context, where elements are inserted (pushed) to the back of the container and removed (popped) from the front. Queues default to using deque, but can also use list.
  • A priority queue is a type of queue where the elements are kept sorted (via operator<). When elements are pushed, the element is sorted in the queue. Removing an element from the front returns the highest priority item in the priority queue.
16.3 -- STL iterators overview
Index
16.1 -- The Standard Template Library (STL)

17 comments to 16.2 — STL containers overview

  • tunvir rahman tusher

    A super site….thanks

  • maalika

    For the vector program to compile correctly, I believe this:
    int nCount

    has to be changed to:
    size_t nCount
    or
    unsigned int nCount

    Is that true?

  • lsrinivasamurthy

    Not needed to change int nCount to some other type.
    It is just to iterate the loop.

  • Gaurav

    Very beautifully written. I always refer this website for c++. I can not see linked list lesson. Can anyone tell me if it is explained in detail because in this lesson it is written that we will talk more about linked list in future lessons.

    Thanks.

  • Hi Alex,
    Kudos to your efforts in maintaining this site. Bless you.
    A special request:
    Can you develop lectures for using data structures and algorithms in C++? I am a beginner C++ programmer and our course teacher has asked us to use STL for algorithms course.

  • nick

    Hi Alex
    Is it possible to build a vector classes several different types of data?

    • Alex

      Are you asking whether you can build a single std::vector that can hold more than one data type? The answer is yes, sort of, but not directly. There are a few ways to do this:
      1) Build a std::vector of a struct, class, or union that contains multiple types.
      2) Build a std::vector of a pointer to a base class, and then insert objects of derived classes into the vector.

      There may be others.

  • nick

    Hi alex
    1. Why not return bool
    2. Will be more optimized code comment

    • Alex

      I don’t understand your question.

      • nick

        Hi Alex
        I ask of you to compile code
        If memory allocation is done properly then why not set a boolean variable in derived class

        • Alex

          I still don’t understand what you’re asking. You’re referring to this line of code:

          One of two things will happen here. Either:
          1) The derived class will be allocated, and the address assigned to base pointer p. If you get a valid address for p, you know the derived class allocated properly.
          2) The system will be out of memory, or the allocation of the derived class will fail for some other reason (e.g. the constructor threw an exception), in which case an exception will be thrown for you to handle.

          If P exists, it was created correctly. So why would it need a boolean to track whether it was allocated properly?

  • nick

    Hi Alex :
    Now :
    I only have problems in the derived class with a Boolean variable
    run online : http://cpp.sh/4crl

    • Alex

      Aah, I see. The problem is that you’ve declared a vector of base. When you push_back a derived, the base portion of derived is copied into your vector. So when you call it->print(), it’s calling the base version because there is no derived portion of the class.

      You can solve this by making the vector a vector of base* instead of base.

  • nick

    thanks Alex;

Leave a Comment

Put C++ code inside [code][/code] tags to use the syntax highlighter

  

  

  

10 + nineteen =