Creating a Sequentially Indexed Ordered Map

Question

The following code shows a very basic but essential functionality I would like to create and am getting some nasty run-time errors currently which I have not been able to debug myself. I have been working to write a solution to what I am looking for and this is the closest I have come. Any help in identifying a fix or re-design of this implementation is greatly appreciated!

This is the class. What I am looking for is a map which can still perform its operator[key] functionality but also be iterated through in sequential order as the elements were added. I am attempting to do this by having a map for lookup with its value being a pointer to the real value being held in a vector of corresponding pairs.

template <typename t>
class IndexedMap {
 public:
  t& operator [] (string s) {
    bool nu = true;

    for (auto& e : actual) // for each pair
      if  (e.first == s) // if exist
    nu = false; 
    if (nu == true) { // if needs created
      actual.push_back(pair <string, t>()); // create proper pair
      actual.back().first = s; // assign key
      // create copy in map @ same key pointing to actual value
      lookup[s] = &actual.back().second;
    }
    return *lookup[s]; // return reference to value
  }

  typename vector <pair <string, t>>::iterator begin () {
    return actual.begin();
  }

  typename vector <pair <string, t>>::iterator end () {
    return actual.end();
  }

 private:
  vector <pair <string, t>> actual;
  map <string, t*> lookup;
};

This implementation "works" with the following test.cpp- meaning that it will run and I actually do see the result I am looking for, but upon exit of test.cpp I am getting some crazy errors involving a call to free() and I am not sure how that is taking place or how to fix.

test.cpp :

int main () {
  IndexedMap <vector <int>> test;

  test["BILLS"]; test["GAS"]; 
  test["GROCERY"]; test["PETS"]; 
  test["TAKEOUT"]; test["OTHER"];

  int i = 0;
  for (auto e : test) // check order
    cout << e.first << endl;
  for (auto& e : test) // assign 3 unique values to each vector
    for (int f = 0; f < 3; ++f, ++i)
      e.second.push_back(i);
  for (auto e : test) { // display them
    cout << e.first << ":" << endl;
    for (auto f : e.second)
      cout << f << endl;
  }
  vector <int> blank; // test modifying a value
  test["GAS"] = blank;
  for (auto e : test["GAS"])
    cout << e << endl;
  cout << "hopefully empty?" << endl;
}

I hope this is not all too confusing the way I have explained or written this out. Many thanks in advance to any help that can be provided.

Happy new year everyone!

Answer 1

Thanks to help from @juanchopanza Ive come up with a working solution for this problem.

Still unsure of exactly where or how the pointers are being invalidated in the previous implementation posted above, but now by using indices to identify the proper element in the vector and then returning that element itself, rather than a pointer to this location I am safe ;)

t& operator [] (string s) {
    bool nu = true;

    for (auto& e : actual) // for each pair
      if  (e.first == s) // if exist
        nu = false; 
    if (nu == true) { // if needs created
      actual.push_back(pair <string, t>()); // create proper pair
      actual.back().first = s; // assign key
      lookup[s] = actual.size()-1; // assign proper index in map @ same key 
    }
    return actual[lookup[s]].second; // return reference to value
  }

Answer 2

This line exposes the error

actual.push_back(pair <string, t>()); // create proper pair

and this is where the misery stems from.

lookup[s] = &actual.back().second; // a pointer to an element in a vector.

What happens when the vector resizes? a new array is allocated for the vector and the data from the old array is copied into the new array and the old array is deallocated. This invalidates the pointers into the old array.

Lets evaluate your solution a bit, you iterate through the vector to see if s exists, this is O(N) and if found you make a lookup in the map anyway of O(log N).

And we want to use an index into actual instead of a pointer, so your map pair should be

using mappair = std::pair<std::string,  int>;

So if we rewrite (untested code)

for (auto& e : actual) // for each pair
  if  (e.first == s) // if exist
    nu = false; 
if (nu == true) { // if needs created
  actual.push_back(pair <string, t>()); // create proper pair
  actual.back().first = s; // assign key
  // create copy in map @ same key pointing to actual value
  lookup[s] = &actual.back().second;
}
return *lookup[s]; // return reference to value

to

auto found = lookup.insert(mappair(s, -1));
if (found.second) { // true if new element
  actual.emplace_back(mappair(s,t());
  found->first.second = actual.size()-1;
}
return *found.first;