C++ STL MAP and multiMAP:

Free Information Technology Software and Development Magazine Subscriptions and Document Downloads

Sparse array example: (why hold space for thousands of elements when all we have is five)

Compile: g++ testMap.cpp
Run: ./a.out

Employees[3374]=Charlie M.

Map size: 5

Natural Order:
1923: David D.
3374: Charlie M.
5234: Mike C.
5328: Peter Q.
7582: John A.

Reverse Order:
7582: John A.
5328: Peter Q.
5234: Mike C.
3374: Charlie M.
1923: David D.

Example using a "string" as an array index:

Compile: g++ testMap.cpp
Run: ./a.out

Map size: 5
Charlie M.: 3374
David D.: 1923
John A.: 7582
Mike C.: 5234
Peter Q.: 5328

Note: The fully defined STL map defines a comparison operator in the map declaration so that the indexes can be ordered. This is used to provide a default comparison operator for the data type. In the above example, the key type is an integer and the C++ "equals" (=) and "less than" operator (<) can operate on an integer so the example works. The use of the STL algorithm std::less<> can be specified explicitly as in the following declaration:

std::map<int, string, std::less< int > >

If defining your own class as the index (first value), C++ will not know how to perform the comparison, thus you will have to provide an operator to perform this function.

The first element in a map can be a class or even another STL container such as a pair. If using a class, the class must provide an overloaded "equals" (=) and "less than" operator (<).

Thus using "char" instead of "string" requires the use of a comparison function:

Compile: g++ testMap.cpp
Run: ./a.out

Map size: 5
Charlie M.: 3374
David D.: 1923
John A.: 7582
Mike C.: 5234
Peter Q.: 5328

SGI Map Documentation:

• map

---

Using STL MAP to store class objects:

This example uses a string as the MAP index and an object as the value pair. In order for a class to be stored in an STL container, it must have a default constructor, the class must be assignable, less than comparable and equality comparable. Thus the overloaded = and < operators are provided to satisfy MAP container use.

Compile: g++ testMap.cpp
Run: ./a.out
Output:

A: 5 2 3.2355

B: 5 2 4.2355

C: 7 2 4.2355

D: 3 7 7.2355

Note: The Map elements were inserted out of order but put in order in the internal Map structure and thus printed out in order. This is why the overloaded "<" operator was required. An alternative friend class with an overloaded "()" operator is shown in the next example.

[Potential Pitfall]: The following error occurs when the < operator is omitted from the class AAA.

/tmp/cca5a9G9.o: In function `main':
testMap.cpp:(.text+0x3c6): undefined reference to `operator<<(std::basic_ostream<char, std::char_traits<char> >&, AAA const&)'
collect2: ld returned 1 exit status

[Potential Pitfall]: The following error occurs when the = operator is omitted from the class AAA.

