8: A C++ Standard-'map'-Compatible Elements-Order-Preserved Map

<The previous article in this series | The table of contents of this series | The next article in this series>

There is no standard map that preserves the elements order in which the elements are put into it. Here is one that is compatible with '::std::map'.

---

Topics

About: C++

---

The table of contents of this article

• Starting Context
• Target Context
• Orientation
• Main Body
• 1: What Is My Standard-Map-Compatible Elements-Order-Preserved Map Like?
• 2: The Rough Sketch of My Standard-Map-Compatible Elements-Order-Preserved Map
• 3: The Whole Code
• 4: A Test Code
• 5: The Source Files Are Here
• 6: The Conclusion and Beyond

---

Starting Context

• The reader has a basic knowledge on C++, even if he or she doesn't accurately understand its some widely-misrepresented elements.
• The reader has a knowledge on how to create a standard-container-compatible custom container.

---

Target Context

• The reader will have a standard-'map'-compatible map that preserves the elements order in which the elements are put into it, and will understand its mechanism.

---

Orientation

Hypothesizer 7
I want a map in which the order of the elements is preserved, which means that any element is inserted into the map at the specified position and is retrieved as such.

The standard 'map' is not such a map.

I do not want my map to be one that is unrelated with the standard 'map', but a map that can be used in lieu of the standard 'map' in all the possible and allowed cases (what I mean by "in all the possible and allowed cases" is explained in the previous article).

My initial, natural (I think that this is natural according to the object-oriented programming paradigm) plan was to publicly extend the standard 'map', but it has turned out that the standard 'map' is not supposed to be extended, and I have understood how any standard-container-compatible custom container is supposed to be created.

Now, the concept is clear, but to really implement such a custom map is rather tiresome. However, I have created it anyway, as is seen in 'Main Body'.

---

Main Body

---

1: What Is My Standard-Map-Compatible Elements-Order-Preserved Map Like?

Hypothesizer 7
What I mean by "elements-order-preserved map" is a map in which any element is inserted into the map at the specified position and is retrieved as such.

When an element is added into an instance of my elements-order-preserved map without the position being explicitly specified, the element is inserted into the map instance as the last element; when an element is inserted into the map instance with the position being explicitly specified as an iterator, the element is inserted in front of the position.

When the elements of the map instance are iterated through, the elements are retrieved in the order determined when they were inserted into the map instance.

And my map is supposed to be able to be used in lieu of the standard 'map' in all the possible and allowed cases (what I mean by "in all the possible and allowed cases" is explained in the previous article).

---

2: The Rough Sketch of My Standard-Map-Compatible Elements-Order-Preserved Map

Hypothesizer 7
As my map is supposed to be able to be used in lieu of the standard 'map' in all the possible and allowed cases, it has to implement all the public elements (not only members but also types) each of which has the same signature with the corresponding standard 'map' public element, as has been discussed in the previous article.

I have learned what those public elements are like from this page and its sub pages.

My first plan was to make my map have a standard 'map' instance whose key type is the key type of my map and whose value type is a class whose members are the value of the element of my map, the previous key, and the next key. This code will clarify the concept.

@C++ Source Code

#include <map>
#include <mutex>
#include <optional>

			template <typename T, typename U, typename W = less <T>> class NavigableLinkedMap {
				public:
					typedef T key_type;
					typedef U mapped_type;
					typedef W key_compare;
				private:
					class ValueAndLinks {
						private:
						    mapped_type i_value;
							optional <key_type> i_previousKey;
							optional <key_type> i_nextKey;
						public:
							ValueAndLinks ();
							ValueAndLinks (mapped_type a_value, optional <key_type> a_previousKey, optional <key_type> a_nextKey);
							mapped_type getValue ();
							void setValue (mapped_type a_value);
							optional <key_type> getPreviousKey ();
							void setPreviousKey (optional <key_type> a_previousKey);
							optional <key_type> getNextKey ();
							void setNextKey (optional <key_type> a_nextKey);
					};
				private:
					map <key_type, ValueAndLinks, key_compare> * i_keyToValueAndLinksMap;
					optional <key_type> * i_firstKey;
					optional <key_type> * i_lastKey;
					mutex i_mutex;
			};

In fact, I have created a similar map (a navigable and elements-insertable linked hash map) in Java, in that way.

However, that has turned out to have a problem: for example, although the return type of the '->' operator of the non-constant iterator class of my map has to be 'pair <key_type const, mapped_type> *', that is not easy because '*i_keyToValueAndLinksMap' does not have any datum of the type, 'pair <key_type const, mapped_type>', but data of the type, 'pair <key_type const, ValueAndLinks>' (the operator's newly creating such a datum (which would have to be a heap datum, which would necessitate a contrivance to eliminate the heap datum at an appropriate time) is meaningless because the point of the operator's returning the address is that any modification to the datum is reflected into '*i_keyToValueAndLinksMap').

So, I have made my map have two standard 'map' instances, one of which is a standard 'map' instance whose key type is the key type of my map and whose value type is the value type of my map, and the other is a standard 'map' instance whose key type is the key type of my map and whose value type is a class whose members are the previous key and the next key. This code will clarify the concept.

@C++ Source Code

#include <map>
#include <mutex>
#include <optional>

			template <typename T, typename U, typename W = less <T>> class NavigableLinkedMap {
				public:
					typedef T key_type;
					typedef U mapped_type;
					typedef W key_compare;
				private:
					class Links {
						private:
							optional <key_type> i_previousKey;
							optional <key_type> i_nextKey;
						public:
							Links ();
							Links (optional <key_type> a_previousKey, optional <key_type> a_nextKey);
							optional <key_type> getPreviousKey ();
							void setPreviousKey (optional <key_type> a_previousKey);
							optional <key_type> getNextKey ();
							void setNextKey (optional <key_type> a_nextKey);
					};
				private:
					map <key_type, mapped_type, key_compare> * i_keyToValueMap;
					map <key_type, Links, key_compare> * i_keyToLinksMap;
					optional <key_type> * i_firstKey;
					optional <key_type> * i_lastKey;
					mutex i_mutex;
			};

The reason why 'i_keyToValueMap', 'i_keyToLinksMap', 'i_firstKey', and 'i_lastKey' are pointers is that that makes the implementation of the 'swap' method of my map easy: the 'swap' method can just swap the addresses between two map instances.

Some member variables are 'optional' because they are optional: for example, the first element does not have any previous key.

My map has the mutex in order to prevent some instance-modifying methods' being called on any map instance by multiple threads at the same time.

---

3: The Whole Code

Hypothesizer 7
This is the whole code of my standard-'map'-compatible elements-order-preserved map.

theBiasPlanet/coreUtilities/visualCplusplusSpecificHeaders/VisualCplusplusSpecificDefinitions.hpp

@C++ Source Code

#ifndef __theBiasPlanet_coreUtilities_visualCplusplusSpecificHeaders_VisualCplusplusSpecificDefinitions_hpp__
#define __theBiasPlanet_coreUtilities_visualCplusplusSpecificHeaders_VisualCplusplusSpecificDefinitions_hpp__

#ifdef GCC
#define __symbolExportingDeclarationForVisualCplusplus__
#define __symbolExportingOrImportingDeclarationForVisualCplusplus__
#else
#ifdef __dllExport__
#define __symbolExportingDeclarationForVisualCplusplus__ __declspec (dllexport)
#define __symbolExportingOrImportingDeclarationForVisualCplusplus__ __declspec (dllexport)
#else
#define __symbolExportingDeclarationForVisualCplusplus__
#define __symbolExportingOrImportingDeclarationForVisualCplusplus__ __declspec (dllimport)
#endif
#endif

#endif

theBiasPlanet/coreUtilities/collections/NavigableLinkedMap.hpp

@C++ Source Code

#ifndef __theBiasPlanet_coreUtilities_collections_NavigableLinkedMap_hpp__
#define __theBiasPlanet_coreUtilities_collections_NavigableLinkedMap_hpp__

#include <initializer_list>
#include <map>
#include <mutex>
#include <optional>
#include "theBiasPlanet/coreUtilities/visualCplusplusSpecificHeaders/VisualCplusplusSpecificDefinitions.hpp"

using namespace ::std;

