In this article, which is the second in the C++ Standard Template Library series we will be taking a look at Containers and to be more precise we will be looking into the Vector Sequence container.
In the first article from the C++ Standard Template Library series we took a general overview of what the Standard Template Library is and we discussed the different components that make up the library.
We were able to introduce the concept of containers, algorithms and the data structures and how they all inter-operate together. If that is all new to you then I would advise you to go and read on the overview of the C++ Standard Template Library before proceeding with this article.
If you already read the first part of this series then you are in the right place and you may proceed.
The Types of Containers in the C++ Standard Template Library
Even though there are more, Containers in the C++ Standard Template Library can be classified into three major types namely:
- Sequence Containers
- Associative Containers
- Unordered Containers
Sequence Containers are basically implemented as arrays and linked lists. STL provides the vector, list, forward list, deque and array classes to handle these kinds of containers. One example is the Vector Sequence Container.
Associative containers generally implement the binary tree and are composed of set, multiset, map and multimap classes in C++ STL.
Unordered Containers generally make use of hash tables. STL provides classes for the unordered set, unordered multiset, unordered map, and unordered multimap.
In this article, we will cover the vector from the first category of Sequence Containers.
Sequence Containers
In order to use any of the Standard Template Library classes, the C++ programmer is required to include the relevant header files that contain the declaration of the needed classes.
As we are taking a closer look at vectors, lists, deques and arrays classes then the following header files would be included at the top of the C++ code in the format above. If you do not know how the code above works then you may be reading the wrong article.
There is a beginner C++ programming course being released soon on this website which covers all of these coding guidelines. Also, note that we will not be diving deep into the members of these Container classes as there is a lot of readily available STL reference material on the Internet.
The Vector Sequence Container
The std::vector is a sequence container that encapsulates dynamic size arrays. This means the elements are stored contiguously and the elements can be accessed through iterators or through offsets on regular pointers to elements as shown in the example below.
It is worth knowing that accessing the vector sequence container through offsets offers no range check as opposed to using iterators. As we saw in the previous article in this series, the preferred method of operating on STL Containers is through iterators where you get better range checking and it is faster to access elements in the array.
The code snippet below shows an iterator is used to traverse a vector in comparison to using the offset index.
Vector storage is automatically expanded and contracted as needed. Vectors usually occupy more space than static arrays, because of this anticipated growth. A vector does not need to reallocate memory each time an element is inserted, but only when the additional memory is exhausted therefore speeding up the insertions.
The efficiency of common operations on vectors in C++ is as follows:
- Fast insertion or removal of elements at the end O(1)
- Slow insertion or removal of elements at the beginning or in the middle of the vector O(n)
- Slow but constant random access O(1)
In the next article in the series on the C++ Standard Template Library, we will wrap up Sequence Containers and take a look at the linked list, the deque, and the STL array.
You can access the previous article in this series on C++ Standard Template Library Overview here.
Ref:
https://msdn.microsoft.com/en-us/library/cscc687y.aspx
Found this article interesting? Follow Brightwhiz on Facebook, Twitter, and YouTube to read and watch more content we post.