Preserving order of insertion

[Naveen]

I am trying to write a conatiner which has std::map like methods but
preserves the order of insertion.
TO achieve this I thought of providing my own function for comparing
the keys of the map. Following is the sample code for this:

template <class T>
struct my_compare
{
bool operator () (const T&a, const T&b)
{
return false;
}
};

int main()
{
std::map<std::string,int, my_compare<std::string> > a;

std::string str = "1";
a[str] = 1;

str = "3";
a[str] = 3;

str = "2";
a[str] = 2;

str = "5";
a[str] = 5;


int size = a.size();

std::map<std::string,int, my_compare<std::string> > ::iterator iter =
a.begin();
for(; iter != a.end(); ++iter)
{
cout<<iter->first.c_str() <<"\n";
}

return 1;
}

The output of this code is : 1 i.e. there is only one element in the
map. Can somebody explain why ?

If I return true in operator(), the output is 5 2 3 1 (as expected).

I am compiling it using VC 6 compiler.

 

[Kai-Uwe Bux]

I am trying to write a conatiner which has std::map like methods but
preserves the order of insertion.

Try using a map and a vector of iterators into the map. The map does its
thing and after inserting an element into the map, you append its location
to the vector, which then keeps track of the order of insertion. This will
allow you, by adding one level of indirection, to traverse the map in the
order the entries were inserted.

TO achieve this I thought of providing my own function for comparing
the keys of the map. Following is the sample code for this:

template <class T>
struct my_compare
{
bool operator () (const T&a, const T&b)
{
return false;
}
};

int main()
{
std::map<std::string,int, my_compare<std::string> > a;

std::string str = "1";
a[str] = 1;

str = "3";
a[str] = 3;

str = "2";
a[str] = 2;

str = "5";
a[str] = 5;


int size = a.size();

std::map<std::string,int, my_compare<std::string> > ::iterator iter =
a.begin();
for(; iter != a.end(); ++iter)
{
cout<<iter->first.c_str() <<"\n";
}

return 1;
}

The output of this code is : 1 i.e. there is only one element in the
map. Can somebody explain why ?

The map container does not use operator== to check whether entries are
equal. Instead, it relies only upon your comparison predicate comp. Then,
equivalence of keys is defined as follows:

key_a is equivalent to key_b
if and only if
neither comp( key_a, key_b ) nor comp( key_b, key_a )

Your predicate returns always false whence all keys are considered
equivalent. Thus, when you try to insert the second key the map will think
that it already has an entry with an equivalent key.

If I return true in operator(), the output is 5 2 3 1 (as expected).

In this case, all keys will be considered inequivalent, even when you
compare a key to itself. Thus, you should expect WeirdThings(tm) when you
use the same key twice.


[snip]



Best

Kai-Uwe Bux

 

[Michiel.Salters]

I am trying to write a conatiner which has std::map like methods but
preserves the order of insertion.
To achieve this I thought of providing my own function for comparing
the keys of the map. Following is the sample code for this:

That's very complex - push_back on vector/deque/list will also preserve
order of insertion. Which std::map methods would you want?

template <class T>
struct my_compare
{
bool operator () (const T&a, const T&b)
{
return false;
}
};

That says that all T elements are equal. Equality in std::map means
that
compare(a,b) and compare(b,a) are false. Obviously, since you can't
have
duplicates in a map, such a map can store only one item. The second
item
you try to insert will overwrite the first one, since it has the same
key.

int main()
{
std::map<std::string,int, my_compare<std::string> > a;

std::string str = "1";
a[str] = 1;

str = "3";
a[str] = 3;

str = "2";
a[str] = 2;

str = "5";
a[str] = 5;
}

There is only one element in the map. Can somebody explain why ?

Sure: because you said that "1" is not less than "3" and "3" is not
less than
"1". Obviously they are the same key, then.

If I return true in operator(), the output is 5 2 3 1 (as expected).

That means your compiler doesn't double-check your comparison function.
It's not required to. You are required to return false for either
my_compare(a,b)
or my_compare(b,a). A modern compiler can spot this, but typically they
only bother in debug mode. In release mode, they are optimized to
assume
my_compare(b,a) is false if my_compare(a,b) is true.

In your example, you'd get the weird situations that
my_compare("1","1") is
true. I.e. "1" comes before "1" !

