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

Thread: STL Map Question

  1. #1
    Join Date
    Nov 2003
    Posts
    41

    STL Map Question

    Hi gus,

    Can anyone give an estimate figure how much value STL map can hold. The max_size that it occupies in the memory? Can anyone give a sample example for this where maximum value is stored and tested for benchmark? Also what is the complexity for inserting, deleting and searching when using maps?


    raul
    (spain)

  2. #2
    Join Date
    Nov 2003
    Posts
    41
    Does anyone know about STL maps? I dont find any replies so far.
    Please help me out.

    raul
    (spain)

  3. #3
    Join Date
    Jul 2001
    Location
    Netherlands
    Posts
    751
    In first instance a map allocates its contents on the stack. But if you allocate your elements on the heap the bulk will be on the heap and only limited by your machine.
    an example would be SQL server: every index underneath is stored in a map.
    maps like all stl structures are very convenient in their use.
    But look outside MSDN for examples, because MS is pushing their mess-alternatives instead.

  4. #4
    Join Date
    Nov 2003
    Posts
    41
    But i have written a code to find out the max_size of the map and i was expecting that all the outputs will be 4294967295. But only for map<char,char> i got this size. Rest I got only 1073741823. Why so? My code is given here:

    //////////////////////////////////////code///////////////////////////////
    #include <iostream>
    #include <map>
    using namespace std;

    int main()
    {
    map<int, int> m_container1;
    map<char, int> m_container2;
    map<char, char> m_container3;
    map<char, long> m_container4;
    map<int, long> m_container5;
    map<long, long> m_container6;

    map<int, int>::size_type max1 = m_container1.max_size();
    map<char, int>::size_type max2 = m_container2.max_size();

    cout << endl << "max size of map<int, int>: " << max1;
    cout << endl << "max size of map<char, int>: " << max2;
    cout << endl << "max size of map<char, char>: "
    << m_container3.max_size();
    cout << endl << "max size of map<char, long>: "
    << m_container4.max_size();
    cout << endl << "max size of map<int, long>: "
    << m_container5.max_size();
    cout << endl << "max size of map<long, long>: "
    << m_container6.max_size();

    return 0;
    }


    And what about the complexity. Is O(logN) for all operations?

    raul
    (spain)

  5. #5
    Join Date
    Feb 2002
    Posts
    5,758
    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

  6. #6
    Join Date
    Sep 2003
    Location
    Forever Gone... For Now...
    Posts
    1,515
    Originally posted by raul_figous
    But i have written a code to find out the max_size of the map and i was expecting that all the outputs will be 4294967295. But only for map<char,char> i got this size. Rest I got only 1073741823.
    1073741823 * 4 (assuming "Rest" is a 32-bit value) = 4294967292.
    Thought for the day/week/month/year:
    Windows System Error 4006:
    Replication with a nonconfigured partner is not allowed.

  7. #7
    Join Date
    Nov 2003
    Posts
    41
    I agree with 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.
    ////////////////////////////////////////////////////////////

    Even in my system, the STL map is getting destroyed(means access violation) after some point. Also when i use the key value as a string, how is the uniqueness is maintained?I may use a small letter 'a' and later a 'A" .How does it do?

    So what u guys want to say is that size depends on individual system and a minimum of 100,000 records are possible in maps , right?

    raul
    (spain)

  8. #8
    Join Date
    Aug 2000
    Location
    West Virginia
    Posts
    7,568
    And what about the complexity. Is O(logN) for all operations?
    yes, find() , insert() , erase() and some other member functions
    are O(logN)

    Also when i use the key value as a string, how is the uniqueness is maintained?I may use a small letter 'a' and later a 'A" .How does it do?
    It merely checks the key for equality. So if the key is a std::string,
    "A" is not equal to "a" (using the default compare function),
    so they will be different elements in the map.

  9. #9
    Join Date
    Sep 2003
    Location
    Forever Gone... For Now...
    Posts
    1,515
    Originally posted by raul_figous
    So what u guys want to say is that size depends on individual system and a minimum of 100,000 records are possible in maps , right?
    I would venture:

    -"size" (in terms of memory used by the map) depends on the system - how much virtual memory is available - a process can have a max of about 2 GB.
    -"size" (in terms of the number of elements the map can hold) depends on the size of the items stored in the map.
    Thought for the day/week/month/year:
    Windows System Error 4006:
    Replication with a nonconfigured partner is not allowed.

  10. #10
    Join Date
    Feb 2002
    Posts
    4,640
    Maps use the binary predicate 'less' to determine order and equality. You can override this when you declare your map, but most of the time there's no need to. Technically, maps do not use the '==' operator, they use '<'. Two items are equal if they are not less than each other:
    PHP Code:
    == b
    is the same 
    as
    !(
    b) && !(a
    Also, you can have a multi-map, which allows for duplicate keys. Otherwise, if the key already exists in the map, and you are assigning a value to that key, the original value will be overwritten. Note that there is no warning that this will happen (as the system won't actually know, until runtime):
    PHP Code:
    std::map<intcharmyMap;
    myMap[1] = 'a';
    myMap[2] = 'b';
    myMap[1] = 'c';
    // The following will output a 'c' to the console
    std::cout << myMap[1] << std::end
    Since less is defined for the std::string class, you can safely use it as a key in a map.
    Viggy

  11. #11
    Join Date
    Aug 2002
    Location
    Madrid
    Posts
    4,588
    Originally 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
    The problem is most likely the very heavy memory fragmentation that comes with the use of the default memory allocator. Also, of course, one must not forget that per node, a map has to allocate other data as well. Usually there are at least three addidtional pointers in a mapnode: left child, right child and parent. Allocating a lot of small objects is bound to cause problems sooner or later with the default allocator.

    So if you expect your map to grow large, consider using a custom allocator. Boost has a few examples, but anyways, for specific cases they are usually not too hard to design.

    Also, I would really consider moving to a different data structure for data this size. A hash_map is a good intermediade candidate (available in most STL implementations), but more specialize structires may be more appropriate.
    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.

  12. #12
    Join Date
    Nov 2003
    Posts
    41
    Thanks mate,

    But in my case, the number of data to be stored is more as well the search is going to be vital.I think SGI supports hash_map but the negative point is it does not support sorting of keys. Only map does that. So you say that data around 100,000 used in map is bound to face trouble?But some sites say that memory space available in your machine is the limit for map.

    Also u have mentioned about allocators. Can u please mention it in detail or with a sample so that i can understand it better?

    raul
    (spain)

  13. #13
    Join Date
    Aug 2002
    Location
    Madrid
    Posts
    4,588
    If you need it to be sorted, then yes, std::map is pretty much the only option.

    Custom allocators are not *that* easy, so I can't write an example off the top of my head, but there is a good example in boost's pool library. It will definitely help with memory fragmentation if you use a custom allocator, but how you design it depends very much on your usage scenario.

    But some sites say that memory space available in your machine is the limit for map.
    Yes, in theory that's true, in practice you may run into other problems first.

    Why do you need that many elements in the map ? Why does it have to be sorted ? Are you inserting / deleting elements during operation or is it rather a fixed structure ?

    P.S. With 100.000 elements, you might still find std::map to be OK, but of course the problem is that deleting the whole data in one go is bound to be horribly slow (that's because of the allocator).
    Last edited by Yves M; November 13th, 2003 at 07:09 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.

  14. #14
    Join Date
    Feb 2002
    Posts
    5,758
    Yves,

    Correct.

    Kuphryn

  15. #15
    Join Date
    Nov 2003
    Posts
    41
    Hi yves,

    Thanks for that info. But why did the STL developers developed map using red and black tree and not with heap. I know they have a seperate heap_map structure implemented in heap. But they could have gone only with heap which is really efficient in many ways. If u see CMap of mfc, they use heap to implement it and it is really good. Do u have any comments on this?

    raul
    (spain)

Page 1 of 2 12 LastLast

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