-
November 13th, 2003, 01:20 PM
#16
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).
-
November 13th, 2003, 01:36 PM
#17
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)
-
November 13th, 2003, 01:53 PM
#18
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.
-
November 15th, 2003, 12:43 PM
#19
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.
-
November 16th, 2003, 01:35 PM
#20
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)
-
November 16th, 2003, 04:49 PM
#21
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:
#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.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|