Thread: Is is possible to specify the ordering of a std::map ?

  1. #1
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657

    Is is possible to specify the ordering of a std::map ?

    From the reference, it seems that they try to be automatically sorted...(they called it weak ordering)

    What happens when the compiler does not know how to sort the data it contains ?

    Can I rely on the order I specified on the initializer list ?

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    What happens when the compiler does not know how to sort the data it contains ?
    It'll fail to compile. Either the type itself supports the necessary comparison, or you pass in a comparison object that knows what to do.
    My best code is written with the delete key.

  3. #3
    Registered User
    Join Date
    May 2011
    Location
    Around 8.3 light-minutes from the Sun
    Posts
    1,949
    You can specifier your own compare function, if that is what you are asking. See: map constructor.
    Quote Originally Posted by anduril462 View Post
    Now, please, for the love of all things good and holy, think about what you're doing! Don't just run around willy-nilly, coding like a drunk two-year-old....
    Quote Originally Posted by quzah View Post
    ..... Just don't be surprised when I say you aren't using standard C anymore, and as such,are off in your own little universe that I will completely disregard.
    Warning: Some or all of my posted code may be non-standard and as such should not be used and in no case looked at.

  4. #4
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    Quote Originally Posted by Prelude View Post
    It'll fail to compile. Either the type itself supports the necessary comparison, or you pass in a comparison object that knows what to do.
    I was wondering why my example(below) was compiling when I found out that std::string `s do support some comparison.
    //Located outside any function block in a .cpp file
    Code:
    std::map<std::string,Operator> op_ini_map=
    {
            {std::string("+"),plus},
            {std::string("-"),minus},
            {std::string("*"),mult},
            {std::string("/"),divide}
    };
    //..where plus, minus... etc are objects of a class Operator;

    So, my question would better be...
    Is there a way to override the sorting and preserve the ordering I put in the initializer list ?

  5. #5
    Registered User
    Join Date
    May 2011
    Location
    Around 8.3 light-minutes from the Sun
    Posts
    1,949
    Quote Originally Posted by manasij7479 View Post
    I was wondering why my example(below) was compiling when I found out that std::string `s do support some comparison.
    Yes, it is part of std::string. That's why you can do string1==string2 in c++.


    Quote Originally Posted by manasij7479 View Post
    So, my question would better be...
    Is there a way to override the sorting and preserve the ordering I put in the initializer list ?
    Yes, override the default comparison by making your own function as both Prelude and I said. Look at the link I posted.
    Quote Originally Posted by anduril462 View Post
    Now, please, for the love of all things good and holy, think about what you're doing! Don't just run around willy-nilly, coding like a drunk two-year-old....
    Quote Originally Posted by quzah View Post
    ..... Just don't be surprised when I say you aren't using standard C anymore, and as such,are off in your own little universe that I will completely disregard.
    Warning: Some or all of my posted code may be non-standard and as such should not be used and in no case looked at.

  6. #6
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    Is there a way to override the sorting and preserve the ordering I put in the initializer list ?
    If you want to preserve the ordering of the initialization list (ie. an arbitrary order), why are you using a map?
    My best code is written with the delete key.

  7. #7
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    Quote Originally Posted by Prelude View Post
    If you want to preserve the ordering of the initialization list (ie. an arbitrary order), why are you using a map?
    Because I need to map some strings(Here operators) the user would be allowed to input to some pre-created objects so that the constructor would not be needed to create new ones.
    I did what I needed manually with some 30 lines of code(setting the precedences), but the ordering would have made it possible to make a loop for that.

  8. #8
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    Bolding "map" and "to" doesn't change the fact that you're probably using the wrong data structure. std::map is basically just a balanced binary search tree. If it were named std::binary_tree instead of std::map, would you still want to use it?
    My best code is written with the delete key.

  9. #9
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    Quote Originally Posted by Prelude View Post
    Bolding "map" and "to" doesn't change the fact that you're probably using the wrong data structure. std::map is basically just a balanced binary search tree. If it were named std::binary_tree instead of std::map, would you still want to use it?
    I didn't know that !
    Can you think of a better data structure that would fit what I need to do ?

  10. #10
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    Why do you need to preserve the order?

    What are the most common ways this container will be used?

    It may be suitable to make a map<string,pair<int,Operator>, or vector<pair<string,Operator> >, or something else depending on your use case. Also If you're writing Operator yourself, the string or index could be a data member instead of using a pair.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  11. #11
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    What are the most common ways this container will be used?
    In general, the program will grab the input, if it is an operator, I figured that having it run through a constructor containing dozens of switch-cases/else-ifs would be a waste when I know there is a limited no. of possibilities. So I defined all the possible operator objects and am using the map to directly assign the address to the Operator* pointers (because the same object for all the cases is okay).

    It may be suitable to make a map<string,pair<int,Operator>, or vector<pair<string,Operator> >, or something else depending on your use case. Also If you're writing Operator yourself, the string or index could be a data member instead of using a pair.
    I'd try the first one tomorrow, but I'm not inclined to use vectors because it may be necessary to make searches occasionally.

    Why do you need to preserve the order?
    I don't actually 'need' to do so.
    But it'd make the task of defining the pre-built objects easier.

  12. #12
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Quote Originally Posted by manasij7479 View Post
    I didn't know that !
    Can you think of a better data structure that would fit what I need to do ?
    Have you considered using a hash table? unordered_map is a hash table type.

  13. #13
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    Quote Originally Posted by whiteflags View Post
    Have you considered using a hash table? unordered_map is a hash table type.
    That would mean no iteration through it.
    But it could potentially alter my design for the better if I can design the whole thing to not need any.

  14. #14
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    Quote Originally Posted by manasij7479 View Post
    In general, the program will grab the input, if it is an operator, I figured that having it run through a constructor containing dozens of switch-cases/else-ifs would be a waste when I know there is a limited no. of possibilities. So I defined all the possible operator objects and am using the map to directly assign the address to the Operator* pointers (because the same object for all the cases is okay).

    I'd try the first one tomorrow, but I'm not inclined to use vectors because it may be necessary to make searches occasionally.
    Yeah, a hash map sound like a good choice for this.

    I don't actually 'need' to do so.
    But it'd make the task of defining the pre-built objects easier.
    How? Can this be done with a separate container?
    Last edited by King Mir; 08-23-2011 at 04:17 PM.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  15. #15
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    Quote Originally Posted by King Mir View Post
    How?
    If I make an initialization function for the operators, and have the Operators arranged in order of precedence, I could set the value of the precedence with a loop instead of by hand.
    It could also make the task of inserting new Operators later easier.

    But thinking on it for some time, I do realize that it'd be much more complicated that simply running a loop. So I'd go with the manual approach I've already coded.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. ordering characters
    By 12thman in forum C Programming
    Replies: 3
    Last Post: 11-02-2010, 07:15 AM
  2. key ordering in map
    By m37h0d in forum C++ Programming
    Replies: 4
    Last Post: 04-07-2008, 08:28 AM
  3. ListView ordering
    By kidburla in forum Windows Programming
    Replies: 2
    Last Post: 10-16-2006, 03:48 PM
  4. Ordering Queue
    By Japatron in forum C Programming
    Replies: 3
    Last Post: 05-09-2006, 06:51 PM
  5. Ordering names
    By unixOZ in forum C Programming
    Replies: 1
    Last Post: 11-06-2002, 05:54 PM