Printable View
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)
Does anyone know about STL maps? I dont find any replies so far.
Please help me out.
raul
(spain)
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.
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)
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
1073741823 * 4 (assuming "Rest" is a 32-bit value) = 4294967292.Quote:
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.
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)
yes, find() , insert() , erase() and some other member functionsQuote:
And what about the complexity. Is O(logN) for all operations?
are O(logN)
It merely checks the key for equality. So if the key is a std::string,Quote:
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?
"A" is not equal to "a" (using the default compare function),
so they will be different elements in the map.
I would venture:Quote:
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?
-"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.
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: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:a == b
is the same as
!(a < b) && !(b < a)
Since less is defined for the std::string class, you can safely use it as a key in a map.PHP Code:std::map<int, char> myMap;
myMap[1] = 'a';
myMap[2] = 'b';
myMap[1] = 'c';
// The following will output a 'c' to the console
std::cout << myMap[1] << std::end;
Viggy
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.Quote:
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
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.
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)
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.
Yes, in theory that's true, in practice you may run into other problems first.Quote:
But some sites say that memory space available in your machine is the limit for map.
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).
Yves,
Correct.
Kuphryn
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)
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).Quote:
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?
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)
The reason is that std::map is sorted, and using a hashed container will not let you do this without incurring serious penalties.Quote:
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).
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:Quote:
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.
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.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();
}
};
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.
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)
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:
If thats' not what you want, then define your own comparison function along these lines:Code:A01
A02
A1
A10
A2
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;
}