Thread: Choice of std:: Container

  1. #1
    Confused
    Join Date
    Nov 2002
    Location
    Warwick, UK
    Posts
    209

    Choice of std:: Container

    Hello all,

    I'm trying to pin down the kind of container I need to select, and if there isn't one that works, to determine what I need to write my own that isn't too slow. Here are the requirements :

    - Associative. I need it to work like a std::map in the way it can be used to return some value object based on a unique key object ( keys are unique in this scenario ).
    - Unordered. I don't want the container ordering my pairs based on their keys.
    - end() deletion, begin() insertion. I need to effectively be able to push() onto the end and pop() from the beginning - hence the unordered criterion above.

    I came across unordered_map from C++11, but it's still ordering the objects by key, even when I provide a hint, unless I'm doing it wrong :

    Code:
    unordered_map <int, int> umap;
    
    umap.insert(pair <int, int> (1, 123));
    umap.insert(pair <int, int> (3, 345));
    umap.insert(pair <int, int> (2, 234));
    When I iterate from begin() to end(), my output is
    Code:
    123
    234
    345
    I've also used
    Code:
    umap.insert(umap.end(), pair <int, int> (1, 123));
    as a hint, to no avail.

    Any suggestions would be hugely appreciated. Thank you !
    Last edited by Korhedron; 04-02-2012 at 09:04 AM.

  2. #2
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    (AFAIK) The point of std::unordered_map is that you do not get a reliable order of iteration, but I'm not sure about that.
    (Giving more elements, I see that the results are not sorted w.r.t 'first' )

    How fast do you need search to be ?
    Unless ordered (/ stored down a tree), I think, the best is linear.
    In that case, using std::deque<std::pair<int,int> > internally and making a class wrapping up your functionality would be okay.
    Last edited by manasij7479; 04-02-2012 at 09:22 AM.

  3. #3
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    Here are the requirements
    O_o

    Why?

    I can tell you how to get the behavior you require, but only if you tell me why and what you are trying to do.

    I can't fathom a reality where you need those requirements; they make no sense when you put them together.

    I'm reading "I want a dictionary that has no notion of order while still having some canonical notion of "beginning" and "ending"." and my brain is starting to reject all reality.

    The point of std::unordered_map is that you do not get a reliable order of iteration, but I'm not sue about that.
    That's a side effect.

    The "point" of the horrendously named facility is providing an associative container that has better complexity guarantees over `std::map' when used properly.

    Soma

  4. #4
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Korhedron View Post
    - Associative. I need it to work like a std::map in the way it can be used to return some value object based on a unique key object ( keys are unique in this scenario ).
    - Unordered. I don't want the container ordering my pairs based on their keys.
    It sounds like you mean "in order" (the order you add them in), like a vector, and not "unordered". This is going to be an issue with an associative key-value container, because, eg, the reason std::map orders the keys is not to conveniently sort them for the user; it's to make the associative look-ups efficient -- it is logarithmic, using an in-order tree, and not linear, going thru a list of unordered values. That makes a huge difference esp. if the map is large. And as phantomotap points out, the "unorderedness" of an unordered map just means the order cannot be predicted or relied upon by the user -- they almost certainly are kept in a specific order to maximize the efficiency of look-ups, but that order does not equate to a linear sort. So when you add an element to an unordered_map, it may end up anywhere -- but that spot is not random, it is according to the logic of the underlying implementation (which you should not try to decipher, predict, depend upon, etc).

    If you need to maintain an order not conducive to look-ups, you can either abandon associative containers, use a vector, and just do linear look-ups yourself, or you could combine the two in some kind of class which stores the key-value pairs in a map, but when they are added, also pushes a pointer to the pair onto a vector. The iterator for the class iterates the vector, so the order is preserved, but the [] look-up uses the map. You may want to use a further pair or struct as the map value to keep track of the index in the vector for when an element is deleted.

    If it is important to prevent duplicate keys, using just a vector will also require you to wrap it in a class and iterate every time something is added -- at that point you might as well just use the combined map/vector.
    Last edited by MK27; 04-02-2012 at 10:06 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  5. #5
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    sounds like you mean "in order"
    It is already too late for that!

    My brain was already bruised trying to escape from imaging a "use case" for undirected dictionaries.

    Soma

  6. #6
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    Quote Originally Posted by phantomotap View Post
    imaging a "use case" for undirected dictionaries.
    How about a map of (Author, Book) pairs? [Edit: (Book, Author) actually]
    ...you remove those you've finished reading
    ...and insert those you just bought
    ...and read them in the order they are bought
    Last edited by manasij7479; 04-02-2012 at 10:24 AM.

  7. #7
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    How about a map of (Author, Book) pairs?
    O_o

    That's actually a very clear set of guidelines to form both a queue and a map.

    That's a good case for doing what Mk27 said only using a queue (as you said) instead of a vector.

    [Edit]
    ^_^

    Has anyone noticed that post four keeps getting longer?
    [/Edit]

    Soma

  8. #8
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by phantomotap View Post
    Has anyone noticed that post four keeps getting longer?
    It's forum OCD. I always re-read them to catch mistakes and think, "well you should also point out..."

    That 1 hour edit limit turned out to be a blessing in disguise. I have so much extra free time now, I'm building a sun room over the front deck.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. multiple choice
    By iLike in forum C Programming
    Replies: 6
    Last Post: 10-30-2009, 03:53 PM
  2. Replies: 1
    Last Post: 01-23-2006, 07:12 PM
  3. Language of choice after C++
    By gandalf_bar in forum A Brief History of Cprogramming.com
    Replies: 47
    Last Post: 06-15-2004, 01:20 AM
  4. Replies: 4
    Last Post: 03-21-2004, 03:34 PM
  5. Os of Choice
    By Fordy in forum A Brief History of Cprogramming.com
    Replies: 13
    Last Post: 09-26-2001, 08:27 AM