STL Map Question

Does anyone know about STL maps? I dont find any replies so far.
Please help me out.

raul
(spain)

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)

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.

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.

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:a == b
is the same as
!(a < b) && !(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):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;
Since less is defined for the std::string class, you can safely use it as a key in a map.
Viggy

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)

Yves,

Correct.

Kuphryn

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).

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.

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)