Custom STL Containers

Question

I have written code that allows one to traverse mapped data in the order it was entered.

The solution I coded a couple of times was:

Given a keytype, K, and and data type, D, std::map std::vector

When one wanted to randomly find a data entry, use map.find(K). When one wanted to traverse the map in entry order, use std::vector::iterator (begin(), end()].

This was fine, but as an exercise, I wanted to write this 'OrderedMap' as an STL compliant container. I also have (stripped down to this discussion):

template <typename K, typename D>
class OrderedMapValue
{
private:
    K first_ref;
    std::map<K,size_t>& m;
    std::vector<D>& v;
public:
    const K& first
    D& second
    assignment operator=(const D& data) 
    {
        std::map<K,size_t>::const_iterator iter = m.find(first_ref);
        v[iter.second] = data;  // error checking of iter stripped
    }
};

Further assuming

template <typename K, typename D>
class OrderedMap
{
public:
     typename OrderedMapValue<K,D>& OrderedMap<K,D>::operator[](const K&);
     // snip...
};

class MyClass
{
public:
    MyClass(std::string s) : _my_data(s) {}
private:
    std::string _my_data;
};

The following code works:

OrderedMap<std::string,MyClass*> omap;
omap["MyKey"] = new MyClass("dummy");

However, this code does not:

OrderedMap::iterator iter = omap.find("MyKey");
MyClass * obj = iter->second;
delete obj;
iter->second = new MyClass("dummy");

Assuming I have done something a) Structurally silly or b) Unnecessarily complex, how should this be done?

I realize that I'm likely reinventing the wheel here, but again, this effort is mainly to increase my knowledge of STL containers, their design patterns and proper use.

Thanks in advance for any insights,

Answer 1

In OrderedMapValue::operator=, you have:

    std::map<K,size_t>::const_iterator iter = m.find(first_ref);

What is first_ref? The code doesn't reference it (no pun intended) elsewhere. It looks to me like it might be a vestige from an older implementation, replaced elsewhere by the public member

const K& first.

Could this be the problem?

EDIT from the comments: The code doesn't show that first_ref is initialized anywhere; so for all I can tell, the call to m.find(first_ref) is searching for an empty string, rather than the key for the OrderedMapValue.

Answer 2

I don't have a compiler right now to test this, so there could be errors, but I think you want it more like:

template <typename K, typename D>
class OrderedMap
{
private:
     std::map<K,size_t> &m;
     std::vector<D> &v;
public:
 typename pair<K,D> TYPE;

     TYPE& operator[](const K &k)
 {
  return v[ m[ k ]];
 }

 TYPE& operator[](size_t idx)
 {
  return v[ idx ];
 }

 pair<iterator,bool> insert( const TYPE& pair )
 {
  map<K, size_t>::const_iterator iter;
  iter = m.find( pair.first );

  if( iter != m.end() )
   return make_pair( v[ iter.second], false );

  m.insert( make_pair( pair->first, v.size() ));
  v.push_back( pair->second );

  return make_pair(  v.last() , inserted );
 }

 iterator &begin()
 {
  return v.begin();
 }
 // etc
};