Preserving order of insertion

Discussion in 'C++' started by Naveen, Oct 17, 2006.

  1. Naveen

    Naveen Guest

    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.
     
    Naveen, Oct 17, 2006
    #1
    1. Advertising

  2. Naveen

    Kai-Uwe Bux Guest

    Naveen wrote:

    > 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
     
    Kai-Uwe Bux, Oct 17, 2006
    #2
    1. Advertising

  3. Naveen

    Guest

    Naveen wrote:
    > 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
     
    , Oct 17, 2006
    #3
  4. Naveen

    Kai-Uwe Bux Guest

    Kai-Uwe Bux wrote:

    > Naveen wrote:
    >
    >> 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.


    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>::p_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
     
    Kai-Uwe Bux, Oct 17, 2006
    #4
  5. Kai-Uwe Bux wrote:
    > ...
    > 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.
    > ...


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

    --
    Best regards,
    Andrey Tarasevich
     
    Andrey Tarasevich, Oct 17, 2006
    #5
  6. Andrey Tarasevich wrote:

    > Kai-Uwe Bux wrote:
    >> ...
    >> 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.
    >> ...

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

    --
    Best regards,
    Andrey Tarasevich
     
    Andrey Tarasevich, Oct 17, 2006
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Dave
    Replies:
    2
    Views:
    366
    tom_usenet
    Oct 27, 2003
  2. He Shiming
    Replies:
    8
    Views:
    4,865
    Stephen Howe
    Jan 3, 2005
  3. TTroy
    Replies:
    16
    Views:
    795
    Peter Nilsson
    Jan 31, 2005
  4. Replies:
    4
    Views:
    536
  5. Owner
    Replies:
    14
    Views:
    991
Loading...

Share This Page