In this 3rd part of the C++ Standard Template Library tutorial we pick up from our previous article on Sequence Containers that focused mostly on the Vector. This tutorial builds on that content and adds the Linked list and the Deque.
Before we jump in to discuss the Linked list and the Deque, if you missed the beginning of this programming tutorial series then you might want to go back and read on the overview of the C++ Standard Template Library.Before we take a look at the Linked List which comes in the form of a list and a forward list. We want to keep things much simpler than they already are. So we will go ahead and discuss the Deque first then come back to the Linked list.
Deque
Deque so happens to be very similar in implementation to the vector with the major difference being one. The vector grows in one direction, which is the back while the deque can grow either in the front or the back ends.
Deque also has similar interfaces to the vector. It has fast inserts and removes at the beginning and the end. It comes with slow inserts and removes in the middle of the container and slow search.
Below is an example implementation of the deque in code.
Linked List (Or Simply List)
A linked list or just List is a doubly linked list. this means each element in the container has a pointer which points to the element before and after it. The advantage of this sort of Sequence Containers is that you get fast inserts and removes from anywhere on the list.
Other properties include slow searching and no random access. This means the linked list has no [] operator. The reason for the slow search in a list is because unlike vector, the elements of a linked list are not stored in contiguous memory.
Therefore there is a lot of swapping going on in and out of the cache to accommodate these elements and to read out the values.
The following is a sample code snippet showing the implementation of a Linked list.
Forward List (Forward Linked List)
There’s not much more we can say about the Forward linked list except that it is exactly like a list only that the pointers point to the next element in the sequence container.
The STL Array
This is the Standard Template library’s implementation of an array that allows you to use the STL function just like you would on a vector. Just like a normal array and unlike the vector, the STL array is fixed size. Secondly, the sizes of two arrays which differ in size are treated differently.
The sample code shows how you can use an STL array.
That is it for the topic of the Sequence containers in the C++ Standard Template Library. In the next article in this tutorial series, we will be looking at associative containers and discussing sets, multisets, maps, and multimaps.
Meanwhile you can always go back and brush up on the details about the vector in the C++ Standard Template Library.
Found this article interesting? Follow Brightwhiz on Facebook, Twitter, and YouTube to read and watch more content we post.