Sorted Associative Containers

Sorted Associative Containers

Sorted associative containers store elements in a sorted order based on their keys. This allows for efficient retrieval and manipulation of elements. 

Here are the main sorted associative containers in C++:

  • set<Key> : Supports a unique set of keys, and provides for fast retrieval of keys
  • multiset<Key> : Supports duplicate keys, and provides for fast retrieval of keys.
  • map<Key, T> : Supports a unique set of keys and associated values of a type T;  provides fast retrieval of a value based on its key.
  • multimap<Key, T> : Supports duplicate keys and associated values of a type T;  provides fast retrieval of a value based on its key.

The set Sorted Associative Container

Here’s an example of the use of a set:

//
//  main.cpp
//  STL Sorted Associative Containers
//
//  Created by Bryan Higgs on 10/23/24.
//

#include <iostream>
#include <set>
#include <vector>

#include "Make.h"

int main(int argc, const char * argv[])
{
  char sentence[] = "A little knowledge is a dangerous thing";
  std::vector<char> v = make< std::vector<char> >(sentence);
  std::set<char> s;
  
  std::vector<char>::iterator vi;
  for (vi = v.begin(); vi != v.end(); vi++)
  {
    s.insert(*vi);
  }
  
  std::set<char>::iterator si;
  std::cout << '<';
  for (si = s.begin(); si != s.end(); si++)
  {
    std::cout << *si;
  }
  std::cout << ">" << std::endl;
  
  return 0;
}

Which uses the Make.h file we defined earlier:

//
//  Make.h
//  STL Sorted Associative Containers
//
//  Created by Bryan Higgs on 10/23/24.
//

#ifndef Make_h
#define Make_h

template <typename Container>
Container make(const char s[])
{
  return Container(&s[0], &s[strlen(s)]);
}

#endif /* Make_h */

… and outputs:

< Aadeghiklnorstuw>
Program ended with exit code: 0

The multiset Sorted Associative Container

Here’s an example of the use of a multiset:

//
//  main.cpp
//  STL Sorted Associative Containers
//
//  Created by Bryan Higgs on 10/23/24.
//

#include <iostream>
#include <set>
#include <vector>

#include "make.h"

int main(int argc, const char * argv[])
{
  char sentence[] = "A little knowledge is a dangerous thing";
  std::vector<char> v = make< std::vector<char> >(sentence);
  std::multiset<char> s;
  
  std::vector<char>::iterator vi;
  for (vi = v.begin(); vi != v.end(); vi++)
  {
    s.insert(*vi);
  }
  
  std::multiset<char>::iterator si;
  std::cout << '<';
  for (si = s.begin(); si != s.end(); si++)
  {
    std::cout << *si;
  }
  std::cout << ">" << std::endl;
  return 0;
}

It outputs:

<      Aaaddeeeeggghiiiklllnnnoorsstttuw>
Program ended with exit code: 0

The map Sorted Associative Container

Here’s an example of the use of a map:

//
//  main.cpp
//  STL Sorted Associative Containers
//
//  Created by Bryan Higgs on 10/23/24.
//

#include <iostream>
#include <map>    // for map class
#include <string>  // for string class

int main(int argc, const char * argv[])
{
  std::map<std::string, long> phoneDir;
  
  // Populate with some names/telephone numbers
  phoneDir["Lincoln"] = 5551212;
  phoneDir["Jefferson"] = 5556000;
  phoneDir["Washington"] = 5557890;
  
  std::string name;
  
  while (true)  // Look up number by name
  {
    std::cout << "Enter a name: ";
    if ( !(std::cin >> name) )
      break; // End of input
    
    if (phoneDir.find(name) != phoneDir.end())
    {
      std::cout << "Telephone number: "
                << phoneDir[name] << std::endl;
    }
    else
    {
      std::cout << "No entry found for: "
                << name << std::endl;
    }
  }
  
  return 0;
}

It outputs:

Enter a name: Gandhi
No entry found for: Gandhi
Enter a name: Lincoln
Telephone number: 5551212
Enter a name: Obama
No entry found for: Obama
Enter a name: Jefferson
Telephone number: 5556000
Enter a name: {Ctrl/D}
Program ended with exit code: 0

The multimap Sorted Associative Container

Here’s an example of the use of a multimap:

//
//  main.cpp
//  STL Sorted Associative Containers
//
//  Created by Bryan Higgs on 10/23/24.
//

#include <iostream>
#include <map>  // for multimap class
#include <string>  // for string class

int main(int argc, const char * argv[])
{
  std::multimap<std::string, long> phoneDir;
  // Populate with some names/telephone numbers
  // (Note that multimap does not support operator[].)
  phoneDir.insert( std::pair<std::string, long>("Lincoln", 5551212) );
  phoneDir.insert( std::pair<std::string, long>("Jefferson", 5556000) );
  phoneDir.insert( std::pair<std::string, long>("Washington", 5557890) );
  phoneDir.insert( std::pair<std::string, long>("Adams", 5551790) );
  phoneDir.insert( std::pair<std::string, long>("Adams", 5551810) );
  phoneDir.insert( std::pair<std::string, long>("Bush", 5551990) );
  phoneDir.insert( std::pair<std::string, long>("Bush", 5552001) );
  
  std::string name;
  
  while (true)  // Look up number by name
  {
    std::cout << "Enter a name: ";
    if ( !(std::cin >> name) )
      break;  // End of input
    
    std::multimap<std::string, long>::iterator match
              = phoneDir.lower_bound(name);
    
    if (match != phoneDir.end())
    {
      std::cout << "Telephone number(s):" << std::endl;
      std::multimap<std::string, long>::iterator matchEnd
              = phoneDir.upper_bound(name);
      
      for (; match != matchEnd; match++)
      {
        std::cout << match->first
                  << ": " << match->second << std::endl;
      }
    }
    else
      std::cout << "No entry found for: " << name << std::endl;
  }
  
  
  return 0;
}

It outputs:

Enter a name: Washington
Telephone number(s):
Washington: 5557890
Enter a name: Bush
Telephone number(s):
Bush: 5551990
Bush: 5552001
Enter a name: Obama
Telephone number(s):
Enter a name: {Ctrl/D}
Program ended with exit code: 0

The pair Class Template

Note the use of the pair class template.

pair is used to combine together two values that may be of different data types. Pair provides a way to store two heterogeneous objects as a single unit. The pair container is a simple container defined in <utility> header consisting of two data elements or objects. 

  • The first element is referenced as ‘first’ and the second element as ‘second’ and the order is fixed (first, second).

Sorted Associative Container Ordering

The template parameters of both the set and the multiset class templates are:

template <typename Key, 
		  typename Compare = less<Key>,
		  typename Allocator = allocator<Key> >

The template parameters of both the map and multimap class templates are:

template <typename Key, typename T,
		  typename Compare = less<Key>,
		  typename Allocator = allocator< pair<const Key, T> > >

Notice the Compare parameter.  It is the comparison function that is used to determine the order of the container’s elements.

You can override the default Compare function to change the ordering of the container, if you wish.

Next: Function Adapters

Table of Contents

→ Index