Many people who either begin C++ as beginners, or are coming from another language will always start off by using the Array Container. They fail to realize however, that there are alot of other types of Containers in C++, that are usually better for many scenarios. In this article, we are going to compare 3 C++ containers, Arrays, Vectors and Lists to see which is the better container type.
Each of them has their own unique characteristics, which makes them shine in a certain scenario. We’ll discuss these characteristics, and explain when to use either the Arrays, Vectors or Lists.
Arrays
The most standard type of container used in C++. There isn’t much to say on them, as they are fairly “normal” and straightforward.
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. Arrays are more suited to tasks which require a fixed size. (The old C style, malloc and realloc functions are not recommended).
Vectors
Pros: The biggest benefit that Vectors provide, is the automatic memory management that makes your coding process much simpler. You don’t have to worry about allocating space, or re-sizing the Vector once the limit of values has been reached. Vectors automate the whole process by automatically doubling it’s capacity every time the limit is reached.
Another really great feature of the Vectors is that they are templates. This means you can literally store almost anything inside them. From simple integers, to actual Class objects to regular and smart pointers, Vectors can do it all. Not to say you can’t do the same thing with other Container types, but it’s far easier and simpler with Vectors, and the various functions that it supports.
A vector is aware of it’s size at all times. So you can simply use the size() function to return the number of elements currently inside it.
#include <vector>
void main() {
vector<int> vector1;
}
Cons: One slight performance handicap with Vectors is when you are adding in elements. Appending values is really fast, but inserting a value in the middle requires all the values after it to be reallocated to make space for the new value. The time complexity for insertion and deletions in Vectors is O(n).
Another slight annoyance is that since vectors copy over their objects to a new vector when resizing, this can invalidate iterators or pointers that point to any element in that vector group. (You can get around this by using smart pointers).
Lists
Lists 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 (another data structure). 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.
Another obvious benefit over Vectors is that it doesn’t need to resize itself when adding new elements. So it basically has the Dynamically managed benefit without the problem that can occur with vectors. Likewise, if you remove an element from the list, iterators or pointers do not become invalid.
#include <list>
void main() {
list<int> list1;
}
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.
Conclusion
Generally speaking, if you are dealing with something of fixed size, Arrays are a great choice. However, if you are dealing with something that needs to have values added and removed, Vectors are superior.
In any case, for the average programmer and 99% of use cases, you shouldn’t be too concerned with performance. You should primarily aim for the Container type, which you find easier to work with and manage. For personal experience, I would recommend using the vector container type by default, and only switching to Arrays or Lists if the situation requires it.
You might find that in certain circumstances, Vectors may be causing a few issues. In that case I’ve found that switching to lists was a good idea. As mentioned earlier, lists don’t have some of the issues that vectors do, which make it a good substitute. Hence, we can say that for places where you want to do alot of insertions or deletions, lists would be better.
This marks the end of the C++, Arrays vs Vectors vs Lists Article. Any suggestions or contributions for CodersLegacy are more than welcome. Questions regarding the tutorial content can be asked in the comments section below.