Equivalent of Java linked hash map (insertion order)

[Mosfet]

Hi,

I am looking for an equivalent of Java linked hash map (Hash table and
linked list implementation of the Map interface, with predictable
iteration order. This implementation differs from HashMap in that it
maintains a doubly-linked list running through all of its entries. This
linked list defines the iteration ordering, which is normally the order
in which keys were inserted into the map (insertion-order). Note that
insertion order is not affected if a key is re-inserted into the map.)

I would like a simple implementation since boost is not a choice for me.

Thanks

 

[jkherciueh]

Hi,

I am looking for an equivalent of Java linked hash map (Hash table and
linked list implementation of the Map interface, with predictable
iteration order. This implementation differs from HashMap in that it
maintains a doubly-linked list running through all of its entries. This
linked list defines the iteration ordering, which is normally the order
in which keys were inserted into the map (insertion-order). Note that
insertion order is not affected if a key is re-inserted into the map.)

I would like a simple implementation since boost is not a choice for me.

Note that std::list has the nice feature that iterators remain valid under
almost all operations. Thus, you could implement that linked map centered
around a pair

std::list< MappedType > the_insertion_order;
std::map< KeyType, std::list<MappedType>::iterator > the_map;

Implementations of inserts, erase, find, and iterators should be straight
forward (with a little twist to meet your requirement about re-inserting a
key not changing the iteration order).


Best

Kai-Uwe Bux

 

[Mosfet]

Thanks a lot and I will use this but I am sure someone has already
developped it.
Actually I am a bit in a hurry.
So if people could share ...




(e-mail address removed) a écrit :

 

[Erik Wikström]

Hi,

I am looking for an equivalent of Java linked hash map (Hash table and
linked list implementation of the Map interface, with predictable
iteration order. This implementation differs from HashMap in that it
maintains a doubly-linked list running through all of its entries. This
linked list defines the iteration ordering, which is normally the order
in which keys were inserted into the map (insertion-order). Note that
insertion order is not affected if a key is re-inserted into the map.)

I would like a simple implementation since boost is not a choice for me.

What is wrong with std::map? While it is not a hash-map it have quite
good performance anyway and it is sorted. Or do you need to be able to
iterate in order of insertion?

 

[jkherciueh]

Thanks a lot and I will use this but I am sure someone has already
developped it.
Actually I am a bit in a hurry.
So if people could share ...

Please don't top post.

(e-mail address removed) a écrit :

If someone has done this before, it wasn't me (as is apparent from my
misguided first answer). The problem is that the key and the value are
stored in different places so that the linked_map would not have iterators
that point to a pair (key,value).


Here is a proof of concept based upon a different idea:


#include <list>
#include <set>
#include <utility>

template < typename KeyType, typename MappedType,
typename Comp = std::less< KeyType > >
struct linked_map {

typedef KeyType key_type;
typedef MappedType mapped_type;
typedef std:air< const key_type, mapped_type > value_type;

private:

typedef std::list< value_type > list_type;
typedef typename list_type::iterator list_iterator;

struct compare_keys {

Comp the_order;

compare_keys ( Comp o )
: the_order ( o )
{}

bool operator() ( list_iterator lhs, list_iterator rhs ) const {
return ( the_order( lhs->first, rhs->first ) );
}

};

typedef std::set< list_iterator, compare_keys > set_type;
typedef typename set_type::iterator set_iterator;

list_type the_list;
set_type the_set;

public:

typedef list_iterator iterator;
typedef typename set_type::size_type size_type;

linked_map ( Comp o = Comp() )
: the_list()
, the_set ( compare_keys( o ) )
{}

iterator find ( key_type const & key ) {
value_type dummy_value ( key, mapped_type() );
list_type dummy_list;
dummy_list.push_back( dummy_value );
set_iterator where = the_set.find( dummy_list.begin() );
if ( where == the_set.end() ) {
return ( the_list.end() );
}
return ( *where );
}

iterator insert ( value_type const & value ) {
list_type dummy;
dummy.push_back( value );
set_iterator where = the_set.find( dummy.begin() );
if ( where == the_set.end() ) {
the_list.push_back( value );
list_iterator pos = the_list.end();
-- pos;
the_set.insert( pos );
return ( pos );
} else {
(*where)->second = value.second;
return ( *where );
}
}

iterator erase ( iterator where ) {
the_set.erase( where );
return ( the_list.erase( where ) );
}

iterator begin ( void ) {
return ( the_list.begin() );
}

iterator end ( void ) {
return ( the_list.end() );
}

size_type size ( void ) const {
return ( the_set.size() );
}

mapped_type & operator[] ( key_type const & key ) {
iterator pos = insert( std::make_pair( key, mapped_type() ) );
return ( pos->second );
}

};


#include <iostream>

int main ( void ) {
linked_map< int, int > lm;
lm[4] = 3;
lm[2] = 1;
lm[5] = 2;
lm[2] = 0;
for ( linked_map<int,int>::iterator iter = lm.begin();
iter != lm.end(); ++iter ) {
std::cout << iter->first << " --> " << iter->second << '\n';
}
}

// end of file

I am sure this can be vastly improved in terms of readability and
performance. But maybe it gives you an idea.


Best

Kai-Uwe Bux

 

[Mosfet]

Erik Wikström a écrit :

What is wrong with std::map? While it is not a hash-map it have quite
good performance anyway and it is sorted. Or do you need to be able to
iterate in order of insertion?

Yes I want to be able to iterate in order of insertion.

 

[Eric.Malenfant]

Thanks a lot and I will use this but I am sure someone has already
developped it.
Actually I am a bit in a hurry.
So if people could share ...

Boost.MultiIndex seems to fit your requirements well.
http://www.boost.org/libs/multi_index/doc/index.html

Even if its as simple as #include-ing headers? IIRC, MultiIndex is a
"headers only" library.