Another way to implement this is with a map
instead of a vector
. I will show you this approach and discuss the differences:
Just create a class that has two maps behind the scenes.
#include <map>
#include <string>
using namespace std;
class SpecialMap {
// usual stuff...
private:
int counter_;
map<int, string> insertion_order_;
map<string, int> data_;
};
You can then expose an iterator to iterator over data_
in the proper order. The way you do that is iterate through insertion_order_
, and for each element you get from that iteration, do a lookup in the data_
with the value from insertion_order_
You can use the more efficient hash_map
for insertion_order since you don't care about directly iterating through insertion_order_
.
To do inserts, you can have a method like this:
void SpecialMap::Insert(const string& key, int value) {
// This may be an over simplification... You ought to check
// if you are overwriting a value in data_ so that you can update
// insertion_order_ accordingly
insertion_order_[counter_++] = key;
data_[key] = value;
}
There are a lot of ways you can make the design better and worry about performance, but this is a good skeleton to get you started on implementing this functionality on your own. You can make it templated, and you might actually store pairs as values in data_ so that you can easily reference the entry in insertion_order_. But I leave these design issues as an exercise :-).
Update: I suppose I should say something about efficiency of using map vs. vector for insertion_order_
- lookups directly into data, in both cases are O(1)
- inserts in the vector approach are O(1), inserts in the map approach are O(logn)
- deletes in the vector approach are O(n) because you have to scan for the item to remove. With the map approach they are O(logn).
Maybe if you are not going to use deletes as much, you should use the vector approach. The map approach would be better if you were supporting a different ordering (like priority) instead of insertion order.