An Introduction to Ordered Associative Containers in C++

Associative containers are those that provide direct access to its elements for storage and retrieval purposes. The elements are accessed via keys, also known as search keys. There are four ordered and four unordered associative containers in C++ such as multiset, set, multimap, map and unordered_multiset, unordered_set, unordered_multimap, and unordered_map, respectively. This article focuses on the ordered associative containers and explains them with examples.

Overview

The C++ Standard Library defines a host of different types of powerful containers. These containers are nothing but a template-based version of different storage data structures. There also are other implementations, such as template-based implementation of algorithms and iterators in the Standard Library. But, the containers are specifically for storing objects. To make the container generic, it has to have been templatized. This provides the container the capability to store objects of almost any data type.

According to the style of operation, C++ container classes can be loosely categorized as sequence containers, associative containers, and container adapters. The difference lies in how each of them adapts the data structure. For example, the sequence container adapts the linear data structure, the associative container stores a value a key-value pair, and container adapters are basically sequence containers with some constraints.

All containers are equipped with a list of member functions and most of them share a subset of similar prototype of these functions. This poses great advantage for the programmer to quickly discern the meaning implied by the function name and understand immediately how to use them even if the type of container changes. Here, we focus on the associative container and only ordered ones.

Types of Sequence Containers

In the C++ Standard Library, there are four ordered associative containers and four unordered associative containers. The four ordered associative containers are multiset, set, multimap, and map. The four unordered associative containers are unordered_multiset, unordered_set, unordered_multimap, and unordered_map, respectively.

Note that the meanings implied by containers are same except one is strict about maintaining order among the objects stored whereas another one is not. This means that ordered ones store the keys in a sorted order, but the unordered ones have no such order. That’s all the difference. Here, we’ll take up only the ordered associative container and discuss it with examples.

Set Associative Container

The set associative containers store values in such a way that the storage and retrieval of the container object is fast. The idea of “set” is derived from the mathematical set theory which does not allow duplicate elements. The elements stored in the set associative container must be unique. Any attempt to insert a duplicate element in the set is ignored according to the mathematical behavior of the set. It supports bidirectional iterators but does not support random access iterators. If we consider that the order of the objects in the set is not required, we can simply use its unordered version, called unordered_set. Otherwise, both ordered set and unordered_set are same in their functionality.

A Quick Example

#include <iostream>
#include <set>
#include <iterator>

using namespace std;

int main()
{
   set< int, less< int > > intSet;
   intSet.insert(55);
   intSet.insert(22);
   intSet.insert(66);
   intSet.insert(77);
   intSet.insert(11);
   intSet.insert(99);
   intSet.insert(88);

   set<int>::iterator iter;
   for (iter = intSet.begin();iter!=intSet.end();++iter) {
      cout<<*iter<<" ";
   }
   auto val = intSet.insert(44);
   cout<<"n"<< *(val.first)<<
      (val.second ? " inserted: not duplicate"
                  : " not inserted: duplicate " ) <<endl;
   val = intSet.insert(55);
   cout<<"n"<< *(val.first)<<
      (val.second ? " inserted: not duplicate"
                  : " not inserted: duplicate " ) <<endl;

   return 0;

}

Multiset Associative Container

Multiset is a type of associative container which is similar to set but allows duplicate keys. As with set, the ordering of the elements is determined by the comparator function object. The comparator function object, such as less<int>, determines that the elements would be sorted in ascending order. Use greater<int> to sort elements in descending order. However, the objects stored in the associative container must support comparison according to the comparator function. Any custom data type stored in the ordered associative container must have an appropriate comparison operator. Like set, it also supports bidirectional iterators but not random-access iterators. The unordered counterpart of multiset is called unordered_multiset.

A Quick Example

#include <iostream>
#include <set>
#include <iterator>

using namespace std;

