STL Map Question

[gstercken]

Originally posted by raul_figous
If u see CMap of mfc, they use heap to implement it and it is really good. Do u have any comments on this?

MFC's CMap doesn't implement a heap, but a hash table. Honestly, I never understood why STL's std::map uses a red/black tree instead of a hash table (which is far more efficient in lookup).

[raul_figous]

Hi

Sorry CMap supports hashtable not heap. I typed it wrong. I think it is probably because of the hash function which is really specific to the problem handled. It may be probably because of collisions. What do u guys think?

raul
(spain)

[Yves M]

Originally posted by gstercken
MFC's CMap doesn't implement a heap, but a hash table. Honestly, I never understood why STL's std::map uses a red/black tree instead of a hash table (which is far more efficient in lookup).

The reason is that std::map is sorted, and using a hashed container will not let you do this without incurring serious penalties.

From CMap's documentation
A variable of type POSITION is used for alternate access to entries. You can use a POSITION to “remember” an entry and to iterate through the map. You might think that this iteration is sequential by key value; it is not. The sequence of retrieved elements is indeterminate.

If you don't need it to be sorted, then hash_map is definitely a better choice, especially if it grows large. However, also with hash_map, you should consider a custom allocator for large data sets. Anyways, you may consider using a combination of things anyways, depending on your usage scenario. If you need to access elements using sorted keys only very occasionally, you could for example store everything in a hash_map and then when sorted access is required dump this to a vector which you sort afterwards. Or keep updating the vector as you go along. Or maybe keep an std::map along with your hash_map along these lines:

// For STLPort
#include <map>
#include <hash_map>

template <class Key, class Value, class HashFcn>
class IndexedHashMap {
  typdef std::hash_map<Key, Value, HashFcn> STORAGE_TYPE;
  typdef std::map<Key, Value>  INDEX_TYPE;
  INDEX_TYPE m_index;
  STORAGE_TYPE m_storage;
public:
  typedef INDEX_TYPE::iterator iterator;
  typedef INDEX_TYPE::const_iterator const_iterator;
  Value &operator[](const Key &k)
  {
    // check whether element exists
    if ((STORAGE_TYPE::iterator it = m_storage.find(k)) != m_storage.end()) {
      // lookup is O(1) here
      return *it;
    } else {
      // insertion is O(log(N))
      Value v;
      m_storage.insert(make_pair(k, v));
      m_index.insert(make_pair(k, v));
      return v;
    }
  }
  iterator begin()
  {
    return m_index.begin();
  }
  iterator end()
  {
    return m_index.end();
  }
};

Current hash_map implementations differ (I know the ones from STLPort and Dinkumware) in the details and some runtime characteristics, but they are both better than MFC's CMap.

[fransn]

formerly posted by Kuphryn:
----------------------------------------------------------------------------------
I have seen a system running WinXP with 386mb RAM terminate a program after it had used up 100mb RAM via STL map of strings.

Kuphryn
---------------------------------------------------------------------------------

That has nothing to do with std::map.
If you make your pagefile size 1 or 2 gB you can go a lot further with std::map.
I just stepped into the code and unfortunately map does allocate all its memory with 'new', otherwise you could draw the memory straight from a memorymappedfile of your own.

[raul_figous]

Hi guys,

How does this map sort when we alpha numeric as keys? Like for instance i have

A1
A2
A10
A01
A02

Do we have any algorithm where these alpha numeric values can be converted to a number and then used in map as key values so that they can be sorted properly. As u know the alpha numeric values given above cannot be sorted properly.This sequence could change according to user requirement. Like for a user A10 is less than A2 .Probably this may not be the case with other users. Any inputs on this?

raul
(spain)

[Yves M]

It depends on your comparison function. If you are using map<string, string> then the default comparison function will be less<string>. So it's a lexicographical comparison (i.e. simple string comparison) and your odering will look like this:

A01
A02
A1
A10
A2

If thats' not what you want, then define your own comparison function along these lines:

#include <map>

using namespace std;
struct StringCompare
{
  bool operator()(const &string l, const string &r) const {
    return l < r;
  }
};

int main()
{
  map<string, string, StringCompare> my_map;
  return 0;
}