C++ code only. Comments would help. Here is the .h file:

proj09_trimap.h

#ifndef TRIMAP #define TRIMAP

#include using std::string; #include using std::ostream; #include using std::vector; #include using std::initializer_list;

class Element{ private: string key_; size_t index_ = 0;

public: string value_;

Element()=default; Element(string k, string v, long i): key_(k), index_(i), value_(v) {} ;

friend class TriMap; friend ostream& operator

class TriMap { private: vector vec_; size_t sz_ = 0;

public: TriMap() = default; TriMap(const Element&); TriMap(initializer_list);

size_t size(); bool insert(string,string); bool remove(string); Element* find_key(const string&); Element* find_value(const string&); Element* find_index(size_t);

friend ostream& operator

#endif

The Problem You have done work with an STL map, a way to map a key to a value. But there are some restrictions on a map. You can search a map for a key (and then the associated value) but you cannot search a map for a value (and then the associated key). Furthermore, because a map is kept in a particular order, an ordering based on the keys, we cannot know the order of insertion of each element. We are going to fix all that with a new STL-like data structure, the TriMap Basic Premise The underlying implementation of an STL map is such that search for a key (which is all you are allowed to do) is very fast. That underlying data structure is not fixed by the STL implementers, but it is likely something like a red-black tree (look it up). That is quite beyond us at this stage However, we can keep a vector as the underlying data structure and keep that vector in key-sorted order for fairly fast lookup. That is what we are going to do! We are also going to make astructcalled Element that will store the key, the associated value and the insertion number (called the index here) indicating the order of placing an Element in the data structure Element struct key value ^naex_vector, key order robin boywonder homer george unglesimpson insert homer george junglesimpson boywonder robin cat insert woman robin boywonder cat homer george jungle remove Woman george cat homer robin Woman s1mOson boywonder Element is shown as a key-value-index triple (a struct). We maintain a vector in key order. When an insert occurs, the new element is placed in the vector so that key-order is maintained. In this way, we can quickly do a search through the vector to find a key (or note that it does not exist) using a binary search (but see below on how to do that). However, with this data structure we can also doa search for an index or a value, though we can only do it by a linear search Like a map, TriMap only allows one example of a key. That is, only one Element in the TriMap can have a particular key. No duplicates allowed. The Problem You have done work with an STL map, a way to map a key to a value. But there are some restrictions on a map. You can search a map for a key (and then the associated value) but you cannot search a map for a value (and then the associated key). Furthermore, because a map is kept in a particular order, an ordering based on the keys, we cannot know the order of insertion of each element. We are going to fix all that with a new STL-like data structure, the TriMap Basic Premise The underlying implementation of an STL map is such that search for a key (which is all you are allowed to do) is very fast. That underlying data structure is not fixed by the STL implementers, but it is likely something like a red-black tree (look it up). That is quite beyond us at this stage However, we can keep a vector as the underlying data structure and keep that vector in key-sorted order for fairly fast lookup. That is what we are going to do! We are also going to make astructcalled Element that will store the key, the associated value and the insertion number (called the index here) indicating the order of placing an Element in the data structure Element struct key value ^naex_vector, key order robin boywonder homer george unglesimpson insert homer george junglesimpson boywonder robin cat insert woman robin boywonder cat homer george jungle remove Woman george cat homer robin Woman s1mOson boywonder Element is shown as a key-value-index triple (a struct). We maintain a vector in key order. When an insert occurs, the new element is placed in the vector so that key-order is maintained. In this way, we can quickly do a search through the vector to find a key (or note that it does not exist) using a binary search (but see below on how to do that). However, with this data structure we can also doa search for an index or a value, though we can only do it by a linear search Like a map, TriMap only allows one example of a key. That is, only one Element in the TriMap can have a particular key. No duplicates allowed