Is there a 'parent' stl container class?

[winbatch]

I may not be asking this question right... Basically, I have a wrapper around an stl map. I would like to use either a map or a hash_map based on whether the user wants the items sorted or not. To achieve this, I wanted to have a pointer to the 'parent' class of both, and then based on the flag, either create a new map or a new hash_map. Is there a way to do this? Or should I just use a hash_map and sort it whenever anyone asks for an iterator?

By the way, I've been experimenting with hash_map and it seems that it is still somehow sorted. (Though this could be simply that the most efficient way to store hash_map<string,string> is in fact to sort it). Is there a way I can test/prove that a hash_map is not sorted?

[Dogtree]

There's not a common base class for map and hash_map since hash_map isn't even a standard container and they aren't commonly implemented in remotely the same way. set and map might have a common base class, but that's an implementation detail that you shouldn't rely on because the standard doesn't require it. A better way to design your map wrapper would be with policies:

#include <iostream>
#include <map>
#include <set>

template <typename MapType>
class MapWrap {
  MapType m;
public:
  typedef MapType value_type;
  MapType& get() { return m; }
};

int main()
{
  MapWrap<std::map<int, int> > wrap1;
  MapWrap<std::set<int> > wrap2;

  for (int i = 0; i < 10; i++)
    wrap1.get()[i] = i * i;

  for (int i = 0; i < 10; i++)
    wrap2.get().insert(i);

  MapWrap<std::map<int, int> >::value_type::iterator it1 = wrap1.get().begin();

  while (it1 != wrap1.get().end()) {
    std::cout << it1->first << ' ' << it1->second << '\n';
    ++it1;
  }

  std::cout << '\n';

  MapWrap<std::set<int> >::value_type::iterator it2 = wrap2.get().begin();

  while (it2 != wrap2.get().end()) {
    std::cout << *it2 << '\n';
    ++it2;
  }
}

You could also inherit from MapType:

#include <iostream>
#include <map>
#include <set>

template <typename MapType>
class MapWrap: public MapType {
};

int main()
{
  MapWrap<std::map<int, int> > wrap1;
  MapWrap<std::set<int> > wrap2;

  for (int i = 0; i < 10; i++)
    wrap1[i] = i * i;

  for (int i = 0; i < 10; i++)
    wrap2.insert(i);

  MapWrap<std::map<int, int> >::iterator it1 = wrap1.begin();

  while (it1 != wrap1.end()) {
    std::cout << it1->first << ' ' << it1->second << '\n';
    ++it1;
  }

  std::cout << '\n';

  MapWrap<std::set<int> >::iterator it2 = wrap2.begin();

  while (it2 != wrap2.end()) {
    std::cout << *it2 << '\n';
    ++it2;
  }
}

This is slightly more convenient and considerably more dangerous because you have to be careful not to treat MapWrap as a polymorphic type because the standard containers were not designed to be used as base classes.

>> Is there a way I can test/prove that a hash_map is not sorted?
If a hash_map happens to be sorted, that's an implementation detail that you shouldn't rely on. The most efficient implementation for a hash_map does not sort the data, though conscientious implementors may add that feature for your convenience. You would be better off assuming that it isn't sorted than trying to prove that it is an having non-portable code that relies on that knowledge.

Though you can prove that it's sorted if you know about the implementation. :) Check your headers and see what you can find, then you can do some sneaky stuff to get access to the internal table and walk through it from beginning to end to see if every element in sequence is less than the next element.

[winbatch]

Dogtree,

Thanks for the explanation. I was hoping to not force the user to know that I was using map or hash_map (which is why I wouldn't like the line:

MapWrap<std::map<int, int> > wrap1;

I think what I'll do is use a hash_map, but have my constructor accept a bool that indicates that the user wants it sorted. If so, then whenever I provide the contents of the hash_map, I'll sort it prior to returning it. If they don't want it sorted, I won't. Does that make sense?

[Dogtree]

>> I was hoping to not force the user to know that I was using map or hash_map
That's dangerous since the operations of a map and typical hash_map implementations are wildly different. If you're going to go the hidden implementation route, you need to specify an interface in your wrapper that conforms to both the map and hash_map. Otherwise you'll just confuse the users of your class when a bool changes everything in seemingly unpredictable ways.

I think a strong separation between a sorted map and an unsorted map is a good one, and I personally would consider a wrapper for both to be a design flaw. Then there's the question of how much you want to hide from your users at the cost of flexibility?

[winbatch]

Maybe I should explain what I'm doing - I have a class that pretty closely matches that of 'Properties' in Java. You setProperties, getProperties, etc. You can also iterate through the list of properties, as well as load the properties with a file.

Currently, my implementation of my Properties class is to use map. However, since it always sorts it, I wanted to give the user of the class to specify whether it was stored sorted or not. The 'user' doesn't care whether it uses hash_map, map, or even two vectors.

[Dogtree]

Why even bother? A hash_map has better performance properties, so it makes sense to choose it over a map. If the user needs something sorted, they can list to a stringstream, then to a vector, then sort it themselves at only minor cost. You're talking about having detrimental performance for everything to support a convenience that probably wouldn't be used often enough to justify it.

[winbatch]

The only reason why I would want to use map is that as you stated previously, hash_map is not part of the standard and therefore my code might not compile on all platforms without a lot of work. (ie a lot of #ifdef's, etc)

[Dogtree]

This is a classic trade-off, and unfortunately, one that only you can decide.