int main()
{
   multiset< int, less< int > > intMultiset;

   intMultiset.insert(55);
   intMultiset.insert(22);
   intMultiset.insert(66);
   intMultiset.insert(77);
   intMultiset.insert(11);
   intMultiset.insert(99);
   intMultiset.insert(88);

   set<int>::iterator iter;
   for (iter = intMultiset.begin();iter!=
      intMultiset.end();++iter) {
      cout<<*iter<<" ";
   }

   intMultiset.insert(44);
   intMultiset.insert(55);
   intMultiset.insert(55);
   intMultiset.insert(55);
   intMultiset.insert(55);
   cout<<"nAfter inserting many duplicate elements"<<endl;
   for (iter = intMultiset.begin();iter!=
      intMultiset.end();++iter) {
      cout<<*iter<<" ";
   }

   return 0;

}

Map Associative Container

The map associative container stores elements as key-value pairs. It uses unique keys to perform fast storage and retrieval of its associated values. With a single value associated with each unique key, it does not allow duplicates. There is one-to-one mapping of key-value pairs. We easily can specify the key to retrieve its associated value quickly. Elements can be inserted and removed from anywhere in the map. If we do not want the constraint of ordering the keys, we can use its unordered version, called the unordered_map.

A Quick Example

#include <iostream>
#include <map>
#include <iterator>
#include <string>

using namespace std;

int main()
{
   map< int, string, less< int > > weekdays;

   weekdays.insert(make_pair(1,"Sunday"));
   weekdays.insert(make_pair(3,"Tuesday"));
   weekdays.insert(make_pair(2,"Money-day"));
   weekdays.insert(make_pair(6,"Friday"));
   weekdays.insert(make_pair(4,"Wednesday"));
   weekdays.insert(make_pair(5,"Thursday"));
   weekdays.insert(make_pair(7,"Saturday"));

   for(auto day: weekdays)
      cout<<day.first<<" - "<<day.second<<endl;

   cout<<"n-------------------------------"<<endl;
   weekdays[2] = "Monday";   // Provide key in subscript
   for(auto day: weekdays)
      cout<<day.first<<" - "<<day.second<<endl;

   return 0;
}

Multimap Associative Container

Similar to the map, the multimap associative container is also an associative container. The elements of multimap also are stored in key-value pairs. The key elements are ordered according to the comparator function object. The main difference between map and multimap is that multimap allows duplicate keys to be stored in the container. The relationship between key-value pairs, therefore, is of one-to-many. If we do not want the constraint of ordering the keys, we can use its unordered version called the unordered_multimap.

A Quick Example

#include <iostream>
#include <map>
#include <iterator>
#include <string>

using namespace std;

int main()
{
   multimap< int, string, less< int > > box;

   box.insert(make_pair(1,"socks"));
   box.insert(make_pair(1,"socks"));
   box.insert(make_pair(1,"socks"));
   box.insert(make_pair(1,"socks"));
   box.insert(make_pair(1,"socks"));

   box.insert(make_pair(3,"T-Shirt"));
   box.insert(make_pair(2,"Gloves"));
   box.insert(make_pair(6,"Jacket"));
   box.insert(make_pair(4,"Shirt"));

   for(auto day: box)
      cout<<day.first<<" - "<<day.second<<endl;

   cout<<"There are "<<box.count(1)<<" pair of socks"<<endl;

   return 0;
}

Conclusion

Associative containers, such as set, multiset, map, and multimap are an implementation of non-linear data structure. Each of them has ordered and unordered versions. The ordering of the elements is based upon a comparator function object. There are many common functions among them. They are a time tested, robust, and efficient data structure implementation. They also are highly intuitive and very easy to use in everyday C++ programming.

Manoj Debnath
Manoj Debnath
A teacher(Professor), actively involved in publishing, research and programming for almost two decades. Authored several articles for reputed sites like CodeGuru, Developer, DevX, Database Journal etc. Some of his research interest lies in the area of programming languages, database, compiler, web/enterprise development etc.

More by Author

Get the Free Newsletter!

Subscribe to Developer Insider for top news, trends & analysis

Must Read