namespace theBiasPlanet {
	namespace coreUtilities {
		namespace collections {
			template <typename T, typename U, typename W = less <T>> class __symbolExportingDeclarationForVisualCplusplus__ NavigableLinkedMap {
				public:
					typedef T key_type;
					typedef U mapped_type;
					typedef W key_compare;
				private:
					class Links {
						private:
							optional <key_type> i_previousKey;
							optional <key_type> i_nextKey;
						public:
							Links ();
							Links (optional <key_type> a_previousKey, optional <key_type> a_nextKey);
							optional <key_type> getPreviousKey ();
							void setPreviousKey (optional <key_type> a_previousKey);
							optional <key_type> getNextKey ();
							void setNextKey (optional <key_type> a_nextKey);
					};
				public:
					typedef pair <key_type const, mapped_type> value_type;
					class ValueComparer {
						private:
							key_compare i_keyComparer;
						public:
							ValueComparer (key_compare a_keyComparer);
							bool operator () (value_type const & a_keyValuePair1, value_type const & a_keyValuePair2) const;
					};
					typedef ValueComparer value_compare;
					typedef allocator <value_type> allocator_type;
					typedef value_type & reference;
					typedef value_type const & const_reference;
					typedef value_type * pointer;
					typedef value_type const * const_pointer;
					class BaseIterator {
						protected:
							map <key_type, mapped_type, key_compare> * i_keyToValueMap;
							map <key_type, Links, key_compare> * i_keyToLinksMap;
							optional <key_type> * i_firstKey;
							optional <key_type> * i_lastKey;
							optional <key_type> i_currentKey;
							virtual void goToNextElement ();
							virtual void goToPreviousElement ();
						public:
							typedef ptrdiff_t difference_type;
							typedef bidirectional_iterator_tag iterator_category;
							BaseIterator (NavigableLinkedMap <key_type, mapped_type, key_compare> const & a_navigableLinkedMap, optional <key_type> a_currentKey);
							BaseIterator (BaseIterator const & a_originalIterator);
							virtual bool operator == (BaseIterator const & a_iteratorToBeCompared) const;
							virtual bool operator != (BaseIterator const & a_iteratorToBeCompared) const;
					};
					class NonConstantIterator : public BaseIterator {
						public:
							typedef pair <key_type const, mapped_type> value_type;
							typedef value_type * pointer;
							typedef value_type & reference;
							NonConstantIterator (NavigableLinkedMap <key_type, mapped_type, key_compare> const & a_navigableLinkedMap, optional <key_type> a_currentKey);
							NonConstantIterator (BaseIterator const & a_originalIterator);
							virtual NonConstantIterator & operator ++ ();
							virtual NonConstantIterator operator ++ (int);
							virtual NonConstantIterator & operator -- ();
							virtual NonConstantIterator operator -- (int);
							virtual value_type & operator * ();
							virtual value_type * operator -> ();
					};
					class ConstantIterator : public BaseIterator {
						public:
							typedef pair <key_type const, mapped_type> const value_type;
							typedef pair <key_type const, mapped_type> NonConstantvalue_type;
							typedef value_type * pointer;
							typedef value_type & reference;
							ConstantIterator (NavigableLinkedMap <key_type, mapped_type, key_compare> const & a_navigableLinkedMap, optional <key_type> a_currentKey);
							ConstantIterator (BaseIterator const & a_originalIterator);
							virtual ConstantIterator & operator ++ ();
							virtual ConstantIterator operator ++ (int);
							virtual ConstantIterator & operator -- ();
							virtual ConstantIterator operator -- (int);
							virtual value_type & operator * ();
							virtual value_type * operator -> ();
					};
					typedef NonConstantIterator iterator;
					typedef ConstantIterator const_iterator;
					typedef ::std::reverse_iterator <iterator> reverse_iterator;
					typedef ::std::reverse_iterator <const_iterator> const_reverse_iterator;
					typedef ptrdiff_t difference_type;
					typedef size_t size_type;
				private:
					map <key_type, mapped_type, key_compare> * i_keyToValueMap;
					map <key_type, Links, key_compare> * i_keyToLinksMap;
					optional <key_type> * i_firstKey;
					optional <key_type> * i_lastKey;
					mutex i_mutex;
					pair <key_type &, mapped_type &> getKeyValuePair (key_type & a_key, mapped_type & a_value);
					virtual void insertNewElementAtEnd (key_type const a_key, optional <mapped_type> a_value);
					virtual void insertNewElementAtMiddle (key_type const a_positionKey, key_type const a_key, optional <mapped_type> a_value);
					virtual void updateElement (key_type const a_key, mapped_type a_value);
				public:
					explicit NavigableLinkedMap (key_compare const & a_keysComparer = key_compare ());
					template <typename V> NavigableLinkedMap (V a_iteratorPointedAtFirstElement, V a_iteratorPointedAtLastElementNotIncluded, key_compare const & a_keysComparer = key_compare ());
					NavigableLinkedMap (initializer_list <value_type> a_initializer, key_compare const & a_keysComparer = key_compare ());
					NavigableLinkedMap (NavigableLinkedMap const & a_navigableLinkedMap);
					virtual ~NavigableLinkedMap ();
					virtual NavigableLinkedMap <T, U, W> & operator = (NavigableLinkedMap <T, U, W> const & a_navigableLinkedMap);
					virtual iterator begin ();
					virtual const_iterator begin () const;
					virtual iterator end ();
					virtual const_iterator end () const;
					virtual reverse_iterator rbegin ();
					virtual const_reverse_iterator rbegin () const;
					virtual reverse_iterator rend ();
					virtual const_reverse_iterator rend () const;
					virtual const_iterator cbegin () const noexcept;
					virtual const_iterator cend () const noexcept;
					virtual const_reverse_iterator crbegin () const noexcept;
					virtual const_reverse_iterator crend () const noexcept;
					virtual bool empty () const;
					virtual size_type size () const;
					virtual size_type max_size () const;
					virtual mapped_type & operator [] (key_type const & a_key);
					virtual mapped_type & at (key_type const & a_key);
					virtual mapped_type const & at (key_type const & a_key) const;
					virtual pair <iterator, bool> insert (value_type const & a_keyValuePair);
					virtual iterator insert (iterator a_position, value_type const & a_keyValuePair);
					// Any template method cannot be virtual only because it is decided so by the specification.
					template <typename V> void insert (V a_iteratorPointedAtFirstElement, V a_iteratorPointedAtLastElementNotIncluded);
					virtual void erase (iterator a_position);
					virtual size_type erase (key_type const & a_key);
     				virtual void erase (iterator a_iteratorPointedAtFirstElement, iterator a_iteratorPointedAtLastElementNotIncluded);
					virtual void swap (NavigableLinkedMap <T, U, W> & a_navigableLinkedMap);
					virtual void clear();
					template <typename ... V> pair <iterator, bool> emplace (V && ... a_arguments);
					template <typename ... V> iterator emplace_hint (const_iterator a_position, V && ... a_arguments);
					virtual key_compare key_comp () const;
					virtual value_compare value_comp () const;
					virtual iterator find (key_type const & a_key);
					virtual const_iterator find (key_type const & a_key) const;
					virtual size_type count (key_type const & a_key) const;
					virtual iterator lower_bound (key_type const & a_key);
					virtual const_iterator lower_bound (key_type const & a_key) const;
					virtual iterator upper_bound (key_type const & a_key);
					virtual const_iterator upper_bound (key_type const & a_key) const;
					virtual pair <const_iterator, const_iterator> equal_range (key_type const & a_key) const;
					virtual pair <iterator, iterator> equal_range (key_type const & a_key);
					virtual allocator_type get_allocator () const;
			};
		}
	}
}

#endif

theBiasPlanet/coreUtilities/collections/NavigableLinkedMap.tpp

@C++ Source Code

#include "theBiasPlanet/coreUtilities/collections/NavigableLinkedMap.hpp"
#include <cstdarg>
#include <stdexcept>
#include <string>
#include "theBiasPlanet/coreUtilities/locksHandling/Locker.hpp"

using namespace ::theBiasPlanet::coreUtilities::locksHandling;

namespace theBiasPlanet {
	namespace coreUtilities {
		namespace collections {
			template <typename T, typename U, typename W> NavigableLinkedMap <T, U, W>::Links::Links () : i_previousKey (nullopt), i_nextKey (nullopt) {
			}
			
			template <typename T, typename U, typename W> NavigableLinkedMap <T, U, W>::Links::Links (optional <key_type> a_previousKey, optional <key_type> a_nextKey) : i_previousKey (a_previousKey), i_nextKey (a_nextKey) {
			}
			
			template <typename T, typename U, typename W> optional <typename NavigableLinkedMap <T, U, W>::key_type> NavigableLinkedMap <T, U, W>::Links::getPreviousKey () {
				return i_previousKey;
			}
			
			template <typename T, typename U, typename W> void NavigableLinkedMap <T, U, W>::Links::setPreviousKey (optional <key_type> a_previousKey) {
				i_previousKey = a_previousKey;
			}
			
			template <typename T, typename U, typename W> optional <typename NavigableLinkedMap <T, U, W>::key_type> NavigableLinkedMap <T, U, W>::Links::getNextKey () {
				return i_nextKey;
			}
			
			template <typename T, typename U, typename W> void NavigableLinkedMap <T, U, W>::Links::setNextKey (optional <key_type> a_nextKey) {
				i_nextKey = a_nextKey;
			}
			
			template <typename T, typename U, typename W> pair <typename NavigableLinkedMap <T, U, W>::key_type &, typename NavigableLinkedMap <T, U, W>::mapped_type &> NavigableLinkedMap <T, U, W>::getKeyValuePair (key_type & a_key, mapped_type & a_value) {
				return pair <key_type &, mapped_type &> (a_key, a_value);
			}
			
			template <typename T, typename U, typename W> NavigableLinkedMap <T, U, W>::ValueComparer::ValueComparer (key_compare a_keyComparer) : i_keyComparer (a_keyComparer) {
			}
			
			template <typename T, typename U, typename W> bool NavigableLinkedMap <T, U, W>::ValueComparer::operator () (value_type const & a_keyValuePair1, value_type const & a_keyValuePair2) const {
				return i_keyComparer (a_keyValuePair1.first, a_keyValuePair2.first);
			}
			
			template <typename T, typename U, typename W> void NavigableLinkedMap <T, U, W>::insertNewElementAtEnd (key_type const a_key, optional <mapped_type> a_value) {
				mapped_type & l_insertedElementValue = (*i_keyToValueMap) [a_key];
				Links & l_insertedElementLinks = (*i_keyToLinksMap) [a_key];
				if (i_lastKey->has_value ()) {
					(*i_keyToLinksMap) [**i_lastKey].setNextKey (a_key);
				}
				l_insertedElementLinks.setPreviousKey (*i_lastKey); 
				*i_lastKey = a_key;
				if (!i_firstKey->has_value ()) {
					*i_firstKey = a_key;
				}
				if (a_value.has_value ()) {
					l_insertedElementValue = *a_value;
				}
			}
			
			template <typename T, typename U, typename W> void NavigableLinkedMap <T, U, W>::insertNewElementAtMiddle (key_type const a_positionKey, key_type const a_key, optional <mapped_type> a_value) {
				Links & l_foundElementLinks = (*i_keyToLinksMap) [a_positionKey];
				mapped_type & l_insertedElementValue = (*i_keyToValueMap) [a_key];
				Links & l_insertedElementLinks = (*i_keyToLinksMap) [a_key];
				optional <key_type> l_previousKey = l_foundElementLinks.getPreviousKey ();
				if (l_previousKey == nullopt) {
					*i_firstKey = a_key;
				}
				else {
					Links & l_previousElementLinks = (*i_keyToLinksMap) [*l_previousKey];
					l_previousElementLinks.setNextKey (a_key);
				}
				l_insertedElementLinks.setPreviousKey (l_foundElementLinks.getPreviousKey ());
				l_insertedElementLinks.setNextKey (a_positionKey); 
				l_insertedElementValue = *a_value; 
				l_foundElementLinks.setPreviousKey (a_key);
			}
			
