STL Map Question - Page 2
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 2 of 2 FirstFirst 12
Results 16 to 21 of 21

Thread: STL Map Question

  1. #16
    Join Date
    Sep 2002
    Location
    14° 39'19.65"N / 121° 1'44.34"E
    Posts
    9,815
    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).

  2. #17
    Join Date
    Nov 2003
    Posts
    41
    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)

  3. #18
    Join Date
    Aug 2002
    Location
    Madrid
    Posts
    4,588
    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:
    Code:
    // 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.
    Last edited by Yves M; November 13th, 2003 at 02:09 PM.
    Get this small utility to do basic syntax highlighting in vBulletin forums (like Codeguru) easily.
    Supports C++ and VB out of the box, but can be configured for other languages.

  4. #19
    Join Date
    Jul 2001
    Location
    Netherlands
    Posts
    751
    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.
    Last edited by fransn; November 15th, 2003 at 07:10 PM.

  5. #20
    Join Date
    Nov 2003
    Posts
    41
    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)

  6. #21
    Join Date
    Aug 2002
    Location
    Madrid
    Posts
    4,588
    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:

    Code:
    A01
    A02
    A1
    A10
    A2
    If thats' not what you want, then define your own comparison function along these lines:

    Code:
    #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;
    }
    Last edited by Yves M; November 17th, 2003 at 08:06 AM.
    Get this small utility to do basic syntax highlighting in vBulletin forums (like Codeguru) easily.
    Supports C++ and VB out of the box, but can be configured for other languages.

Page 2 of 2 FirstFirst 12

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center