Sequence and Associative Containers in the C++ Standard Library

Instead of jumping right in giving code examples of a set and a multiset, I should have started by covering some of the different kinds of containers available in the c++ standard library. If you continue to read this blog, that soon won’t come as a surprise to you. Much like my writing, I sort of think in leaps and jumps as well.

From the book “The C++ Standard Library: A Tutorial and Reference”:

There are two general kinds of containers:

1. Sequence containers are ordered collections in which every element has a certain position. This position depends on the time and place of the insertion, but it is independent of the value of the element. For example, if you put six elements into a collection by appending each element at the end of the actual collection, these elements are in the exact order in which you put them. The STL contains three predefined sequence container classes: vector, deque, and list.

2. Associative containers are sorted collections in which the actual position of an element depends on its value due to a certain sorting criterion. If you put six elements into a collection, their order depends only on their value. The order of insertion doesn’t matter. The STL contains four predefined associative container classes: set, multiset, map, and multimap.

These seven different types of containers can be used, separately and together, to solve a multitude of common problems while programming. Let’s start with the sequence containers.

Sequence Containers:

Sequence containers have their advantage in rapidly storing information in an efficient manner. Two of the three sequence containers also provide for random access.

Vectors were created to start with nothing and add elements to one side (the end). While it is possible to add elements in other places or sort the elements into some kind of order, vectors operate fastest when new elements are simply dumped at the end. Vectors provide for random access. If you have 50 objects stored in a vector, you can easily jump to object 25 to see what it is.

Deques, much like vectors, were created to add elements quickly at the end. The difference between a deque and vector is that the deque can operate at the same speed regardless of which end the object is added to. You can add objects to the front of the queue as fast as you can add them to the rear of the queue. Deques also provide random access. Just like a vector, if you have 50 objects stored in a deque, you can easily jump to object 25 and see what it is.

Lists have the advantage that they can add elements anywhere without suffering a speed penalty. You can add objects to the beginning, anywhere in the middle, and at the end without loss of speed. This versatility, however, comes at the cost. You can’t get to an object in the middle of the list without following the list from one end or the other. To put it another way, there is no random access of a list. If there are 50 objects in the list, to find out what object 10 is you must start at the beginning and work you way up to the desired object.

Now let’s look at the associative containers.

Associative Containers:

Associative containers have their advantage in sorting. While they can generally store information quickly, the larger they grow, the slower they store information. Also, since they are sorted containers, they don’t provide for random access. You can’t, for instance, ask it which element is in the 5th position since they use a binary tree to store information.

Sets and multisets are the same except a set will not allow duplicate entries and a multiset will. When you add an object to either, there isn’t a position associated with the object in the traditional sense. The object is simply added to a binary tree. The advantage of storing objects in this manner is that they are sorted and searching for a specific object by type instead of by location is both quick and easy. In the worst case scenario a set or multiset will find the desired object as fast as if it were stored in a vector. Typically it will be found much, much faster.

Maps and multimaps: like sets and multisets, the only difference between a map and a multimap is whether the container will allow duplicates. A map will not allow duplicate objects and a multimap will. Maps and multimaps work almost exactly like sets and multisets. The difference is that each stored object is actually a pair of objects. Each map object contains a key and a value object called a key/value pair. The key is used to store the map object in the binary tree. The value goes along for the ride. This would allow you to, for instance, use a last name as a key and a first name as a value. This would create a sorted container containing a map sorted by the person’s last name.

Advertisements

Published by

Marisa

I am a writer of words, a thinker of thoughts, a changer of genders, and a queerer of life. I am an antagonist of the ordinary; and while I do tolerate it, I also look at it with contempt.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s