			template <typename T, typename U, typename W> void NavigableLinkedMap <T, U, W>::updateElement (key_type const a_key, mapped_type a_value) {
				mapped_type & l_updatedElementValue = i_keyToValueMap->at (a_key);
				l_updatedElementValue = a_value;
			}
			
			template <typename T, typename U, typename W> NavigableLinkedMap <T, U, W>::NavigableLinkedMap (key_compare const & a_keysComparer) : i_keyToValueMap (new map <key_type, mapped_type, key_compare> (a_keysComparer)), i_keyToLinksMap (new map <key_type, Links, key_compare> ( (key_compare) a_keysComparer)), i_firstKey (new optional <key_type> ()), i_lastKey (new optional <key_type> ()) {
			}
			
			template <typename T, typename U, typename W> template <typename V> NavigableLinkedMap <T, U, W>::NavigableLinkedMap (V a_iteratorPointedAtFirstElement, V a_iteratorPointedAtLastElementNotIncluded, key_compare const & a_keysComparer) : i_keyToValueMap (new map <key_type, mapped_type, key_compare> (a_keysComparer)), i_keyToLinksMap (new map <key_type, Links, key_compare> ( (key_compare) a_keysComparer)), i_firstKey (new optional <key_type> ()), i_lastKey (new optional <key_type> ()) {
				this->insert (a_iteratorPointedAtFirstElement, a_iteratorPointedAtLastElementNotIncluded);
			}
			
			template <typename T, typename U, typename W> NavigableLinkedMap <T, U, W>::NavigableLinkedMap (initializer_list <value_type> a_initializer, key_compare const & a_keysComparer) : i_keyToValueMap (new map <key_type, mapped_type, key_compare> (a_keysComparer)), i_keyToLinksMap (new map <key_type, Links, key_compare> ( (key_compare) a_keysComparer)), i_firstKey (new optional <key_type> ()), i_lastKey (new optional <key_type> ()) {
				for (value_type const & l_keyValuePair: a_initializer) {
					insert (l_keyValuePair);
				}
			}
			
			template <typename T, typename U, typename W> NavigableLinkedMap <T, U, W>::NavigableLinkedMap (NavigableLinkedMap <key_type, mapped_type, key_compare> const & a_navigableLinkedMap) : i_keyToValueMap (new map <key_type, mapped_type, key_compare> (*(a_navigableLinkedMap.i_keyToValueMap))), i_keyToLinksMap (new map <key_type, Links, key_compare> (*(a_navigableLinkedMap.i_keyToLinksMap))), i_firstKey (new optional <key_type> (*(a_navigableLinkedMap.i_firstKey))), i_lastKey (new optional <key_type> (*(a_navigableLinkedMap.i_lastKey))) {
			}
			
			template <typename T, typename U, typename W> NavigableLinkedMap <T, U, W>::~NavigableLinkedMap () {
				delete i_keyToValueMap;
				i_keyToValueMap = nullptr;
				delete i_keyToLinksMap;
				i_keyToLinksMap = nullptr;
				delete i_firstKey;
				i_firstKey = nullptr;
				delete i_lastKey;
				i_lastKey = nullptr;
			}
			
