{"id":2197,"date":"2025-01-28T20:27:45","date_gmt":"2025-01-28T20:27:45","guid":{"rendered":"https:\/\/bhiggs.x10hosting.com\/PracticalCPlusPlusProgramming\/?page_id=2197"},"modified":"2025-01-28T21:43:11","modified_gmt":"2025-01-28T21:43:11","slug":"sorted-associative-containers","status":"publish","type":"page","link":"https:\/\/bhiggs.x10hosting.com\/PracticalCPlusPlusProgramming\/index.php\/topics\/c-details\/the-standard-template-library-2\/sorted-associative-containers\/","title":{"rendered":"Sorted Associative Containers"},"content":{"rendered":"\n

<\/span>Sorted Associative Containers<\/span><\/h2>\n\n\n\n

Sorted associative containers<\/strong><\/em> store elements in a sorted order based on their keys. This allows for efficient retrieval and manipulation of elements. <\/p>\n\n\n\n

Here are the main sorted associative containers in C++:<\/p>\n\n\n\n

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

    <\/span>The set Sorted Associative Container<\/span><\/h3>\n\n\n\n

    Here’s an example of the use of a set<\/strong>:<\/p>\n\n\n\n

    \n
    \n
    <\/path><\/path><\/svg><\/span>
    \/\/<\/span><\/span>\n\/\/  main.cpp<\/span><\/span>\n\/\/  STL Sorted Associative Containers<\/span><\/span>\n\/\/<\/span><\/span>\n\/\/  Created by Bryan Higgs on 10\/23\/24.<\/span><\/span>\n\/\/<\/span><\/span>\n<\/span>\n#include<\/span> <\/span><iostream><\/span><\/span>\n#include<\/span> <\/span><set><\/span><\/span>\n#include<\/span> <\/span><vector><\/span><\/span>\n<\/span>\n#include<\/span> <\/span>"Make.h"<\/span><\/span>\n<\/span>\nint<\/span> <\/span>main<\/span>(<\/span>int<\/span> <\/span>argc<\/span>, <\/span>const<\/span> <\/span>char<\/span> <\/span>*<\/span> <\/span>argv<\/span>[])<\/span><\/span>\n{<\/span><\/span>\n  <\/span>char<\/span> sentence[] = <\/span>"A little knowledge is a dangerous thing"<\/span>;<\/span><\/span>\n  <\/span>std<\/span>::vector<<\/span>char<\/span>> v = <\/span>make<\/span>< <\/span>std<\/span>::<\/span>vector<\/span><<\/span>char<\/span>> >(sentence);<\/span><\/span>\n  <\/span>std<\/span>::set<<\/span>char<\/span>> s;<\/span><\/span>\n  <\/span><\/span>\n  <\/span>std<\/span>::<\/span>vector<\/span><<\/span>char<\/span>>::iterator vi;<\/span><\/span>\n  <\/span>for<\/span> (vi = <\/span>v<\/span>.<\/span>begin<\/span>(); vi != <\/span>v<\/span>.<\/span>end<\/span>(); vi++)<\/span><\/span>\n  {<\/span><\/span>\n    <\/span>s<\/span>.<\/span>insert<\/span>(*vi);<\/span><\/span>\n  }<\/span><\/span>\n  <\/span><\/span>\n  <\/span>std<\/span>::<\/span>set<\/span><<\/span>char<\/span>>::iterator si;<\/span><\/span>\n  <\/span>std<\/span>::cout << <\/span>'<'<\/span>;<\/span><\/span>\n  <\/span>for<\/span> (si = <\/span>s<\/span>.<\/span>begin<\/span>(); si != <\/span>s<\/span>.<\/span>end<\/span>(); si++)<\/span><\/span>\n  {<\/span><\/span>\n    <\/span>std<\/span>::cout << *si;<\/span><\/span>\n  }<\/span><\/span>\n  <\/span>std<\/span>::cout << <\/span>">"<\/span> << <\/span>std<\/span>::endl;<\/span><\/span>\n  <\/span><\/span>\n  <\/span>return<\/span> <\/span>0<\/span>;<\/span><\/span>\n}<\/span><\/span><\/code><\/pre><\/div>\n<\/div>\n\n\n\n
    \n
    Which uses the Make.h<\/strong> file we defined earlier:<\/p>\n\n\n\n
    <\/path><\/path><\/svg><\/span>
    \/\/<\/span><\/span>\n\/\/  Make.h<\/span><\/span>\n\/\/  STL Sorted Associative Containers<\/span><\/span>\n\/\/<\/span><\/span>\n\/\/  Created by Bryan Higgs on 10\/23\/24.<\/span><\/span>\n\/\/<\/span><\/span>\n<\/span>\n#ifndef<\/span> Make_h<\/span><\/span>\n#define<\/span> Make_h<\/span><\/span>\n<\/span>\ntemplate<\/span> <<\/span>typename<\/span> <\/span>Container<\/span>><\/span><\/span>\nContainer<\/span> <\/span>make<\/span>(<\/span>const<\/span> <\/span>char<\/span> <\/span>s<\/span>[])<\/span><\/span>\n{<\/span><\/span>\n  <\/span>return<\/span> <\/span>Container<\/span>(&<\/span>s<\/span>[<\/span>0<\/span>], &<\/span>s<\/span>[<\/span>strlen<\/span>(s)]);<\/span><\/span>\n}<\/span><\/span>\n<\/span>\n#endif<\/span> \/* Make_h *\/<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
    … and outputs:<\/p>\n\n\n\n
    < Aadeghiklnorstuw>\nProgram ended with exit code: 0<\/strong><\/code><\/pre>\n<\/div>\n<\/div>\n\n\n\n
    <\/span>The multiset Sorted Associative Container<\/span><\/h3>\n\n\n\n
    Here’s an example of the use of a multiset<\/strong>:<\/p>\n\n\n\n
    \n
    \n
    <\/path><\/path><\/svg><\/span>
    \/\/<\/span><\/span>\n\/\/  main.cpp<\/span><\/span>\n\/\/  STL Sorted Associative Containers<\/span><\/span>\n\/\/<\/span><\/span>\n\/\/  Created by Bryan Higgs on 10\/23\/24.<\/span><\/span>\n\/\/<\/span><\/span>\n<\/span>\n#include<\/span> <\/span><iostream><\/span><\/span>\n#include<\/span> <\/span><set><\/span><\/span>\n#include<\/span> <\/span><vector><\/span><\/span>\n<\/span>\n#include<\/span> <\/span>"make.h"<\/span><\/span>\n<\/span>\nint<\/span> <\/span>main<\/span>(<\/span>int<\/span> <\/span>argc<\/span>, <\/span>const<\/span> <\/span>char<\/span> <\/span>*<\/span> <\/span>argv<\/span>[])<\/span><\/span>\n{<\/span><\/span>\n  <\/span>char<\/span> sentence[] = <\/span>"A little knowledge is a dangerous thing"<\/span>;<\/span><\/span>\n  <\/span>std<\/span>::vector<<\/span>char<\/span>> v = <\/span>make<\/span>< <\/span>std<\/span>::<\/span>vector<\/span><<\/span>char<\/span>> >(sentence);<\/span><\/span>\n  <\/span>std<\/span>::multiset<<\/span>char<\/span>> s;<\/span><\/span>\n  <\/span><\/span>\n  <\/span>std<\/span>::<\/span>vector<\/span><<\/span>char<\/span>>::iterator vi;<\/span><\/span>\n  <\/span>for<\/span> (vi = <\/span>v<\/span>.<\/span>begin<\/span>(); vi != <\/span>v<\/span>.<\/span>end<\/span>(); vi++)<\/span><\/span>\n  {<\/span><\/span>\n    <\/span>s<\/span>.<\/span>insert<\/span>(*vi);<\/span><\/span>\n  }<\/span><\/span>\n  <\/span><\/span>\n  <\/span>std<\/span>::<\/span>multiset<\/span><<\/span>char<\/span>>::iterator si;<\/span><\/span>\n  <\/span>std<\/span>::cout << <\/span>'<'<\/span>;<\/span><\/span>\n  <\/span>for<\/span> (si = <\/span>s<\/span>.<\/span>begin<\/span>(); si != <\/span>s<\/span>.<\/span>end<\/span>(); si++)<\/span><\/span>\n  {<\/span><\/span>\n    <\/span>std<\/span>::cout << *si;<\/span><\/span>\n  }<\/span><\/span>\n  <\/span>std<\/span>::cout << <\/span>">"<\/span> << <\/span>std<\/span>::endl;<\/span><\/span>\n  <\/span>return<\/span> <\/span>0<\/span>;<\/span><\/span>\n}<\/span><\/span><\/code><\/pre><\/div>\n<\/div>\n\n\n\n
    \n
    It outputs:<\/p>\n\n\n\n
    <      Aaaddeeeeggghiiiklllnnnoorsstttuw>\nProgram ended with exit code: 0<\/strong><\/code><\/pre>\n<\/div>\n<\/div>\n\n\n\n
    <\/span>The map Sorted Associative Container<\/span><\/h3>\n\n\n\n
    Here’s an example of the use of a map<\/strong>:<\/p>\n\n\n\n
    \n
    \n
    <\/path><\/path><\/svg><\/span>
    \/\/<\/span><\/span>\n\/\/  main.cpp<\/span><\/span>\n\/\/  STL Sorted Associative Containers<\/span><\/span>\n\/\/<\/span><\/span>\n\/\/  Created by Bryan Higgs on 10\/23\/24.<\/span><\/span>\n\/\/<\/span><\/span>\n<\/span>\n#include<\/span> <\/span><iostream><\/span><\/span>\n#include<\/span> <\/span><map><\/span>    <\/span>\/\/ for map class<\/span><\/span>\n#include<\/span> <\/span><string><\/span>  <\/span>\/\/ for string class<\/span><\/span>\n<\/span>\nint<\/span> <\/span>main<\/span>(<\/span>int<\/span> <\/span>argc<\/span>, <\/span>const<\/span> <\/span>char<\/span> <\/span>*<\/span> <\/span>argv<\/span>[])<\/span><\/span>\n{<\/span><\/span>\n  <\/span>std<\/span>::map<<\/span>std<\/span>::string, <\/span>long<\/span>> phoneDir;<\/span><\/span>\n  <\/span><\/span>\n  \/\/ Populate with some names\/telephone numbers<\/span><\/span>\n  <\/span>phoneDir<\/span>[<\/span>"Lincoln"<\/span>] = <\/span>5551212<\/span>;<\/span><\/span>\n  <\/span>phoneDir<\/span>[<\/span>"Jefferson"<\/span>] = <\/span>5556000<\/span>;<\/span><\/span>\n  <\/span>phoneDir<\/span>[<\/span>"Washington"<\/span>] = <\/span>5557890<\/span>;<\/span><\/span>\n  <\/span><\/span>\n  <\/span>std<\/span>::string name;<\/span><\/span>\n  <\/span><\/span>\n  <\/span>while<\/span> (<\/span>true<\/span>)<\/span>  \/\/ Look up number by name<\/span><\/span>\n  {<\/span><\/span>\n    <\/span>std<\/span>::cout << <\/span>"Enter a name: "<\/span>;<\/span><\/span>\n    <\/span>if<\/span> ( !(<\/span>std<\/span>::cin >> name) )<\/span><\/span>\n      <\/span>break<\/span>;<\/span> \/\/ End of input<\/span><\/span>\n    <\/span><\/span>\n    <\/span>if<\/span> (<\/span>phoneDir<\/span>.<\/span>find<\/span>(name) != <\/span>phoneDir<\/span>.<\/span>end<\/span>())<\/span><\/span>\n    {<\/span><\/span>\n      <\/span>std<\/span>::cout << <\/span>"Telephone number: "<\/span><\/span>\n                << <\/span>phoneDir<\/span>[name] << <\/span>std<\/span>::endl;<\/span><\/span>\n    }<\/span><\/span>\n    <\/span>else<\/span><\/span>\n    {<\/span><\/span>\n      <\/span>std<\/span>::cout << <\/span>"No entry found for: "<\/span><\/span>\n                << name << <\/span>std<\/span>::endl;<\/span><\/span>\n    }<\/span><\/span>\n  }<\/span><\/span>\n  <\/span><\/span>\n  <\/span>return<\/span> <\/span>0<\/span>;<\/span><\/span>\n}<\/span><\/span><\/code><\/pre><\/div>\n<\/div>\n\n\n\n
    \n
    It outputs:<\/p>\n\n\n\n
    Enter a name: Gandhi<\/em><\/kbd>\nNo entry found for: Gandhi\nEnter a name: Lincoln<\/em><\/kbd>\nTelephone number: 5551212\nEnter a name: Obama<\/em><\/kbd>\nNo entry found for: Obama\nEnter a name: Jefferson<\/em><\/kbd>\nTelephone number: 5556000\nEnter a name: \u001a{Ctrl\/D}<\/em><\/kbd>\nProgram ended with exit code: 0<\/strong><\/code><\/pre>\n<\/div>\n<\/div>\n\n\n\n
    <\/span>The multimap Sorted Associative Container<\/span><\/h3>\n\n\n\n
    Here’s an example of the use of a multimap<\/strong>:<\/p>\n\n\n\n
    \n
    \n
    <\/path><\/path><\/svg><\/span>
    \/\/<\/span><\/span>\n\/\/  main.cpp<\/span><\/span>\n\/\/  STL Sorted Associative Containers<\/span><\/span>\n\/\/<\/span><\/span>\n\/\/  Created by Bryan Higgs on 10\/23\/24.<\/span><\/span>\n\/\/<\/span><\/span>\n<\/span>\n#include<\/span> <\/span><iostream><\/span><\/span>\n#include<\/span> <\/span><map><\/span>  <\/span>\/\/ for multimap class<\/span><\/span>\n#include<\/span> <\/span><string><\/span>  <\/span>\/\/ for string class<\/span><\/span>\n<\/span>\nint<\/span> <\/span>main<\/span>(<\/span>int<\/span> <\/span>argc<\/span>, <\/span>const<\/span> <\/span>char<\/span> <\/span>*<\/span> <\/span>argv<\/span>[])<\/span><\/span>\n{<\/span><\/span>\n  <\/span>std<\/span>::multimap<<\/span>std<\/span>::string, <\/span>long<\/span>> phoneDir;<\/span><\/span>\n  \/\/ Populate with some names\/telephone numbers<\/span><\/span>\n  \/\/ (Note that multimap does not support operator[].)<\/span><\/span>\n  <\/span>phoneDir<\/span>.<\/span>insert<\/span>( <\/span>std<\/span>::<\/span>pair<\/span><<\/span>std<\/span>::<\/span>string<\/span>, <\/span>long<\/span>>(<\/span>"Lincoln"<\/span>, <\/span>5551212<\/span>) );<\/span><\/span>\n  <\/span>phoneDir<\/span>.<\/span>insert<\/span>( <\/span>std<\/span>::<\/span>pair<\/span><<\/span>std<\/span>::<\/span>string<\/span>, <\/span>long<\/span>>(<\/span>"Jefferson"<\/span>, <\/span>5556000<\/span>) );<\/span><\/span>\n  <\/span>phoneDir<\/span>.<\/span>insert<\/span>( <\/span>std<\/span>::<\/span>pair<\/span><<\/span>std<\/span>::<\/span>string<\/span>, <\/span>long<\/span>>(<\/span>"Washington"<\/span>, <\/span>5557890<\/span>) );<\/span><\/span>\n  <\/span>phoneDir<\/span>.<\/span>insert<\/span>( <\/span>std<\/span>::<\/span>pair<\/span><<\/span>std<\/span>::<\/span>string<\/span>, <\/span>long<\/span>>(<\/span>"Adams"<\/span>, <\/span>5551790<\/span>) );<\/span><\/span>\n  <\/span>phoneDir<\/span>.<\/span>insert<\/span>( <\/span>std<\/span>::<\/span>pair<\/span><<\/span>std<\/span>::<\/span>string<\/span>, <\/span>long<\/span>>(<\/span>"Adams"<\/span>, <\/span>5551810<\/span>) );<\/span><\/span>\n  <\/span>phoneDir<\/span>.<\/span>insert<\/span>( <\/span>std<\/span>::<\/span>pair<\/span><<\/span>std<\/span>::<\/span>string<\/span>, <\/span>long<\/span>>(<\/span>"Bush"<\/span>, <\/span>5551990<\/span>) );<\/span><\/span>\n  <\/span>phoneDir<\/span>.<\/span>insert<\/span>( <\/span>std<\/span>::<\/span>pair<\/span><<\/span>std<\/span>::<\/span>string<\/span>, <\/span>long<\/span>>(<\/span>"Bush"<\/span>, <\/span>5552001<\/span>) );<\/span><\/span>\n  <\/span><\/span>\n  <\/span>std<\/span>::string name;<\/span><\/span>\n  <\/span><\/span>\n  <\/span>while<\/span> (<\/span>true<\/span>)<\/span>  \/\/ Look up number by name<\/span><\/span>\n  {<\/span><\/span>\n    <\/span>std<\/span>::cout << <\/span>"Enter a name: "<\/span>;<\/span><\/span>\n    <\/span>if<\/span> ( !(<\/span>std<\/span>::cin >> name) )<\/span><\/span>\n      <\/span>break<\/span>;<\/span>  \/\/ End of input<\/span><\/span>\n    <\/span><\/span>\n    <\/span>std<\/span>::<\/span>multimap<\/span><<\/span>std<\/span>::<\/span>string<\/span>, <\/span>long<\/span>>::iterator match<\/span><\/span>\n              = <\/span>phoneDir<\/span>.<\/span>lower_bound<\/span>(name);<\/span><\/span>\n    <\/span><\/span>\n    <\/span>if<\/span> (match != <\/span>phoneDir<\/span>.<\/span>end<\/span>())<\/span><\/span>\n    {<\/span><\/span>\n      <\/span>std<\/span>::cout << <\/span>"Telephone number(s):"<\/span> << <\/span>std<\/span>::endl;<\/span><\/span>\n      <\/span>std<\/span>::<\/span>multimap<\/span><<\/span>std<\/span>::<\/span>string<\/span>, <\/span>long<\/span>>::iterator matchEnd<\/span><\/span>\n              = <\/span>phoneDir<\/span>.<\/span>upper_bound<\/span>(name);<\/span><\/span>\n      <\/span><\/span>\n      <\/span>for<\/span> (; match != matchEnd; match++)<\/span><\/span>\n      {<\/span><\/span>\n        <\/span>std<\/span>::cout << <\/span>match<\/span>-><\/span>first<\/span><\/span>\n                  << <\/span>": "<\/span> << <\/span>match<\/span>-><\/span>second<\/span> << <\/span>std<\/span>::endl;<\/span><\/span>\n      }<\/span><\/span>\n    }<\/span><\/span>\n    <\/span>else<\/span><\/span>\n      <\/span>std<\/span>::cout << <\/span>"No entry found for: "<\/span> << name << <\/span>std<\/span>::endl;<\/span><\/span>\n  }<\/span><\/span>\n  <\/span><\/span>\n  <\/span><\/span>\n  <\/span>return<\/span> <\/span>0<\/span>;<\/span><\/span>\n}<\/span><\/span><\/code><\/pre><\/div>\n<\/div>\n\n\n\n
    \n
    It outputs:<\/p>\n\n\n\n
    Enter a name: Washington<\/em><\/kbd>\nTelephone number(s):\nWashington: 5557890\nEnter a name: Bush<\/em><\/kbd>\nTelephone number(s):\nBush: 5551990\nBush: 5552001\nEnter a name: Obama<\/kbd><\/em>\nTelephone number(s):\nEnter a name: \u0004{Ctrl\/D}<\/em><\/kbd>\nProgram ended with exit code: 0<\/strong><\/code><\/pre>\n<\/div>\n<\/div>\n\n\n\n
    \n
    The pair Class Template<\/strong><\/p>\n\n\n\n
    Note the use of the pair<\/strong> class template.<\/p>\n\n\n\n
    pair<\/strong> 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<\/strong> container is a simple container defined in <utility><\/strong> header consisting of two data elements or objects. <\/p>\n\n\n\n