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.6 -- 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 containers 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.

As of C++11, the STL contains 6 sequence containers: std::vector, std::deque, std::array, std::list, std::forward_list, and std::basic_string.

  • 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 containers 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
16.1 -- The Standard Library

61 comments to 16.2 — STL containers overview

  • salah

    are the elements of the 'list' and 'deque' sequential in memory like an array?

    assume we have 'list' of 'int'  'list[0] = 3 (in memory location 1000)'

    would list[1] = 4 be in memory location 1004 ? or you mean by 'sequential ' that they sorted as the programmer enter them, but not important they are sequential in their location?

  • Gabe

    Why aren't the code example for Sequence Containers properly indented and shown inside of "

    ?" Even 16.3--STL iterators overview lacks it.

  • JasonA

    In the section on sequence containers, why don’t you have bullets with information/examples for array and forward_list ? Or at least give them a brief mention like you did for vector, deque and list.

    And why do you mention “STL strings“ but not “basic_string“ in the final bullet ?

    This just feels “mysterious”, and I guess (short of reading lesson by lesson or going back to the Index), that I’m missing something ...

  • AbraxasKnister

    What further reading is recommended for the STL containers? I'm trying to read Effective STL by Scott Myers since that's STL focused but it looks a lot like I should get to know the container classes and iterators he's talking about before doing that so I'd like to know what fills the gap here. I want more than a reference since that doesn't tell me when to choose which and how they defer exactly. I'd love to have a look at all the "...Effective..." books by him since they seem to give sound advice to intermediate to advanced programmers but I'm not sure whether the older one are still mostly applicable.

  • Anthony

    I'm gradually getting to know the STL. However, I'm finding std::ref confusing.

    Since std::ref is often used with std::bind, I made a simple version of std::bind() which I've called bond() better to understand how std::ref() works:

    I know what std::ref does, but I don't know how it works. To demonstrate what I mean:

    On the other hand:

    This is, of course, exactly how std::ref is supposed to work. But how does it do this exactly? From https ://, I can see that the object returned by std::ref is a std::reference_wrapper, which stores its internal object as a pointer. This makes sense, since pointers are ultimately the mechanism by which references are implemented, and I've somehow got to have access to the address of the internal object to achieve the desired behaviour. So, to begin with, I believe that a std::reference_wrapper object is copy-constructed (i.e. by value) through the bond() helper function into member variable bond::arg_ of the bond_t object.

    If the object is *not* a std::ref, what happens next is simple. Let's say that it's an int with value 5, as in the example code. The line 'return func_(arg_);' is executed, passing the int to the function stored in the function pointer, and '5' is printed. But, if the object is a std::ref, how can I make a deferenced pointer to an internal object be printed? Because this is what needs to happen for the '7' to be printed. Perhaps it's an overload? But what overload and where?

    Thanks :)

    • `std::ref` isn't a type, it's a function that returns an `std::reference_wrapper`.
      `std::reference_wrapper<T>` has a conversion operator to `T&` ( ) which gets used when you call `print`.

      • Anthony

        Oops, that was a typo calling std::ref an object. Yes, the object returned is the std::reference_wrapper object. I have not seen a conversion operator to T& before.

        So am I correct in saying that it is specifically the 'int&' in the 'void print(int& n)' function that triggers the use of the std::reference_wrapper's T& overload? Or put another way, it's the fact that the function pointer 'S(*func_)(T&)' has the 'T&'?

      • Anthony

        At the risk of sounding like an annoying child who keeps asking 'why?', can I ask why the conversion operator & gets used when one calls the function in line 11? :)

        I've been experimenting, and I'm surprised to see that the result is the same whether a reference is used as the argument in the function pointer or not. I.e. this works the same:

        So when you say that the conversion operator get used, I'm just not seeing how. I thought perhaps that the copy constructor and assignment operator had been altered to use a reference, but that isn't it I guess. I'm lost!

        • All of these are fine. When the types don't match, eg. `std::reference_wrapper<int>` and `int`, your compiler will try to convert them. `std::reference_wrapper<int>` can be converted to `int&` and `int&` can be converted to `int`.

          > can I ask why the conversion operator & gets used when one calls the function in line 11?
          Yes go ahead.

          > // S = the return type, T = the class type
          Template names don't have to be single letters.

          • Anthony

            But.. but..

            When a std::reference_wrapper<int> object is passed into a @bond_t object, how does the compiler know to pass the @int, held as a pointer inside the @bond_t object, to @func_ as its @arg_?

            And I know your answer will be:
            >`std::reference_wrapper<T>` has a conversion operator to `T&` ( ) which gets used when you call `print`.

            From that site, I see there's this:
            operator T& () const noexcept;

            This.. erm.. how does this work? I'm sorry, but I can't see how this grabs the pointer, dereferences it, and passes it to @func_.


            So perhaps it's defined like this:


            If that's the case, then I'm just having problems visualising what a T& operator is. Something like a ++ operator, on the other hand, is easy to visualise.

            • Give lesson 9.10 ( ) another read, seems like this is what's giving you trouble.
              Please edit comments instead of deleting and re-posting them. Syntax highlighting works after refreshing the page.

            • Anthony

              I'm inserting an edit here, since it makes sense to the flow. I meant:

              • Anthony

                Finally I understand:) Thank you so much for your patience. Yes, I did not see that it was a cast overload. Anyway, I wrote my own version of std::ref<T> and std::reference_wrapper<T> to test it out, and yes it works!:  

  • Dars

    Which category does std::pair belong to ?

  • sbj

    why you don't include "using namespace std" in any of your code ? Is there any specific reason or you are used to write code like this.

  • Test Code tag

  • Akshay Chavan

    Hi Alex,
    Forgive me if this is a somewhat silly question: In the vector and deque code samples, why have you used variable names like "nCount" and "nIndex" instead of "count" and "index" respectively?

  • Tyler

    I hope this isn't too trivial, however the link at the top that says,"10.4 -- Container Classes" I think is supposed to say, "10.6 -- Container Classes".

  • Martin

    In the Associative Containers section I am missing the std::unordered_map, sometimes called hashmap. Is there a reason you left that one out? I think it is quite important in many cases.

    • Alex

      std::unordered_map was defined in C++11, and this lesson hasn't been rewritten to be C++11 compliant yet. I'm intending to do a whole chapter on containers soon, so this lesson will probably disappear and get replaced by a much weightier discussion.

  • Rohit

    Hi Alex!
    which is prefered to use vector or deque? and why?

    • Alex

      You should use whichever one is more appropriate for the problem you are trying to solve. I'm intending to rewrite this lesson some point soon to talk more about the pros and cons of the various containers.

  • manikanth

    hello Alex,
    As we know Sequence containers are container classes that maintain the ordering of elements in the container in a continuous dynamic array but how come list can be called a sequence container.

    • Alex

      To be a sequence container, a class must allow the user to access elements in sequential order without recursion. Linked lists meet this criteria by allowing you to start from the head and walk through each node in sequence until you reach the tail.

  • I want to know more about iterators In c++

  • What about std::array? Isn't that a sequence container too?

  • Lokesh

    #typo "Associative contains are containers that automatically" -> containers are containers

  • Bede

    Hi Alex, a typo: "containerss" --> "containers"

  • nick

    thanks Alex;

  • nick

    Hi Alex :
    Now :
    I only have problems in the derived class with a Boolean variable
    run online :

    • 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.

      • Mekacher Anis

        please help , these things I can't understand :
        _ why there is a semicolon after the derived constructor
        _ how can u push_back a base* to normal base vector
        and thank's

      • Shantanu

        Could you please elaborate your response?
        I understood what he is asking, but your solution to the problem isn't clear to me.

        • Alex

          Ah, yes, I think I answered a question that he wasn't asking. :)

          Rather than answer this question here, let me direct you to the lesson on object slicing which discusses the underlying causes of exactly this case in more detail (because it's a common mistake), and includes solutions to the issue.

  • 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
    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.

  • 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.

  • 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.


  • lsrinivasamurthy

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

  • maalika

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

    has to be changed to:
    size_t nCount
    unsigned int nCount

    Is that true?

  • tunvir rahman tusher

    A super site....thanks

Leave a Comment

Put all code inside code tags: [code]your code here[/code]