			template <typename T, typename U, typename W> NavigableLinkedMap <T, U, W> & NavigableLinkedMap <T, U, W>::operator = (NavigableLinkedMap <key_type, mapped_type, key_compare> const & a_navigableLinkedMap) {
				*i_keyToValueMap = *(a_navigableLinkedMap.i_keyToValueMap);
				*i_keyToLinksMap = *(a_navigableLinkedMap.i_keyToLinksMap);
				*i_firstKey = *(a_navigableLinkedMap.i_firstKey);
				*i_lastKey = *(a_navigableLinkedMap.i_lastKey);
				return *this;
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::iterator NavigableLinkedMap <T, U, W>::begin () {
				return iterator (*this, *i_firstKey);
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::const_iterator NavigableLinkedMap <T, U, W>::begin () const {
				return const_iterator (*this, *i_firstKey);
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::iterator NavigableLinkedMap <T, U, W>::end () {
				return iterator (*this, nullopt);
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::const_iterator NavigableLinkedMap <T, U, W>::end () const {
				return const_iterator (*this, nullopt);
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::reverse_iterator NavigableLinkedMap <T, U, W>::rbegin () {
				return reverse_iterator (end ());
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::const_reverse_iterator NavigableLinkedMap <T, U, W>::rbegin () const {
				return const_reverse_iterator (end ());
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::reverse_iterator NavigableLinkedMap <T, U, W>::rend () {
				return reverse_iterator (begin ());
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::const_reverse_iterator NavigableLinkedMap <T, U, W>::rend () const {
				return const_reverse_iterator (begin ());
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::const_iterator NavigableLinkedMap <T, U, W>::cbegin () const noexcept {
				return const_iterator (*this, *i_firstKey);
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::const_iterator NavigableLinkedMap <T, U, W>::cend () const noexcept {
				return const_iterator (*this, nullopt);
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::const_reverse_iterator NavigableLinkedMap <T, U, W>::crbegin () const noexcept {
				return const_reverse_iterator (cend ());
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::const_reverse_iterator NavigableLinkedMap <T, U, W>::crend () const noexcept {
				return const_reverse_iterator (cbegin ());
			}
			
			template <typename T, typename U, typename W> bool NavigableLinkedMap <T, U, W>::empty () const {
				i_keyToValueMap->empty ();
				return i_keyToLinksMap->empty ();
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::size_type NavigableLinkedMap <T, U, W>::size () const {
				return i_keyToValueMap->size ();
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::size_type NavigableLinkedMap <T, U, W>::max_size () const {
				return i_keyToValueMap->max_size ();
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::mapped_type & NavigableLinkedMap <T, U, W>::operator []  (key_type const & a_key) {
				Locker l_locker (&i_mutex);
				if (i_keyToValueMap->count (a_key) == 0) {
					insertNewElementAtEnd (a_key, nullopt);
				}
				else {
				}
				return (*i_keyToValueMap) [a_key];
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::mapped_type & NavigableLinkedMap <T, U, W>::at (key_type const & a_key) {
				return i_keyToValueMap->at (a_key);
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::mapped_type const & NavigableLinkedMap <T, U, W>::at (key_type const & a_key) const {
				return i_keyToValueMap->at (a_key);
			}
			
			template <typename T, typename U, typename W> pair <typename NavigableLinkedMap <T, U, W>::iterator, bool> NavigableLinkedMap <T, U, W>::insert (value_type const & a_keyValuePair) {
				Locker l_locker (&i_mutex);
				bool l_isNewlyInserted = false;
				if (i_keyToValueMap->count (a_keyValuePair.first) == 0) {
					l_isNewlyInserted = true;
					insertNewElementAtEnd (a_keyValuePair.first, a_keyValuePair.second);
				}
				else {
					updateElement (a_keyValuePair.first, a_keyValuePair.second);
				}
				return pair (iterator (*this, a_keyValuePair.first), l_isNewlyInserted);
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::iterator NavigableLinkedMap <T, U, W>::insert (iterator a_position, value_type const & a_keyValuePair) {
				Locker l_locker (&i_mutex);
				if (i_keyToValueMap->count (a_keyValuePair.first) == 0) {
					if (i_keyToValueMap->count ((*a_position).first) == 0) {
						insertNewElementAtEnd (a_keyValuePair.first, a_keyValuePair.second);
					}
					else {
						insertNewElementAtMiddle ((*a_position).first, a_keyValuePair.first, a_keyValuePair.second);
					}
				}
				else {
					updateElement (a_keyValuePair.first, a_keyValuePair.second);
				}
				return iterator (*this, a_keyValuePair.first);
			}
			
			template <typename T, typename U, typename W> template <typename V> void NavigableLinkedMap <T, U, W>::insert (V a_iteratorPointedAtFirstElement, V a_iteratorPointedAtLastElementNotIncluded) {
				for (V l_iterator = a_iteratorPointedAtFirstElement; l_iterator != a_iteratorPointedAtLastElementNotIncluded; l_iterator++) {
					insert (*l_iterator);
				}
			}
			
			template <typename T, typename U, typename W> void NavigableLinkedMap <T, U, W>::erase (iterator a_position) {
				erase ((*a_position).first);
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::size_type NavigableLinkedMap <T, U, W>::erase (key_type const & a_key) {
				Locker l_locker (&i_mutex);
				if (i_keyToValueMap->count (a_key) == 0) {
					return 0;
				}
				else {
					Links & l_foundElementLinks = (*i_keyToLinksMap) [a_key];
					optional <key_type> l_previousKey = l_foundElementLinks.getPreviousKey (); 
					optional <key_type> l_nextKey = l_foundElementLinks.getNextKey ();
					if (l_previousKey.has_value ()) {
						Links & l_previousElementLinks = (*i_keyToLinksMap) [*l_previousKey];
						if (l_nextKey.has_value ()) {
							Links & l_nextElementLinks = (*i_keyToLinksMap) [*l_nextKey];
							l_previousElementLinks.setNextKey (l_nextKey);
							l_nextElementLinks.setPreviousKey (l_previousKey);
						}
						else {
							l_previousElementLinks.setNextKey (nullopt);
							*i_lastKey = l_previousKey;
						}
					}
					else {
						if (l_nextKey.has_value ()) {
							Links & l_nextElementLinks = (*i_keyToLinksMap) [*l_nextKey];
							*i_firstKey = l_nextKey;
							l_nextElementLinks.setPreviousKey (nullopt);
						}
						else {
							*i_firstKey = nullopt;
							*i_lastKey = nullopt;
						}
					}
					i_keyToValueMap->erase (a_key);
					i_keyToLinksMap->erase (a_key);
					return 1;
				}
			}
			
     		template <typename T, typename U, typename W> void NavigableLinkedMap <T, U, W>::erase (iterator a_iteratorPointedAtFirstElement, iterator a_iteratorPointedAtLastElementNotIncluded) {
				for (NavigableLinkedMap <key_type, mapped_type, key_compare>::iterator l_iterator = a_iteratorPointedAtFirstElement; l_iterator != a_iteratorPointedAtLastElementNotIncluded; l_iterator++) {
					erase (l_iterator);
				}
			}
			
			template <typename T, typename U, typename W> void NavigableLinkedMap <T, U, W>::swap (NavigableLinkedMap <key_type, mapped_type, key_compare> & a_navigableLinkedMap) {
				map <key_type, mapped_type, key_compare> * l_keyToValueMapSaved = i_keyToValueMap;
				map <key_type, Links, key_compare> * l_keyToLinksMapSaved = i_keyToLinksMap;
				i_keyToValueMap = a_navigableLinkedMap.i_keyToValueMap;
				i_keyToLinksMap = a_navigableLinkedMap.i_keyToLinksMap;
				a_navigableLinkedMap.i_keyToValueMap = l_keyToValueMapSaved;
				a_navigableLinkedMap.i_keyToLinksMap = l_keyToLinksMapSaved;
				optional <key_type> * l_firstKeySaved = i_firstKey;
				i_firstKey = a_navigableLinkedMap.i_firstKey;
				a_navigableLinkedMap.i_firstKey = l_firstKeySaved;
				optional <key_type> * l_lastKeySaved = i_lastKey;
				i_lastKey = a_navigableLinkedMap.i_lastKey;
				a_navigableLinkedMap.i_lastKey = l_lastKeySaved;
			}
			
			template <typename T, typename U, typename W> void NavigableLinkedMap <T, U, W>::clear () {
				i_keyToValueMap->clear ();
				i_keyToLinksMap->clear ();
				*i_firstKey = nullopt;
				*i_lastKey = nullopt;
			}
			
			template <typename T, typename U, typename W> template <typename ... V> pair <typename NavigableLinkedMap <T, U, W>::iterator, bool> NavigableLinkedMap <T, U, W>::emplace (V && ... a_arguments) {
				Locker l_locker (&i_mutex);
				pair <key_type &, mapped_type &> l_keyValuePair = getKeyValuePair (a_arguments...);
				T & l_key = l_keyValuePair.first;
				U & l_value = l_keyValuePair.second;
				bool l_isNewlyInserted = false;
				if (i_keyToValueMap->count (l_key) == 0) {
					l_isNewlyInserted = true;
					if (i_lastKey->has_value ()) {
						(*i_keyToLinksMap) [**i_lastKey].setNextKey (l_key);
					}
					i_keyToValueMap->emplace (l_key, l_value);
					i_keyToLinksMap->emplace (l_key, Links (*i_lastKey, nullopt));
					*i_lastKey = l_key;
					if (!i_firstKey->has_value ()) {
						*i_firstKey = l_key;
					}
				}
				else {
				}
				return pair (iterator (*this, l_key), l_isNewlyInserted);
			}
			
			template <typename T, typename U, typename W> template <typename ... V> typename NavigableLinkedMap <T, U, W>::iterator NavigableLinkedMap <T, U, W>::emplace_hint (const_iterator a_position, V && ... a_arguments) {
				Locker l_locker (&i_mutex);
				pair <key_type &, mapped_type &> l_keyValuePair = getKeyValuePair (a_arguments...);
				key_type & l_key = l_keyValuePair.first;
				mapped_type & l_value = l_keyValuePair.second;
				bool l_isNewlyInserted = false;
				if (i_keyToValueMap->count (l_key) == 0) {
					l_isNewlyInserted = true;
					if (i_keyToValueMap->count (a_position->first) == 0) {
						return emplace (a_arguments...).first;
					}
					else {
						Links & l_foundElementLinks = (*i_keyToLinksMap) [a_position->first];
						optional <key_type> l_previousKey = l_foundElementLinks.getPreviousKey ();
						i_keyToValueMap->emplace (l_key, l_value);
						i_keyToLinksMap->emplace (l_key, Links (l_previousKey, a_position->first));
						if (!l_previousKey.has_value ()) {
							*i_firstKey = l_key;
						}
						else {
							Links & l_previousElementLinks = (*i_keyToLinksMap) [*l_previousKey];
							l_previousElementLinks.setNextKey (l_key);
						}
						l_foundElementLinks.setPreviousKey (l_key);
					}
				}
				else {
				}
				return iterator (*this, l_key);
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::key_compare NavigableLinkedMap <T, U, W>::key_comp () const {
				return i_keyToValueMap->key_comp ();
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::value_compare NavigableLinkedMap <T, U, W>::value_comp () const {
				return value_compare (key_comp ());
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::iterator NavigableLinkedMap <T, U, W>::find (key_type const & a_key) {
				if (i_keyToValueMap->count (a_key) == 0) {
					return iterator (*this, nullopt);
				}
				else {
					return iterator (*this, a_key);
				}
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::const_iterator NavigableLinkedMap <T, U, W>::find (key_type const & a_key) const {
				if (i_keyToValueMap->count (a_key) == 0) {
					return const_iterator (*this, nullopt);
				}
				else {
					return const_iterator (*this, a_key);
				}
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::size_type NavigableLinkedMap <T, U, W>::count (key_type const & a_key) const {
				return i_keyToValueMap->count (a_key);
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::iterator NavigableLinkedMap <T, U, W>::lower_bound (key_type const & a_key) {
				key_compare l_keyComparer = this->key_comp ();
				for (value_type const & l_keyValuePair: *this) {
					if (!l_keyComparer (l_keyValuePair.first, a_key)) {
						return iterator (*this, l_keyValuePair.first);
					}
				}
				return end ();
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::const_iterator NavigableLinkedMap <T, U, W>::lower_bound (key_type const & a_key) const {
				key_compare l_keyComparer = this->key_comp ();
				for (value_type const & l_keyValuePair: *this) {
					if (!l_keyComparer (l_keyValuePair.first, a_key)) {
						return const_iterator (*this, l_keyValuePair.first);
					}
				}
				return cend ();
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::iterator NavigableLinkedMap <T, U, W>::upper_bound (key_type const & a_key) {
				key_compare l_keyComparer = this->key_comp ();
				for (value_type const & l_keyValuePair: *this) {
					if (l_keyComparer (a_key, l_keyValuePair.first)) {
						return iterator (*this, l_keyValuePair.first);
					}
				}
				return end ();
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::const_iterator NavigableLinkedMap <T, U, W>::upper_bound (key_type const & a_key) const {
				key_compare l_keyComparer = this->key_comp ();
				for (value_type const & l_keyValuePair: *this) {
					if (l_keyComparer (a_key, l_keyValuePair.first)) {
						return const_iterator (*this, l_keyValuePair.first);
					}
				}
				return cend ();
			}
			
			template <typename T, typename U, typename W> pair <typename NavigableLinkedMap <T, U, W>::const_iterator, typename NavigableLinkedMap <T, U, W>::const_iterator> NavigableLinkedMap <T, U, W>::equal_range (key_type const & a_key) const {
				const_iterator l_lowerBoundIterator = lower_bound (a_key);
				if (l_lowerBoundIterator != cend () && l_lowerBoundIterator->first == a_key) {
					iterator l_nextToLowerBoundIterator = l_lowerBoundIterator;
					l_nextToLowerBoundIterator ++;
					return pair <iterator, iterator> (l_lowerBoundIterator, l_nextToLowerBoundIterator);
				}
				else {
					return pair <const_iterator, const_iterator> (l_lowerBoundIterator, l_lowerBoundIterator);
				}
			}
			
			template <typename T, typename U, typename W> pair <typename NavigableLinkedMap <T, U, W>::iterator, typename NavigableLinkedMap <T, U, W>::iterator> NavigableLinkedMap <T, U, W>::equal_range (key_type const & a_key) {
				iterator l_lowerBoundIterator = lower_bound (a_key);
				if (l_lowerBoundIterator != end () && l_lowerBoundIterator->first == a_key) {
					iterator l_nextToLowerBoundIterator = l_lowerBoundIterator;
					l_nextToLowerBoundIterator ++;
					return pair <iterator, iterator> (l_lowerBoundIterator, l_nextToLowerBoundIterator);
				}
				else {
					return pair <iterator, iterator> (l_lowerBoundIterator, l_lowerBoundIterator);
				}
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::allocator_type NavigableLinkedMap <T, U, W>::get_allocator () const {
				return i_keyToValueMap->get_allocator ();
			}
			
			template <typename T, typename U, typename W> void NavigableLinkedMap <T, U, W>::BaseIterator::goToNextElement () {
				if (i_currentKey.has_value ()) {
					try {
						Links & l_currentElementLinks = i_keyToLinksMap->at (*i_currentKey);
						i_currentKey = l_currentElementLinks.getNextKey ();
					}
					catch (out_of_range l_exception) {
						i_currentKey  = nullopt;
					}
				}
				else {
				}
			}
			
			template <typename T, typename U, typename W> void NavigableLinkedMap <T, U, W>::BaseIterator::goToPreviousElement () {
				if (i_currentKey.has_value ()) {
					try {
						Links & l_currentElementLinks = i_keyToLinksMap->at (*i_currentKey);
						// If the current element is the first element, the past-the-end-element becomes the current element.
						i_currentKey = l_currentElementLinks.getPreviousKey ();
					}
					catch (out_of_range l_exception) {
						i_currentKey  = nullopt;
					}
				}
				else {
					i_currentKey  = *i_lastKey;
				}
			}
			
			template <typename T, typename U, typename W> NavigableLinkedMap <T, U, W>::BaseIterator::BaseIterator (NavigableLinkedMap <key_type, mapped_type, key_compare> const & a_navigableLinkedMap, optional <key_type> a_currentKey) : i_keyToValueMap (a_navigableLinkedMap.i_keyToValueMap), i_keyToLinksMap (a_navigableLinkedMap.i_keyToLinksMap), i_firstKey (a_navigableLinkedMap.i_firstKey), i_lastKey (a_navigableLinkedMap.i_lastKey), i_currentKey (a_currentKey) {
			}
			
			template <typename T, typename U, typename W> NavigableLinkedMap <T, U, W>::BaseIterator::BaseIterator (BaseIterator const & a_originalIterator) : i_keyToValueMap (a_originalIterator.i_keyToValueMap), i_keyToLinksMap (a_originalIterator.i_keyToLinksMap), i_firstKey (a_originalIterator.i_firstKey), i_lastKey (a_originalIterator.i_lastKey), i_currentKey (a_originalIterator.i_currentKey) {
			}
			
			template <typename T, typename U, typename W> bool NavigableLinkedMap <T, U, W>::BaseIterator::operator == (BaseIterator const & a_iteratorToBeCompared) const {
				return (i_currentKey == a_iteratorToBeCompared.i_currentKey);
			}
			
			template <typename T, typename U, typename W> bool NavigableLinkedMap <T, U, W>::BaseIterator::operator != (BaseIterator const & a_iteratorToBeCompared) const {
				return (i_currentKey != a_iteratorToBeCompared.i_currentKey);
			}
			
			template <typename T, typename U, typename W> NavigableLinkedMap <T, U, W>::NonConstantIterator::NonConstantIterator (NavigableLinkedMap <key_type, mapped_type, key_compare> const & a_navigableLinkedMap, optional <key_type> a_currentKey) : BaseIterator (a_navigableLinkedMap, a_currentKey) {
			}
			
			template <typename T, typename U, typename W> NavigableLinkedMap <T, U, W>::NonConstantIterator::NonConstantIterator (BaseIterator const & a_originalIterator) : BaseIterator (a_originalIterator) {
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::NonConstantIterator & NavigableLinkedMap <T, U, W>::NonConstantIterator::operator ++ () {
				this->goToNextElement ();
				return *this;
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::NonConstantIterator NavigableLinkedMap <T, U, W>::NonConstantIterator::operator ++ (int) {
				NonConstantIterator l_copiedIterator (*this);
				this->goToNextElement ();
				return l_copiedIterator;
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::NonConstantIterator & NavigableLinkedMap <T, U, W>::NonConstantIterator::operator -- () {
				this->goToPreviousElement ();
				return *this;
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::NonConstantIterator NavigableLinkedMap <T, U, W>::NonConstantIterator::operator -- (int) {
				NonConstantIterator l_copiedIterator (*this);
				this->goToPreviousElement ();
				return l_copiedIterator;
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::NonConstantIterator::value_type & NavigableLinkedMap <T, U, W>::NonConstantIterator::operator * () {
				if (this->i_currentKey.has_value ()) {
					try {
						return this->i_keyToValueMap->find (*(this->i_currentKey)).operator * ();
					}
					catch (out_of_range l_exception) {
						throw l_exception;
					}
				}
				else {
					throw out_of_range ("The key does not exist.");
				}
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::NonConstantIterator::value_type * NavigableLinkedMap <T, U, W>::NonConstantIterator::operator -> () {
				if (this->i_currentKey.has_value ()) {
					try {
						return this->i_keyToValueMap->find (*(this->i_currentKey)).operator -> ();
						
					}
					catch (out_of_range l_exception) {
						throw l_exception;
					}
				}
				else {
					throw out_of_range ("The key does not exist.");
				}
			}
			
			template <typename T, typename U, typename W> NavigableLinkedMap <T, U, W>::ConstantIterator::ConstantIterator (NavigableLinkedMap <key_type, mapped_type, key_compare> const & a_navigableLinkedMap, optional <key_type> a_currentKey) : BaseIterator (a_navigableLinkedMap, a_currentKey) {
			}
			
			template <typename T, typename U, typename W> NavigableLinkedMap <T, U, W>::ConstantIterator::ConstantIterator (BaseIterator const & a_originalIterator) : BaseIterator (a_originalIterator) {
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::ConstantIterator & NavigableLinkedMap <T, U, W>::ConstantIterator::operator ++ () {
				this->goToNextElement ();
				return *this;
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::ConstantIterator NavigableLinkedMap <T, U, W>::ConstantIterator::operator ++ (int) {
				ConstantIterator l_copiedIterator (*this);
				this->goToNextElement ();
				return l_copiedIterator;
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::ConstantIterator & NavigableLinkedMap <T, U, W>::ConstantIterator::operator -- () {
				this->goToPreviousElement ();
				return *this;
			}
			
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::ConstantIterator NavigableLinkedMap <T, U, W>::ConstantIterator::operator -- (int) {
				ConstantIterator l_copiedIterator (*this);
				this->goToPreviousElement ();
				return l_copiedIterator;
			}
			
#ifdef GCC
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::ConstantIterator::value_type & NavigableLinkedMap <T, U, W>::ConstantIterator::operator * () {
#else
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::ConstantIterator::NonConstantvalue_type const & NavigableLinkedMap <T, U, W>::ConstantIterator::operator * () {
#endif
				if (this->i_currentKey.has_value ()) {
					try {
						return (const_cast <map <key_type, mapped_type, key_compare> const *> (this->i_keyToValueMap))->find (*(this->i_currentKey)).operator * ();
					}
					catch (out_of_range l_exception) {
						throw l_exception;
					}
				}
				else {
					throw out_of_range ("The key does not exist.");
				}
			}
			
#ifdef GCC
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::ConstantIterator::value_type * NavigableLinkedMap <T, U, W>::ConstantIterator::operator -> () {
#else
			template <typename T, typename U, typename W> typename NavigableLinkedMap <T, U, W>::ConstantIterator::NonConstantvalue_type const * NavigableLinkedMap <T, U, W>::ConstantIterator::operator -> () {
#endif
				if (this->i_currentKey.has_value ()) {
					try {
						return (const_cast <map <key_type, mapped_type, key_compare> const *> (this->i_keyToValueMap))->find (*(this->i_currentKey)).operator -> ();
					}
					catch (out_of_range l_exception) {
						throw l_exception;
					}
				}
				else {
					throw out_of_range ("The key does not exist.");
				}
			}
		}
	}
}

The '::theBiasPlanet::coreUtilities::locksHandling::Locker' class is my class that locks the specified mutex as long as the Locker instance is alive.

Any position specified in any 'insert' or 'emplace_hint' call is not just a hint as is for the standard 'map', but is guaranteed to be reflected in the result.

---

4: A Test Code

Hypothesizer 7
Honestly, I have not thoroughly tested my standard-'map'-compatible elements-order-preserved map. But I have tested it a little, at least calling each method once.

This is the test code.

theBiasPlanet/tests/navigableLinkedMapTest1/Test1Test.hpp

@C++ Source Code

#include <string>

using namespace ::std;

namespace theBiasPlanet {
	namespace tests {
		namespace navigableLinkedMapTest1 {
			class Test1Test {
				public:
					class StringsComparer : public less <string> {
						private:
							bool i_isInReverseMode;
						public:
							StringsComparer (bool const a_isInReverseMode = false);
							bool operator () (string const & a_leftOperand, string const & a_rightOperand) const;
					};
					static void test (string const & a_string);
			};
		}
	}
}

theBiasPlanet/tests/navigableLinkedMapTest1/Test1Test.cpp

@C++ Source Code

#include "theBiasPlanet/tests/navigableLinkedMapTest1/Test1Test.hpp"
#include "theBiasPlanet/coreUtilities/collections/NavigableLinkedMap.hpp"
#include <iostream>
#include <string>

#include <map>

using namespace ::std;
using namespace ::theBiasPlanet::coreUtilities::collections;

namespace theBiasPlanet {
	namespace tests {
		namespace navigableLinkedMapTest1 {
			Test1Test::StringsComparer::StringsComparer (bool const a_isInReverseMode) : i_isInReverseMode (a_isInReverseMode) {
			}
			
			bool Test1Test::StringsComparer::operator () (string const & a_leftOperand, string const & a_rightOperand) const {
				if (!i_isInReverseMode) {
        			return a_leftOperand < a_rightOperand;
				}
				else {
        			return a_leftOperand > a_rightOperand;
				}
			}
			
			void Test1Test::test (string const & a_string) {
				map <string, int> l_standardMap;
				l_standardMap  [string ("ddd")] = 4;
				l_standardMap  [string ("ccc")] = 3;
				l_standardMap  [string ("bbb")] = 2;
				l_standardMap  [string ("aaa")] = 1;
				cout << "### The standard map for-loop Start" << endl << flush;
				for (map <string, int>::value_type l_keyValuePair: l_standardMap) {
					cout << "### The key/value are '" << l_keyValuePair.first << "'/'" << l_keyValuePair.second << "'." << endl << flush;
				}
				cout << "### The standard map for-loop End" << endl << endl << flush;
				
				StringsComparer l_normalStringsComparer (false);
				StringsComparer l_reverseStringsComparer (true);
				NavigableLinkedMap <string, int, StringsComparer> l_navigableLinkedMap1 (l_normalStringsComparer);
				l_navigableLinkedMap1 [string ("ddd")] = 4;
				l_navigableLinkedMap1 [string ("ccc")] = 3;
				l_navigableLinkedMap1 [string ("bbb")] = 2;
				l_navigableLinkedMap1 [string ("aaa")] = 1;
				NavigableLinkedMap <string, int, StringsComparer> l_navigableLinkedMap2 (l_reverseStringsComparer);
				l_navigableLinkedMap2 [string ("ddd")] = 4;
				l_navigableLinkedMap2 [string ("ccc")] = 3;
				l_navigableLinkedMap2 [string ("bbb")] = 2;
				l_navigableLinkedMap2 [string ("aaa")] = 1;
				NavigableLinkedMap <string, int, StringsComparer> l_navigableLinkedMap3 (l_navigableLinkedMap1.find (string ("ccc")), l_navigableLinkedMap1.find ("aaa"), l_normalStringsComparer);
				NavigableLinkedMap <string, int, StringsComparer> l_navigableLinkedMap4 ({ {string ("ddd"), 4}, {string ("ccc"), 3}, {string ("bbb"), 2}, {string ("aaa"), 1}}, l_reverseStringsComparer);
				NavigableLinkedMap <string, int, StringsComparer> l_navigableLinkedMap5 (l_navigableLinkedMap1);
				NavigableLinkedMap <string, int, StringsComparer> l_navigableLinkedMap6 (l_navigableLinkedMap2);
				l_navigableLinkedMap6 = l_navigableLinkedMap4;
				
				cout << "### The range-based for-loop of 'l_navigableLinkedMap1' Start" << endl << flush;
				for (NavigableLinkedMap <string, int, StringsComparer>::value_type l_keyValuePair: l_navigableLinkedMap1) {
					cout << "### The key/value are '" << l_keyValuePair.first << "'/'" << l_keyValuePair.second << "'." << endl << flush;
				}
				cout << "### The range-based for-loop of 'l_navigableLinkedMap1' End" << endl << endl << flush;
				
				NavigableLinkedMap <string, int, StringsComparer>::iterator l_iteratorAtEnd = l_navigableLinkedMap2.end ();
				cout << "### The explicit-iterator for-loop of 'l_navigableLinkedMap2' Start" << endl << flush;
				for (NavigableLinkedMap <string, int, StringsComparer>::iterator l_iterator = l_navigableLinkedMap2.begin (); l_iterator != l_iteratorAtEnd; l_iterator ++) {
					cout << "### The key/value are '" << l_iterator->first << "'/'" << l_iterator->second << "'." << endl << flush;
					l_iterator->second ++;
				}
				cout << "### The explicit-iterator for-loop of 'l_navigableLinkedMap2' End" << endl << endl << flush;
				
				cout << "### The explicit-iterator reverse for-loop of 'l_navigableLinkedMap3' Start" << endl << flush;
				NavigableLinkedMap <string, int, StringsComparer>::iterator l_iteratorAtStart = l_navigableLinkedMap3.begin ();
				for (NavigableLinkedMap <string, int, StringsComparer>::iterator l_iterator = l_navigableLinkedMap3.end (); l_iterator != l_iteratorAtStart;) {
					l_iterator --;
					cout << "### The key/value are '" << l_iterator->first << "'/'" << l_iterator->second << "'." << endl << flush;
				}
				cout << "### The explicit-iterator reverse for-loop of 'l_navigableLinkedMap3' End" << endl << endl << flush;
				
				cout << "### The explicit-reverse-iterator for-loop of 'l_navigableLinkedMap4' Start" << endl << flush;
				NavigableLinkedMap <string, int, StringsComparer>::reverse_iterator l_reverseIteratorAtEnd = l_navigableLinkedMap4.rend ();
				for (NavigableLinkedMap <string, int, StringsComparer>::reverse_iterator l_reverseIterator = l_navigableLinkedMap4.rbegin (); l_reverseIterator != l_reverseIteratorAtEnd; l_reverseIterator ++) {
					cout << "### The key/value are '" << (*l_reverseIterator).first << "'/'" << (*l_reverseIterator).second << "'." << endl << flush;
				}
				cout << "### The explicit-reverse-iterator for-loop of 'l_navigableLinkedMap4' End" << endl << endl << flush;
				
				cout << "### The range-based for-loop of 'l_navigableLinkedMap5' Start" << endl << flush;
				for (NavigableLinkedMap <string, int, StringsComparer>::value_type l_keyValuePair: l_navigableLinkedMap5) {
					cout << "### The key/value are '" << l_keyValuePair.first << "'/'" << l_keyValuePair.second << "'." << endl << flush;
				}
				cout << "### The range-based for-loop of 'l_navigableLinkedMap5' End" << endl << endl << flush;
				
				cout << "### The range-based for-loop of 'l_navigableLinkedMap6' Start" << endl << flush;
				for (NavigableLinkedMap <string, int, StringsComparer>::value_type l_keyValuePair: l_navigableLinkedMap6) {
					cout << "### The key/value are '" << l_keyValuePair.first << "'/'" << l_keyValuePair.second << "'." << endl << flush;
				}
				cout << "### The range-based for-loop of 'l_navigableLinkedMap6' End" << endl << endl << flush;
				
				cout << "### Check the emptiness Start" << endl << flush;
				cout << "### 'l_navigableLinkedMap6' is empty: " << l_navigableLinkedMap6.empty () << endl << flush;
				cout << "### 'l_navigableLinkedMap6' is cleared." << endl << flush;
				l_navigableLinkedMap6.clear ();
				cout << "### 'l_navigableLinkedMap6' is empty: " << l_navigableLinkedMap6.empty () << endl << flush;
				cout << "### Check the emptiness End" << endl << endl << flush;
				
				cout << "### The size of 'l_navigableLinkedMap2' is '" << l_navigableLinkedMap2.size () << "'." << endl << endl << flush;
				
				cout << "### The max size of 'l_navigableLinkedMap2' is '" << l_navigableLinkedMap2.max_size () << "'." << endl << endl << flush;
				
				cout << "### The [] operator test of 'l_navigableLinkedMap2' Start." << endl << flush;
				cout << "### The value for 'string (\"bbb\")' is set." << endl << flush;
				l_navigableLinkedMap2 [string ("bbb")] = 10;
				cout << "### The [] operator result for 'string (\"bbb\")' is '" << l_navigableLinkedMap2 [string ("bbb")] << "'." << endl << flush;
				cout << "### The [] operator result for 'string (\"eee\")' is '" << l_navigableLinkedMap2 [string ("eee")] << "'." << endl << flush;
				cout << "### The size is '" << l_navigableLinkedMap2.size () << "'." << endl << flush;
				cout << "### The [] operator test of 'l_navigableLinkedMap2' End." << endl << endl << flush;
				
				cout << "### The at function test of 'l_navigableLinkedMap2' Start." << endl << flush;
				cout << "### The value for 'string (\"bbb\")' is set." << endl << flush;
				l_navigableLinkedMap2.at (string ("bbb")) = 12;
				cout << "### The at function result for 'string (\"bbb\")' is '" << l_navigableLinkedMap2.at (string ("bbb")) << "'." << endl << flush;
				//cout << "### A at function result for 'string (\"fff\")' is '" << l_navigableLinkedMap2.at (string ("fff")) << "'." << endl << flush;
				cout << "### The size of 'l_navigableLinkedMap2' is '" << l_navigableLinkedMap2.size () << "'." << endl << flush;
				cout << "### The at function test of 'l_navigableLinkedMap2' End." << endl << endl << flush;
				
				cout << "### The insert function test of 'l_navigableLinkedMap2' Start." << endl << flush;
				cout << "### The 'string (\"fff\")' element is inserted at the end." << endl << flush;
				l_navigableLinkedMap2.insert (NavigableLinkedMap <string, int, StringsComparer>::value_type (string ("fff"), 6));
				cout << "### The 'string (\"ggg\")' element is inserted at the beginning." << endl << flush;
				l_navigableLinkedMap2.insert (l_navigableLinkedMap2.begin (), NavigableLinkedMap <string, int, StringsComparer>::value_type (string ("ggg"), 7));
				cout << "### The 'string (\"hhh\")' element is inserted before the string (\"ccc\") element." << endl << flush;
				l_navigableLinkedMap2.insert (l_navigableLinkedMap2.find (string ("ccc")), NavigableLinkedMap <string, int, StringsComparer>::value_type (string ("hhh"), 8));
				NavigableLinkedMap <string, int, StringsComparer> l_navigableLinkedMap7 ({ {string ("iii"), 9}, {string ("jjj"), 10}, {string ("kkk"), 11}, {string ("lll"), 12}}, l_reverseStringsComparer);
				cout << "### The 'string (\"iii\")', 'string (\"jjj\")', and 'string (\"kkk\")' elements are inserted at the end." << endl << flush;
				l_navigableLinkedMap2.insert (l_navigableLinkedMap7.begin (), l_navigableLinkedMap7.find (string ("lll")));
				for (NavigableLinkedMap <string, int, StringsComparer>::value_type l_keyValuePair: l_navigableLinkedMap2) {
					cout << "### The key/value are '" << l_keyValuePair.first << "'/'" << l_keyValuePair.second << "'." << endl << flush;
				}
				cout << "### The insert function test of 'l_navigableLinkedMap2' End." << endl  << endl<< flush;
				
				cout << "### The erase function test of 'l_navigableLinkedMap2' Start." << endl << flush;
				cout << "### The 'string (\"iii\")' element is erased." << endl << flush;
				l_navigableLinkedMap2.erase (l_navigableLinkedMap7.find (string ("iii")));
				cout << "### The 'string (\"eee\")' element is erased." << endl << flush;
				l_navigableLinkedMap2.erase (string ("eee"));
				cout << "### The 'string (\"jjj\")' element is erased." << endl << flush;
				l_navigableLinkedMap2.erase (l_navigableLinkedMap7.find (string ("jjj")), l_navigableLinkedMap7.find (string ("kkk")));
				for (NavigableLinkedMap <string, int, StringsComparer>::value_type l_keyValuePair: l_navigableLinkedMap2) {
					cout << "### The key/value are '" << l_keyValuePair.first << "'/'" << l_keyValuePair.second << "'." << endl << flush;
				}
				cout << "### The erase function test of 'l_navigableLinkedMap2' End." << endl << endl << flush;
				
				cout << "### The swap function test of 'l_navigableLinkedMap2' with 'l_navigableLinkedMap4' Start." << endl << flush;
				l_iteratorAtStart = l_navigableLinkedMap2.begin ();
				cout << "### The iterator at the beginning of 'l_navigableLinkedMap2' before swap is '" << l_iteratorAtStart->first << "'/'" << l_iteratorAtStart->second << "'." << endl << flush;
				cout << "### 'l_navigableLinkedMap2' is swapped with 'l_navigableLinkedMap4'." << endl << flush;
				l_navigableLinkedMap2.swap (l_navigableLinkedMap4);
				cout << "### The iterator after swap is '" << l_iteratorAtStart->first << "'/'" << l_iteratorAtStart->second << "'." << endl << flush;
				cout << "### Seeing the contents of 'l_navigableLinkedMap2' Start." << endl << flush;
				for (NavigableLinkedMap <string, int, StringsComparer>::value_type l_keyValuePair: l_navigableLinkedMap2) {
					cout << "### The key/value are '" << l_keyValuePair.first << "'/'" << l_keyValuePair.second << "'." << endl << flush;
				}
				cout << "### Seeing the contents of 'l_navigableLinkedMap2' End." << endl << flush;
				cout << "### Seeing the contents of 'l_navigableLinkedMap4' Start." << endl << flush;
				for (NavigableLinkedMap <string, int, StringsComparer>::value_type l_keyValuePair: l_navigableLinkedMap4) {
					cout << "### The key/value are '" << l_keyValuePair.first << "'/'" << l_keyValuePair.second << "'." << endl << flush;
				}
				cout << "### Seeing the contents of 'l_navigableLinkedMap4' End." << endl << flush;
				cout << "### The swap function test of 'l_navigableLinkedMap2' with 'l_navigableLinkedMap4' End." << endl << endl << flush;
				
				cout << "### The emplace function test of 'l_navigableLinkedMap4' Start." << endl << flush;
				cout << "### The 'string (\"eee\")' element is emplaced." << endl << flush;
				l_navigableLinkedMap4.emplace (string ("eee"), 6);
				cout << "### The 'string (\"mmm\")' element is emplaced before the 'string (\"ccc\")' element." << endl << flush;
				l_navigableLinkedMap4.emplace_hint (l_navigableLinkedMap4.find (string ("ccc")), string ("mmm"), 13);
				for (NavigableLinkedMap <string, int, StringsComparer>::value_type l_keyValuePair: l_navigableLinkedMap4) {
					cout << "### The key/value are '" << l_keyValuePair.first << "'/'" << l_keyValuePair.second << "'." << endl << flush;
				}
				cout << "### The emplace function test of 'l_navigableLinkedMap4' End." << endl << endl << flush;
				
				cout << "### The key_comp function test of 'l_navigableLinkedMap1' and 'l_navigableLinkedMap4' Start." << endl << flush;
				cout << "### A key_comp result of 'l_navigableLinkedMap1' for 'string (\"ccc\") <  string (\"bbb\")' is " << (l_navigableLinkedMap1.key_comp ()) (string ("ccc"), string ("bbb")) << "'." << endl << flush;
				cout << "### A key_comp result of 'l_navigableLinkedMap4' for 'string (\"ccc\") <  string (\"bbb\")' is " << (l_navigableLinkedMap4.key_comp ()) (string ("ccc"), string ("bbb")) << "'." << endl << flush;
				cout << "### The key_comp function test of 'l_navigableLinkedMap1' and 'l_navigableLinkedMap4' End." << endl << endl << flush;
				
				cout << "### The value_comp function test of 'l_navigableLinkedMap1' and 'l_navigableLinkedMap4' Start." << endl << flush;
				cout << "### A value_comp result of 'l_navigableLinkedMap1' for 'string (\"ccc\") <  string (\"ddd\")' is " << (l_navigableLinkedMap1.value_comp ()) (NavigableLinkedMap <string, int, StringsComparer>::value_type (string ("ccc"), 3), NavigableLinkedMap <string, int, StringsComparer>::value_type (string ("ddd"), 2)) << "'." << endl << flush;
				cout << "### A value_comp result of 'l_navigableLinkedMap4' for 'string (\"ccc\") <  string (\"ddd\")' is " << (l_navigableLinkedMap4.value_comp ()) (NavigableLinkedMap <string, int, StringsComparer>::value_type (string ("ccc"), 3), NavigableLinkedMap <string, int, StringsComparer>::value_type (string ("ddd"), 2)) << "'." << endl << flush;
				cout << "### The value_comp function test of 'l_navigableLinkedMap1' and 'l_navigableLinkedMap4' End." << endl << endl << flush;
				
				cout << "### The count function test of 'l_navigableLinkedMap4' Start." << endl << flush;
				cout << "### A count result for 'string (\"aaa\")' is " << l_navigableLinkedMap4.count (string ("aaa")) << "'." << endl << flush;
				cout << "### A count result is for 'string (\"nnn\")' " << l_navigableLinkedMap4.count (string ("nnn")) << "'." << endl << flush;
				cout << "### The count function test of 'l_navigableLinkedMap4' End." << endl << endl << flush;
				
				cout << "### The lower_bound function test of 'l_navigableLinkedMap1' and 'l_navigableLinkedMap4' Start." << endl << flush;
				cout << "### A lower_bound result of 'l_navigableLinkedMap1' for 'string (\"ccc\")' is " << (l_navigableLinkedMap1.lower_bound (string ("ccc")))->first << "'." << endl << flush;
				cout << "### A lower_bound result of 'l_navigableLinkedMap1' for 'string (\"nnn\")' is " << ((l_navigableLinkedMap1.lower_bound (string ("nnn"))) == l_navigableLinkedMap1.end ()) << "'." << endl << flush;
				cout << "### A lower_bound result of 'l_navigableLinkedMap4' for 'string (\"ccc\")' is " << (l_navigableLinkedMap4.lower_bound (string ("ccc")))->first << "'." << endl << flush;
				cout << "### A lower_bound result of 'l_navigableLinkedMap4' for 'string (\"nnn\")' is " << ((l_navigableLinkedMap4.lower_bound (string ("nnn"))) == l_navigableLinkedMap4.end ()) << "'." << endl << flush;
				cout << "### The lower_bound function test of 'l_navigableLinkedMap1' and 'l_navigableLinkedMap4' End." << endl << endl << flush;
				
				cout << "### The upper_bound function test of 'l_navigableLinkedMap1' and 'l_navigableLinkedMap4' Start." << endl << flush;
				cout << "### A upper_bound result of 'l_navigableLinkedMap1' for 'string (\"ccc\")' is " << (l_navigableLinkedMap1.upper_bound (string ("ccc")))->first << "'." << endl << flush;
				cout << "### A upper_bound result of 'l_navigableLinkedMap1' for 'string (\"nnn\")' is " << ((l_navigableLinkedMap1.upper_bound (string ("nnn"))) == l_navigableLinkedMap1.end ()) << "'." << endl << flush;
				cout << "### A upper_bound result of 'l_navigableLinkedMap4' for 'string (\"ccc\")' is " << (l_navigableLinkedMap4.upper_bound (string ("ccc")))->first << "'." << endl << flush;
				cout << "### A upper_bound result of 'l_navigableLinkedMap4' for 'string (\"nnn\")' is " << ((l_navigableLinkedMap4.upper_bound (string ("nnn"))) == l_navigableLinkedMap4.end ()) << "'." << endl << flush;
				cout << "### The upper_bound function test of 'l_navigableLinkedMap1' and 'l_navigableLinkedMap4' End." << endl << endl << flush;
				
				cout << "### The equal_range function test of 'l_navigableLinkedMap1' and 'l_navigableLinkedMap4' Start." << endl << flush;
				cout << "### The equal_range result of 'l_navigableLinkedMap1' for 'string (\"ddd\")' is '" << (l_navigableLinkedMap1.equal_range (string ("ddd"))).first->first << "->" << (l_navigableLinkedMap1.equal_range (string ("ddd"))).second->first << "'." << endl << flush;
				cout << "### The equal_range result of 'l_navigableLinkedMap1' for 'string (\"nnn\")' is '" << ((l_navigableLinkedMap1.equal_range (string ("nnn")).first) == l_navigableLinkedMap1.end ()) << "'." << endl << flush;
				cout << "### The equal_range result of 'l_navigableLinkedMap4' for 'string (\"ddd\")' is '" << (l_navigableLinkedMap4.equal_range (string ("ddd"))).first->first << "->" << (l_navigableLinkedMap4.equal_range (string ("ddd"))).second->first << "'." << endl << flush;
				cout << "### The equal_range result of 'l_navigableLinkedMap4' for 'string (\"nnn\")' is '" << ((l_navigableLinkedMap4.equal_range (string ("nnn")).first) == l_navigableLinkedMap4.end ()) << "'." << endl << flush;
				cout << "### The equal_range function test of 'l_navigableLinkedMap1' and 'l_navigableLinkedMap4' End." << endl << endl << flush;
				
				cout << "### The get_allocator function test of 'l_navigableLinkedMap4' Start." << endl << flush;
				l_navigableLinkedMap4.get_allocator ();
				
				cout << "### The get_allocator function test of 'l_navigableLinkedMap4' End." << endl << flush;
				
			}
		}
	}
}

'l_standardMap' is a standard 'map' instance that is tested for a comparison: its elements are not retrieved in the order in which they are inserted in it.

'::theBiasPlanet::tests::navigableLinkedMapTest1::Test1Test::StringsComparer' is a keys comparer that compares the specified two string keys in the normal order or in the reverse order. Whichever of 'l_normalStringsComparer' and 'l_reverseStringsComparer' is used for an elements-order-preserved map instance does not influence the order in which the elements are contained in the map instance, because the order is not determined by any comparison of keys, but by the positions of the elements that (the positions) are specified when the elements are inserted. But the comparer instance used for an elements-order-preserved map instance influences the results of the methods, 'key_comp', 'value_comp', 'lower_bound', 'upper_bound', and 'equal_range'.

The result is this.

@Output

### The standard map for-loop Start
### The key/value are 'aaa'/'1'.
### The key/value are 'bbb'/'2'.
### The key/value are 'ccc'/'3'.
### The key/value are 'ddd'/'4'.
### The standard map for-loop End

### The range-based for-loop of 'l_navigableLinkedMap1' Start
### The key/value are 'ddd'/'4'.
### The key/value are 'ccc'/'3'.
### The key/value are 'bbb'/'2'.
### The key/value are 'aaa'/'1'.
### The range-based for-loop of 'l_navigableLinkedMap1' End

### The explicit-iterator for-loop of 'l_navigableLinkedMap2' Start
### The key/value are 'ddd'/'4'.
### The key/value are 'ccc'/'3'.
### The key/value are 'bbb'/'2'.
### The key/value are 'aaa'/'1'.
### The explicit-iterator for-loop of 'l_navigableLinkedMap2' End

### The explicit-iterator reverse for-loop of 'l_navigableLinkedMap3' Start
### The key/value are 'bbb'/'2'.
### The key/value are 'ccc'/'3'.
### The explicit-iterator reverse for-loop of 'l_navigableLinkedMap3' End

### The explicit-reverse-iterator for-loop of 'l_navigableLinkedMap4' Start
### The key/value are 'aaa'/'1'.
### The key/value are 'bbb'/'2'.
### The key/value are 'ccc'/'3'.
### The key/value are 'ddd'/'4'.
### The explicit-reverse-iterator for-loop of 'l_navigableLinkedMap4' End

### The range-based for-loop of 'l_navigableLinkedMap5' Start
### The key/value are 'ddd'/'4'.
### The key/value are 'ccc'/'3'.
### The key/value are 'bbb'/'2'.
### The key/value are 'aaa'/'1'.
### The range-based for-loop of 'l_navigableLinkedMap5' End

### The range-based for-loop of 'l_navigableLinkedMap6' Start
### The key/value are 'ddd'/'4'.
### The key/value are 'ccc'/'3'.
### The key/value are 'bbb'/'2'.
### The key/value are 'aaa'/'1'.
### The range-based for-loop of 'l_navigableLinkedMap6' End

### Check the emptiness Start
### 'l_navigableLinkedMap6' is empty: 0
### 'l_navigableLinkedMap6' is cleared.
### 'l_navigableLinkedMap6' is empty: 1
### Check the emptiness End

### The size of 'l_navigableLinkedMap2' is '4'.

### The max size of 'l_navigableLinkedMap2' is '256204778801521550'.

### The [] operator test of 'l_navigableLinkedMap2' Start.
### The value for 'string ("bbb")' is set.
### The [] operator result for 'string ("bbb")' is '10'.
### The [] operator result for 'string ("eee")' is '0'.
### The size is '5'.
### The [] operator test of 'l_navigableLinkedMap2' End.

### The at function test of 'l_navigableLinkedMap2' Start.
### The value for 'string ("bbb")' is set.
### The at function result for 'string ("bbb")' is '12'.
### The size of 'l_navigableLinkedMap2' is '5'.
### The at function test of 'l_navigableLinkedMap2' End.

### The insert function test of 'l_navigableLinkedMap2' Start.
### The 'string ("fff")' element is inserted at the end.
### The 'string ("ggg")' element is inserted at the beginning.
### The 'string ("hhh")' element is inserted before the string ("ccc") element.
### The 'string ("iii")', 'string ("jjj")', and 'string ("kkk")' elements are inserted at the end.
### The key/value are 'ggg'/'7'.
### The key/value are 'ddd'/'5'.
### The key/value are 'hhh'/'8'.
### The key/value are 'ccc'/'4'.
### The key/value are 'bbb'/'12'.
### The key/value are 'aaa'/'2'.
### The key/value are 'eee'/'0'.
### The key/value are 'fff'/'6'.
### The key/value are 'iii'/'9'.
### The key/value are 'jjj'/'10'.
### The key/value are 'kkk'/'11'.
### The insert function test of 'l_navigableLinkedMap2' End.

### The erase function test of 'l_navigableLinkedMap2' Start.
### The 'string ("iii")' element is erased.
### The 'string ("eee")' element is erased.
### The 'string ("jjj")' element is erased.
### The key/value are 'ggg'/'7'.
### The key/value are 'ddd'/'5'.
### The key/value are 'hhh'/'8'.
### The key/value are 'ccc'/'4'.
### The key/value are 'bbb'/'12'.
### The key/value are 'aaa'/'2'.
### The key/value are 'fff'/'6'.
### The key/value are 'kkk'/'11'.
### The erase function test of 'l_navigableLinkedMap2' End.

### The swap function test of 'l_navigableLinkedMap2' with 'l_navigableLinkedMap4' Start.
### The iterator at the beginning of 'l_navigableLinkedMap2' before swap is 'ggg'/'7'.
### 'l_navigableLinkedMap2' is swapped with 'l_navigableLinkedMap4'.
### The iterator after swap is 'ggg'/'7'.
### Seeing the contents of 'l_navigableLinkedMap2' Start.
### The key/value are 'ddd'/'4'.
### The key/value are 'ccc'/'3'.
### The key/value are 'bbb'/'2'.
### The key/value are 'aaa'/'1'.
### Seeing the contents of 'l_navigableLinkedMap2' End.
### Seeing the contents of 'l_navigableLinkedMap4' Start.
### The key/value are 'ggg'/'7'.
### The key/value are 'ddd'/'5'.
### The key/value are 'hhh'/'8'.
### The key/value are 'ccc'/'4'.
### The key/value are 'bbb'/'12'.
### The key/value are 'aaa'/'2'.
### The key/value are 'fff'/'6'.
### The key/value are 'kkk'/'11'.
### Seeing the contents of 'l_navigableLinkedMap4' End.
### The swap function test of 'l_navigableLinkedMap2' with 'l_navigableLinkedMap4' End.

### The emplace function test of 'l_navigableLinkedMap4' Start.
### The 'string ("eee")' element is emplaced.
### The 'string ("mmm")' element is emplaced before the 'string ("ccc")' element.
### The key/value are 'ggg'/'7'.
### The key/value are 'ddd'/'5'.
### The key/value are 'hhh'/'8'.
### The key/value are 'mmm'/'13'.
### The key/value are 'ccc'/'4'.
### The key/value are 'bbb'/'12'.
### The key/value are 'aaa'/'2'.
### The key/value are 'fff'/'6'.
### The key/value are 'kkk'/'11'.
### The key/value are 'eee'/'6'.
### The emplace function test of 'l_navigableLinkedMap4' End.

### The key_comp function test of 'l_navigableLinkedMap1' and 'l_navigableLinkedMap4' Start.
### A key_comp result of 'l_navigableLinkedMap1' for 'string ("ccc") <  string ("bbb")' is 0'.
### A key_comp result of 'l_navigableLinkedMap4' for 'string ("ccc") <  string ("bbb")' is 1'.
### The key_comp function test of 'l_navigableLinkedMap1' and 'l_navigableLinkedMap4' End.

### The value_comp function test of 'l_navigableLinkedMap1' and 'l_navigableLinkedMap4' Start.
### A value_comp result of 'l_navigableLinkedMap1' for 'string ("ccc") <  string ("ddd")' is 1'.
### A value_comp result of 'l_navigableLinkedMap4' for 'string ("ccc") <  string ("ddd")' is 0'.
### The value_comp function test of 'l_navigableLinkedMap1' and 'l_navigableLinkedMap4' End.

### The count function test of 'l_navigableLinkedMap4' Start.
### A count result for 'string ("aaa")' is 1'.
### A count result is for 'string ("nnn")' 0'.
### The count function test of 'l_navigableLinkedMap4' End.

### The lower_bound function test of 'l_navigableLinkedMap1' and 'l_navigableLinkedMap4' Start.
### A lower_bound result of 'l_navigableLinkedMap1' for 'string ("ccc")' is ddd'.
### A lower_bound result of 'l_navigableLinkedMap1' for 'string ("nnn")' is 1'.
### A lower_bound result of 'l_navigableLinkedMap4' for 'string ("ccc")' is ccc'.
### A lower_bound result of 'l_navigableLinkedMap4' for 'string ("nnn")' is 0'.
### The lower_bound function test of 'l_navigableLinkedMap1' and 'l_navigableLinkedMap4' End.

### The upper_bound function test of 'l_navigableLinkedMap1' and 'l_navigableLinkedMap4' Start.
### A upper_bound result of 'l_navigableLinkedMap1' for 'string ("ccc")' is ddd'.
### A upper_bound result of 'l_navigableLinkedMap1' for 'string ("nnn")' is 1'.
### A upper_bound result of 'l_navigableLinkedMap4' for 'string ("ccc")' is bbb'.
### A upper_bound result of 'l_navigableLinkedMap4' for 'string ("nnn")' is 0'.
### The upper_bound function test of 'l_navigableLinkedMap1' and 'l_navigableLinkedMap4' End.

### The equal_range function test of 'l_navigableLinkedMap1' and 'l_navigableLinkedMap4' Start.
### The equal_range result of 'l_navigableLinkedMap1' for 'string ("ddd")' is 'ddd->ccc'.
### The equal_range result of 'l_navigableLinkedMap1' for 'string ("nnn")' is '1'.
### The equal_range result of 'l_navigableLinkedMap4' for 'string ("ddd")' is 'ddd->hhh'.
### The equal_range result of 'l_navigableLinkedMap4' for 'string ("nnn")' is '0'.
### The equal_range function test of 'l_navigableLinkedMap1' and 'l_navigableLinkedMap4' End.

### The get_allocator function test of 'l_navigableLinkedMap4' Start.
### The get_allocator function test of 'l_navigableLinkedMap4' End.

---

5: The Source Files Are Here

Hypothesizer 7
I fact, the source files are included in this ZIP file. How to build the project contained in the ZIP file is explained here (a build environment will have to be built first as is explained here for Linux or here for Windows).

---

6: The Conclusion and Beyond

Hypothesizer 7
Now, I have a standard-'map'-compatible elements-order-preserved map.

I will be able to create any standard-container-compatible custom container in the same way.

As I have used the template feature of C++ for the elements-order-preserved map, I have found some pitfalls (by falling into them) that should be bewared of, especially by any Java programmer who has understood the template feature in an analogy of the Java generics feature. I will discuss about them in the next article.

---

References

<The previous article in this series | The table of contents of this series | The next article in this series>