/tmp/cciGBZgS.o: In function `main':
testMap.cpp:(.text+0x263): undefined reference to `AAA::operator=(AAA const&)'
testMap.cpp:(.text+0x2c8): undefined reference to `AAA::operator=(AAA const&)'
testMap.cpp:(.text+0x32e): undefined reference to `AAA::operator=(AAA const&)'
testMap.cpp:(.text+0x3a2): undefined reference to `AAA::operator=(AAA const&)'
collect2: ld returned 1 exit status

---

Using class objects as a Map key:

Compile: g++ -o examplePersonKey examplePersonKey.cpp

Run: ./examplePersonKey

Flintstone, Fred: 1
Flintstone, Wilma: 1
Rubble, Barney: 1
Rubble, Betty: 1

The people are written out in sorted order as defined by the class PersonLessThan operator "()". The underlying Map structure requires a sort method so that it can insert the object into the underlying structure. You have two choices:

• Map definition: map<key, value> M;
  Sort defined as a key class overloaded operator "<"
  Shown in previous example.
• Map definition: map<key, value, CompareClass> M;
  Sort defined as a key class friend class with an overloaded "()" operator.
  Shown in this example.

Constructor/Declaration:

Method/operator	Description
map<K,T> m;	Map declaration of key of type "K" and value of type "T". Allocate an empty map: map<int,int> m = new map<int,int>();
map<K,T,compare> m;	Map declaration of key of type "K" and value of type "T". A class (or struct) with an overloaded "()" operator function to compare keys so that they can be ordered in the underlying tree storage structure. Allocate an empty map: map<int,float,CFnCompare> m = new map<int,float,CFnCompare>(); Where CFnCompare is a class which defines the overloaded operator "()" which can compare the key type (in this case int)

C++ 11 and C++14 have introduced constructors which allow one to provide the memory allocators.

Size methods/operators:

Method/operator	Description
empty()	Returns bool (true/false). True if empty. Declaration: bool empty() const
size()	Number of elements of the map. Declaration: size_type size() const
max_size()	Number of elements of the map. Declaration: size_type max_size() const

Note: size_type is an unsigned integer.

Other methods/operators:

Method/operator	Description
erase(&key) erase(iterator) erase( iterator first, iterator last )	Erase element of the Map identified by key, at element pos or elements in a range Declaration (all C++): size_type erase( const key_type& key ) Declaration (until c++11): void erase(iterator pos) void erase(iterator first, iterator last ) Declaration (after C++11): iterator erase(iterator pos) iterator erase(iterator first, iterator last )
clear()	Remove all elements of the entire Map Declaration: void clear()
=	Assign/copy entire contents of one Map to another Declaration: map& operator=( const map& other ) C++11 introduces additional prototypes which use allocators
== != < <= > >=	C++ operators available to compare Map elements
[key]	Access the contents of one Map element indicated by its key Declaration: T& operator[]( const Key& key )
at(key)	Access the contents of one Map element indicated by its key Declaration: const T& at( const Key& key ) const; Introduced in C++11
insert(std::pair)	Insert one Map element with the specified key/value pair. Declaration: std::pair<iterator,bool> insert( const std::pair<key,value> );
swap(&other)	Swap one Map with another. This Map class member function should not be confused with std::swap(std::map) Declaration: void swap( map& other )
find(&key)	Finds the Map iterator for the specified key. Declaration: iterator find( const Key& key ) This function bridges the key/index vs iterator methodologies.

Iterator methods/operators:

Method/operator	Description
begin()	Return iterator to first element of the map. Declaration: const_iterator begin() const
end()	Return iterator to element after the last element of the map. No element exists in this location and attempting to access is undefined behavior Declaration: const_iterator end() const
rbegin()	Return iterator to first element of the map (reverse order). This is equivalent to the last element of the non-reversed container. Declaration: const_reverse_iterator rbegin() const
rend()	Return iterator to end of the map (not last element but past last element) (reverse order). This is equivalent to the element preceding the first element of the non-reversed container. Note that this is a placeholder and that no element exists in this location and attempting to access is undefined behavior Declaration: const_reverse_iterator rend() const

Note that for empty Maps, begin and end point to the same position.

The STL multipmap allows duplicate keys.

Compile: g++ testMultimap.cpp
Run: ./a.out

Number of elements with key a: 2
Number of elements with key b: 3
Number of elements with key c: 1
Elements in m:
  [a, 1]
  [a, 5]
  [b, 3]
  [b, 4]
  [b, 6]
  [c, 2]

Range of "b" elements:
  [b, 3]
  [b, 4]
  [b, 6]

SGI STL Documentation:

• pair
• map
• multimap

	The C++ Standard Library: A Tutorial Reference Nicolai M. Josuttis ISBN #0201379260, Addison Wesley Longman This book is the only book I have seen which covers string classes as implemented by current Linux distributions. It also offers a fairly complete coverage of the C++ Standard Template Library (STL). Good reference book.
	STL for C++ programmers Leen Ammeraal ISBN #0 471 97181 2, John Wiley & Sons Ltd. Short book which teaches C++ Standard Template Library (STL) by example. Not as great as a reference but is the best at introducing all the concepts necessary to grasp STL completely and good if you want to learn STL quickly. This book is easy to read and follow.
	Data Structures with C++ Using STL William Ford, Willaim Topp ISBN #0130858501, Prentice Hall
	STL Tutorial and Reference Guide: C++ Programming with the Standard Template Library David R. Musser, Gillmer J. Derge, Atul Saini ISBN #0201379236, Addison-Wesley Publications
	The C++ Templates: The complete guide. David Vandevoorde, Nicolai Josuttis ISBN #0201734842, Addison Wesley Pub Co. Covers complex use of C++ Templates.
	C++ How to Program by Harvey M. Deitel, Paul J. Deitel ISBN #0131857576, Prentice Hall Fifth edition. The first edition of this book (and Professor Sheely at UTA) taught me to program C++. It is complete and covers all the nuances of the C++ language. It also has good code examples. Good for both learning and reference.