The Design of Software (CLOSED)

A public forum for discussing the design of software, from the user interface to the code architecture. Now closed.

The "Design of Software" discussion group has been merged with the main Joel on Software discussion group.

The archives will remain online indefinitely.

hash_map question

How could I create a "key equality predicate" for hash_map such that it keeps the elements in the order of insertion? The default rearranges the items from smallest to greatest etc.

Is this possible?
coder
Monday, February 05, 2007
 
 
> Is this possible?

Not by just manipulating the key compare methods - the purpose of the associative containers like hash_map / map / set is to use some method to organize your entities so that you can do an efficient retrieval of that item later on.

The efficient retrieval mechanism will not in general be compatible with keeping objects in your initial insertion order.

But you can use other methods than trying to mess with the key compare for this - for example store an extra integer for original order in the hash_map entry along with the object.
Michael G
Monday, February 05, 2007
 
 
Auxiliary the map, you could store a list of the keys in the order in which the keys were inserted into the map.
Christopher Wells Send private email
Monday, February 05, 2007
 
 
Cymen
Monday, February 05, 2007
 
 
> Auxiliary the map, you could store a list of the keys in
> the order in which the keys were inserted into the map.

You mean, in addition to the hash_map, create a vector to hold the keys and insert them in the order they should appear?
coder
Monday, February 05, 2007
 
 
Yes; or in a list or deque or something.

Beware that removing an item could be expensive, if you don't where to find it in the auxiliary collection, or if removing from the middle the auxiliary collection is expensive.

For that reason, it might be good if the auxiliary collection were of type list<Key>, and also if the map stored not only the value but also the iterator into the list. For example, I think that all of the following operations are cheap (i.e. O(1) if you're using a hash_map rather than a map):

typdef list<Key> List;
typedef pair<Value,List::iterator> Pair;
typdef map<Key,Pair> Map;
List m_list;
Map m_map;

void insert(Key key,Value value)
{
 if (m_map.find(key) != m_map.end())
 {
  item already exists in map: what do you want to do about that?
  return;
 }
 //else add this new key+value item to both containers
 m_list.push_back(key);
 List::iterator list_it = m_list.back();
 m_map.insert(Map::value_type(key,Pair(value,list_it));
}

void delete(Key key)
{
 Map::iterator map_it = m_map.find(key);
 if (map_it == m_map.end())
 {
  //item not found
  return;
 }
 Pair& p = map_it->second;
 List::iterator& list_it = p.second;
 m_list.remove(list_it);
 m_map.remove(map_it);
}
Christopher Wells Send private email
Monday, February 05, 2007
 
 
Looks like boost::multi_index_container can do what you want, if you're using C++.
http://www.boost.org/libs/multi_index/doc/index.html

I haven't used it myself, so I can't give it an unconditional recommendation or point to any caveats.
Mark Ransom Send private email
Tuesday, February 06, 2007
 
 
Thank you guys!
coder
Tuesday, February 06, 2007
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz