C++ is a vast language that has a variety of different ways of performing any task. Similarly, when it comes to storing data, and accessing it from “containers”, C++ has several different types to choose from. We have the more common container types like Arrays and Vectors, as well as other several important ones like map and queue.
Each has it’s own unique set of characteristics, which allows it to excel for the tasks it was designed for. In this tutorial we will be discussing the various types and briefly describing them along with examples. If a specific type interests you, you can follow the included tutorial link for a more detailed explanation.
Container Types
There are three main categories of Containers in C++. We’ll discuss each of them in a separate section, starting with the most used type, Sequence Containers.
Sequence Containers
Array: The most standard type of container used in C++ to store data. The Array takes linear time for insertion and deletion of elements. Accessing any index in the array with the [] operator is always really fast compared to the some of the other types (like vectors). Arrays can be dynamically managed to some extent, through the use of the new[] and delete[] commands, but for more complex cases, you’ll find that other dynamically managed containers are better.
Vector: A Dynamic Alternative to Arrays, Vectors have three things that make them really handy. First, they are Dynamically managed so you don’t have to worry about it’s capacity while adding elements. Second, Vectors are templates, allowing you to freely use any datatype or Class with them, without any loss in functionality. Lastly, a Vector has a whole set of useful functions ( e.g: size() ). There are a few problems that you might run into while using them, but those can be easily avoided.
List: They have a linked list (a type of data structure) kind of format, where each element stores the address of the element before and after it. So it’s basically a double-linked list. Due to this, you can insert and delete elements at a time complexity of constant speed, O(1) which is pretty fast. On the same note, Lists have non contiguous memories, due to the use of linked list styled pointers.
Lists however, aren’t good at random access and require O(n) time to reach a random “nth” index. Furthermore, each element requires extra space as it needs to hold the addresses for the previous and the next address in the list.
Deque: A rather complex container, which is an abbreviation for “Double Ended Queue”. Similarly to a Queue, it can easily add in elements to the end of this Queue, but it can also do the same for the front. Hence the name ‘Double Ended”.
They are similar in nature to vectors, but more efficient with the insertion and deletion of elements in the front and back. Unlike Vectors however, they are not guaranteed to store memory contiguously, instead using a series of chunks. This has the benefit of allowing them to grow more efficiently when adding in elements.
Forward_list: These are containers that allow insert and erase operations anywhere within the sequence in constant time O(1). Forward lists are implemented using single-linked lists. This works by using pointer for each element, which store the memory address of the next element in the list.
Forward lists are more memory efficient than lists, as they only need to store one pointer per element. However, they can only be forward iterated.
Associative Containers
Associative Containers are used to store data in a sorted order. This makes it faster to search through and access data, and the cost of insertion’s being a littler slower.
Set: What makes the C++ Set Container different from other Associative Containers is that it stores “unique and sorted” data. By unique, we mean there are no duplicates of the same data element in this container. Any duplicates which are entered will be automatically removed.
Multi-Set: A multi-set container is pretty much the exact same thing as a set with one difference. Unlike a Set, a Multi-Set does not a duplicate filter, meaning it only stores sorted data, not “unique and sorted” data. Other than this, all methods and other related functions work in the exact same manner.
Map: What makes the Map Container different from other Associative Containers is that it stores data in the form key-value pairs. The Key is sort of like the Identification feature for the value, used to access and retrieve values from the Map. Keys must be unique, while values may be non-unique.
If you’ve ever used Dictionaries in Python, Maps in C++ are pretty much the same thing.
Multi-Map: A Multi-Map is just like a map, with one difference. They Key’s do not have to be unique, and can be duplicates of each other. However, the Value’s of these duplicate Key’s must be unique. In short, either the Key must be unique, or the Value. You cannot have two identical Key-Value pairs in a Multi-Map.
Container Adaptors
stack: The Stack is a very important data structure, widely used in all of programming. It follows the concept of L.I.F.O (Last-in, First out). Another way of saying this would be, First in, Last out. Any new element added to the stack is placed “on top” of the stack.
queue: The Queue is another important Data Structure like the stack, but with a fundamental difference. Queue’s follow the concept of F.I.F.O, also known as First In, First out. If 5 elements are added in the Queue, they will be taken out in the same order they were inserted (with the first element being the first, and last element being the last to be removed).
priority-queue: The Priority Queue is a variant of the Queue Data Structure. It’s just like a regular Queue but has the concept of priority, which means those elements with the highest priority will be removed from the Queue first.
This marks the end of the C++ Containers Tutorial. Any suggestions or contributions for CodersLegacy are more than welcome. Questions regarding the tutorial content can be asked in the comments section below.