Containers

Overview

This page goes over the various type of containers that are available in C++. These containers cover the many different way in which you might wish to store data.

The following containers are sorted alphabetically.

arrays

Header #include <deque> 
Full Path std::array 
Time Complexity Random Access: \( \mathcal{O}(1) \)
Insertion At Start Or End: n/a
Insertion In Middle: n/a

Of course, we will always be able to use C-style arrays in C++, which are normally just used and passed around as a pointer to the element type. However, some issues with standard C-style arrays include; no built-in memory management, no bounds checking, and no information about the size of the array is carried with it (so you usually have to indicate the size by passing in another variable to functions).

C++11 provides us with a std container which encapsulates a fixed-size array.

Note that a std::array is more restrictive than a C-style array in that the size must be provided at compile time. e.g.:

If you want a runtime resizable array-like container, reach for a std::vector  instead.

Before C++11 introduced std::array, you could use the Boost equivalent. Boost provides a templated class to create fixed-size arrays of a particular type. To create a fixed array that stored 6 doubles, you would use:

Note that boost::array provides exactly the same syntax as std::array for initializaiton. The first template parameter is the type you wish the array to store, and the second parameter is the number of elements in the array.

deque

Header #include <deque> 
Full Path std::deque 
Time Complexity Random Access: \( \mathcal{O}(1) \)
Insertion At Start Or End: \( \mathcal{O}(1) \)
Insertion In Middle: \( \mathcal{O}(n) \)

deque stands for double-ended queue (usually pronounced similar to “deck”). It is an indexed sequence container used for storing data in C++. It is dynamically sized, and can be quickly expanded/contracted both at the front and back.

A deque is not guaranteed to store all of it’s data in a continuous memory sequence. Thus it’s data cannot be accessed via pointer addition (unlike a vector).

Example

map/multimap

std::map is an associative C++ container. Is is similar to a dictionary in Python. While an array or vector only allows you to store and retrieve data using an integer, a map allows you to store and retrieve data via any other object.

For example, we could store peoples data based on their first name:

We could now store a value into the map:

Notice how we can use a string to index into the map, rather than an integer!

We can retrieve values from a map by using the find() method.

Different Ways Of Adding An Element To A Map

emplace was added to  std::map in C++11. It allows you to pass in the arguments used to create a new element in the map separately. emplace() then forwards these arguments onto the element’s constructor.

set/multiset

A set is an associative, ordered container in where the value of the element also serves as a key (as opposed to a map, where the key is different from the value). Another interesting property of sets is that the elements are const, that is, you cannot modify them directly. However, you can add and remove elements.

The C++ standard does not specify how the library must implement a std::set. However, std::set  is normally implemented behind-the-scenes as binary search trees.

Each element in a set must be unique. If you want to store multiple elements of the same value, use a multiset instead.

vector

A std::vector is your bread-and-butter array type in C++. It supports the insertion and removal of elements and dynamic resizing at run-time.

myVector[<element index>] provides the standard, no bounds checking way of getting and setting elements within the vector. However, if you want bounds checking, you can use .at()  instead.

Since C++11, you can get a C-style pointer to the array using the data()  method:

The C++ standard guarantees that the data will be stored in a contiguous memory space, and accessible like a C-style array.

 

Posted: December 14th, 2016 at 2:03 am
Last Updated on: September 26th, 2017 at 6:19 am