STL map class ordering

Discussion in 'C++' started by evlong, Nov 7, 2006.

  1. evlong

    evlong Guest

    My question is about the STL map class and how it sorts data that it
    stores. By default (as far as I know) it sorts keys in ascending order
    or lexicographically.

    If I were to do something like this:

    ages["z"] = 1;
    ages["a"] = 5;
    ages["x"] = 1;

    for( map<string, int>::iterator iter = ages.begin(); iter !=
    ages.end(); iter++ ) {
    cout << iter->first << " is " << (*iter).second << endl;
    }

    It would output

    a is 5
    x is 1
    z is 1

    Is there a way to tell map not to sort by keys or by value but to leave
    them in the order in which they were created in the list? Or is there a
    way to iterate through a map in the same order they were added to the
    map?

    Thanks in advance.
     
    evlong, Nov 7, 2006
    #1
    1. Advertising

  2. evlong

    Salt_Peter Guest

    evlong wrote:
    > My question is about the STL map class and how it sorts data that it
    > stores. By default (as far as I know) it sorts keys in ascending order
    > or lexicographically.
    >
    > If I were to do something like this:
    >
    > ages["z"] = 1;
    > ages["a"] = 5;
    > ages["x"] = 1;
    >
    > for( map<string, int>::iterator iter = ages.begin(); iter !=
    > ages.end(); iter++ ) {
    > cout << iter->first << " is " << (*iter).second << endl;
    > }
    >
    > It would output
    >
    > a is 5
    > x is 1
    > z is 1
    >
    > Is there a way to tell map not to sort by keys or by value but to leave
    > them in the order in which they were created in the list? Or is there a
    > way to iterate through a map in the same order they were added to the
    > map?
    >
    > Thanks in advance.


    No there isn't. A std::map that ceases to order its elements according
    to its predicate is undefined behaviour. You could use an incrementing
    index key paired with each new element and therefore order the elements
    using their insertion order. What you can't do is defeat the
    container's purpose.

    Which begs the question: why don't you simply use a vector, list or
    deque to store elemennts or std::pairs? Sequenced containers do not
    order using a predicate.
     
    Salt_Peter, Nov 7, 2006
    #2
    1. Advertising

  3. evlong

    Kai-Uwe Bux Guest

    evlong wrote:

    > My question is about the STL map class and how it sorts data that it
    > stores. By default (as far as I know) it sorts keys in ascending order
    > or lexicographically.
    >
    > If I were to do something like this:
    >
    > ages["z"] = 1;
    > ages["a"] = 5;
    > ages["x"] = 1;
    >
    > for( map<string, int>::iterator iter = ages.begin(); iter !=
    > ages.end(); iter++ ) {
    > cout << iter->first << " is " << (*iter).second << endl;
    > }
    >
    > It would output
    >
    > a is 5
    > x is 1
    > z is 1
    >
    > Is there a way to tell map not to sort by keys or by value but to leave
    > them in the order in which they were created in the list?


    No.

    > Or is there a way to iterate through a map in the same order they were
    > added to the map?


    You can play around with the following:

    #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 address_of]
    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 address_of]
    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';
    }
    }


    Of course, this is just a proof of concept. You would need to polish the
    my_map template so that the internals are hidden and so that it presents a
    nice interface.


    Best

    Kai-Uwe Bux
     
    Kai-Uwe Bux, Nov 7, 2006
    #3
  4. evlong

    Ian Collins Guest

    evlong wrote:
    >
    > Is there a way to tell map not to sort by keys or by value but to leave
    > them in the order in which they were created in the list? Or is there a
    > way to iterate through a map in the same order they were added to the
    > map?
    >

    No.

    If you don't want sorted data, why not use a std::vector?

    --
    Ian Collins.
     
    Ian Collins, Nov 7, 2006
    #4
  5. evlong wrote:
    > Is there a way to tell map not to sort by keys or by value but to leave
    > them in the order in which they were created in the list? Or is there a
    > way to iterate through a map in the same order they were added to the
    > map?


    No. If that's what you want, you can use a vector or list of pairs.


    --
    Clark S. Cox III
     
    Clark S. Cox III, Nov 7, 2006
    #5
  6. evlong

    Default User Guest

    Clark S. Cox III wrote:

    > evlong wrote:
    > > Is there a way to tell map not to sort by keys or by value but to
    > > leave them in the order in which they were created in the list? Or
    > > is there a way to iterate through a map in the same order they were
    > > added to the map?

    >
    > No. If that's what you want, you can use a vector or list of pairs.


    That wouldn't really allow you to use it like an associative array,
    which is what I gather the OP is after.





    Brian
     
    Default User, Nov 7, 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. Marcus
    Replies:
    2
    Views:
    593
    Marcus
    Dec 9, 2005
  2. Replies:
    2
    Views:
    556
    klaus hoffmann
    Feb 22, 2006
  3. kl
    Replies:
    7
    Views:
    1,293
    James Kanze
    Jan 1, 2008
  4. nbigaouette

    Z-Ordering (Morton ordering) question

    nbigaouette, Nov 5, 2009, in forum: C Programming
    Replies:
    2
    Views:
    2,172
  5. Luca Risolia

    STL map to STL vector

    Luca Risolia, Jan 13, 2014, in forum: C++
    Replies:
    32
    Views:
    375
    Seungbeom Kim
    Jan 18, 2014
Loading...

Share This Page