If you would want to use any of the map-specific functions, you'll see
they all use
my_compare. operator[ ](x) will return the equality test I described
earlier: find
the key for which my_compare(key,x) and my_compare(x, key) are both
false.

HTH,
Michiel Salters

 

[Kai-Uwe Bux]

Try using a map and a vector of iterators into the map. The map does its
thing and after inserting an element into the map, you append its location
to the vector, which then keeps track of the order of insertion. This will
allow you, by adding one level of indirection, to traverse the map in the
order the entries were inserted.

I should remark that this makes deletions a little costly: you need a linear
search in the vector to find the iterator and remove it. Here is an idea
that should to logarithmic time:

#include <map>
#include <list>
#include <iostream>

template < typename K, typename M >
struct my_map {

typedef std::map<K,M> KM_map;
typedef typename KM_map::value_type value_type;
typedef value_type * pointer;
typedef value_type const * const_pointer;
typedef std::list< pointer > P_list;
typedef std::map< pointer, typename P_list::iterator > P_map;

KM_map the_KM_map;
P_list the_P_list;
P_map the_P_map;


typename KM_map::iterator
insert ( value_type const & value ) {
typename KM_map::iterator iter = the_KM_map.insert( value ).first;
// FIXME: [should use boost::addressof]
pointer ptr = &( *iter );
the_P_list.push_back( ptr );
the_P_map[ ptr ] = -- the_P_list.end();
return ( iter );
}

void erase ( typename KM_map::iterator where ) {
// FIXME: [should use boost::addressof]
pointer ptr = &( *where );
typename P_map::iterator pm_iter = the_P_map.find( ptr );
typename P_list::iterator pl_iter = pm_iter->second;
the_P_list.erase( pl_iter );
the_P_map.erase( pm_iter );
the_KM_map.erase( where );
}

};

typedef my_map<int,int>::KM_map::value_type int_pair;

int main ( void ) {
my_map<int,int> im;
im.insert( int_pair( 4, 5 ) );
im.insert( int_pair( 2, 1 ) );
im.insert( int_pair( 3, 1 ) );
im.erase( im.the_KM_map.find( 2 ) );
for ( my_map<int,int>:_list::const_iterator iter =
im.the_P_list.begin();
iter != im.the_P_list.end(); ++iter ) {
std::cout << (*iter)->first << " " << (*iter)->second << '\n';
}
}

It's just a proof of concept. Hope it helps.


Best

Kai-Uwe Bux

 

[Andrey Tarasevich]

...
The map container does not use operator== to check whether entries are
equal. Instead, it relies only upon your comparison predicate comp. Then,
equivalence of keys is defined as follows:

key_a is equivalent to key_b
if and only if
neither comp( key_a, key_b ) nor comp( key_b, key_a )

Your predicate returns always false whence all keys are considered
equivalent. Thus, when you try to insert the second key the map will think
that it already has an entry with an equivalent key.



In this case, all keys will be considered inequivalent, even when you
compare a key to itself. Thus, you should expect WeirdThings(tm) when you
use the same key twice.
...

(As a side note Strictly speaking, the implementation of an associative
container is free to use the following definition of the equivalence

key_a is equivalent to key_b
if and only if
both !comp( key_a, key_b ) and !comp( key_b, key_a )

which is the same as yours for a correctly defined comparison predicate.

But in this case the _second_ implementation (the one that always returns
'true') will cause all keys to be treated as equivalent, when the first one
(returns 'false') will make them all non-equivalent.

In other words, in general case an incorrectly defined comparison predicate will
always lead to WeirdThings(tm) happening and the first form is not really more
predictable than the second one.

 

[Andrey Tarasevich]

(As a side note Strictly speaking, the implementation of an associative
container is free to use the following definition of the equivalence

key_a is equivalent to key_b
if and only if
both !comp( key_a, key_b ) and !comp( key_b, key_a )

which is the same as yours for a correctly defined comparison predicate.

But in this case the _second_ implementation (the one that always returns
'true') will cause all keys to be treated as equivalent, when the first one
(returns 'false') will make them all non-equivalent.

Oops... Sorry. What I said here just doesn't make any sense. You are right,
there's a certain distinction between the "always false" and "always false"
versions of the predicate.