map<wstring, set<wstring> > preserving insertion order?

Discussion in 'C++' started by He Shiming, Dec 30, 2004.

  1. He Shiming

    He Shiming Guest

    Hi Folks,

    I've been using map<wstring, set<wstring> > to manage the internal
    string-value pairs in my program. Lately, I discovered that the set<wstring>
    doesn't preserve the insertion order when I try to fetch values. Here is
    what I do to push values into the map:

    for (...) { // inserting wstring values in a predefined order
    mymap[L"Field"].insert(L"Stuff");
    }

    And I'm trying to read out values by:

    set<wstring> sszwContent = mymap[L"Field"];
    set<wstring>::const_iterator si;
    for(si = sszwContent.begin(); si!=sszwContent.end(); ++si)
    ;// output "si" as a wstring

    It's wierd that the order of output got messed up and it appears that the
    output order isn't really random. But it's just not the insertion order I
    wanted. How can I keep the insertion order in this scenario? Or is it me
    who's messed up the order somewhere else?

    Thanks and best wishes,
    --
    He Shiming
    He Shiming, Dec 30, 2004
    #1
    1. Advertising

  2. He Shiming

    KPB Guest

    He Shiming wrote:
    > Hi Folks,
    >
    > I've been using map<wstring, set<wstring> > to manage the internal
    > string-value pairs in my program. Lately, I discovered that the set<wstring>
    > doesn't preserve the insertion order when I try to fetch values. Here is
    > what I do to push values into the map:


    std::set<> is not designed to preserve insertion order. It's designed to
    keep its elements ordered relative to each other. Look at the
    documentation for std::set<> and you'll see that the second template
    parameter is a predicate. This predicate value (which is set to
    std::less<your type> by default) is used to order the elements as
    they're inserted.

    > It's wierd that the order of output got messed up and it appears that the
    > output order isn't really random. But it's just not the insertion order I
    > wanted. How can I keep the insertion order in this scenario? Or is it me
    > who's messed up the order somewhere else?


    If you want to maintain the insertion order, you have to use another
    container. std::queue, std::list, and to smaller extents: std::vector or
    std::deque would suit your needs better.

    HTH,
    KPB
    KPB, Dec 30, 2004
    #2
    1. Advertising

  3. He Shiming wrote:
    > I've been using map<wstring, set<wstring> > to manage the internal
    > string-value pairs in my program. Lately, I discovered that the set<wstring>
    > doesn't preserve the insertion order when I try to fetch values.


    Well, 'set' is not designed to preserve the order. You need 'list' for
    that or 'vector' or 'deque' or any other _sequential_ container.

    > Here is
    > what I do to push values into the map:
    >
    > for (...) { // inserting wstring values in a predefined order
    > mymap[L"Field"].insert(L"Stuff");
    > }
    >
    > And I'm trying to read out values by:
    >
    > set<wstring> sszwContent = mymap[L"Field"];
    > set<wstring>::const_iterator si;
    > for(si = sszwContent.begin(); si!=sszwContent.end(); ++si)
    > ;// output "si" as a wstring
    >
    > It's wierd that the order of output got messed up and it appears that the
    > output order isn't really random. But it's just not the insertion order I
    > wanted. How can I keep the insertion order in this scenario? Or is it me
    > who's messed up the order somewhere else?


    No, a 'set<value>' is essentially a 'map<value,value>'. It is sorted by
    the stored values themselves to speed up retrieval.

    If you need both quick retrieval _and_ insertion order preserved, there is
    no such standard container. You _could_ store things in a set for quick
    access _and_ store iterators into that set in a list for the order.

    V
    Victor Bazarov, Dec 30, 2004
    #3
  4. He Shiming

    He Shiming Guest

    Hi, thank you both for the answer. But, the reason why I'm using std::set
    here is because it need to avoid duplicated values. And actual concept of
    this string-value pair is "a collection (set) of values". I'm afraid that if
    I go with std::list or std::vector, I'll need to do a lot of extra
    duplication-check. Does deque have an internal optimization on it? Or is
    there any other suggestions?

    --
    He Shiming

    "He Shiming" <mailbill(NOSPAM)@21cn.com.nospam> wrote in message
    news:...
    > Hi Folks,
    >
    > I've been using map<wstring, set<wstring> > to manage the internal
    > string-value pairs in my program. Lately, I discovered that the
    > set<wstring> doesn't preserve the insertion order when I try to fetch
    > values. Here is what I do to push values into the map:
    >
    > for (...) { // inserting wstring values in a predefined order
    > mymap[L"Field"].insert(L"Stuff");
    > }
    >
    > And I'm trying to read out values by:
    >
    > set<wstring> sszwContent = mymap[L"Field"];
    > set<wstring>::const_iterator si;
    > for(si = sszwContent.begin(); si!=sszwContent.end(); ++si)
    > ;// output "si" as a wstring
    >
    > It's wierd that the order of output got messed up and it appears that the
    > output order isn't really random. But it's just not the insertion order I
    > wanted. How can I keep the insertion order in this scenario? Or is it me
    > who's messed up the order somewhere else?
    >
    > Thanks and best wishes,
    > --
    > He Shiming
    >
    >
    He Shiming, Dec 30, 2004
    #4
  5. He Shiming wrote:
    > Hi, thank you both for the answer. But, the reason why I'm using std::set
    > here is because it need to avoid duplicated values. And actual concept of
    > this string-value pair is "a collection (set) of values". I'm afraid that if
    > I go with std::list or std::vector, I'll need to do a lot of extra
    > duplication-check. Does deque have an internal optimization on it? Or is
    > there any other suggestions?
    >


    I am not sure I understand your hesitation to use 'list' or 'vector' to
    _supplement_ 'set':

    std::set<whatever> set_of_whatever;
    std::list<std::set<whatever>::iterator> order_of_insertion;

    std::pair<std::set<whatever>::iterator,bool> done =
    set_of_whatever.insert(a_whatever);

    if (done.second) // if insertion occurred
    order_of_insertion.push_back(done.first); // store the location

    std::set::insert returns a value, you should take advantage of that.

    Victor
    Victor Bazarov, Dec 30, 2004
    #5
  6. He Shiming wrote:
    > Hi, thank you both for the answer. But, the reason why I'm using std::set
    > here is because it need to avoid duplicated values. And actual concept of
    > this string-value pair is "a collection (set) of values". I'm afraid that if
    > I go with std::list or std::vector, I'll need to do a lot of extra
    > duplication-check.


    Only when adding something in it.

    You don't seem to understand the data structures.
    For a collection to avoid duplicated values, it
    must either have a structure which does that by
    essence (such as a tree) or check all the values
    before inserting. You can't have a binary tree
    that preserves the insertion order, that would
    make no sense.

    > Does deque have an internal optimization on it?


    It is usually implemented as an array of arrays
    for fast inserts at the end and at the beginning.
    Inserting/removing in the middle is slow.

    > Or is
    > there any other suggestions?


    If you need to preserve the insertion order, you
    need a sequential collection, such as std::list.
    If you then need to prevent duplicates, you need
    to check it by hand.

    You could also use two containers. The first one
    would be a set or a map for fast lookups and to
    avoid duplicates and the second one would be
    sequential, like a list or vector to store
    iterators of the set. The thing is, that's
    complicated to manage because the tree will change
    its structure while you add elements and you need
    to synchronize the iterators.

    I would recommend a std::list with manual checking.

    Jonathan
    Jonathan Mcdougall, Dec 30, 2004
    #6
  7. >You could also use two containers. The first one
    >would be a set or a map for fast lookups and to
    >avoid duplicates and the second one would be
    >sequential, like a list or vector to store
    >iterators of the set. The thing is, that's
    >complicated to manage because the tree will change
    >its structure while you add elements and you need
    >to synchronize the iterators.


    The Boost Multi-index Containers library
    (http://boost.org/libs/multi_index)
    serves this purpose. The particular case of a list-like container
    with duplicates banning can be achieved by combining
    so-called sequenced and ordered indices. Please check the tutorial
    for examples covering this and other cases.
    HTH

    Joaquín M López Muñoz
    Telefónica, Investigación y Desarrollo
    =?iso-8859-1?B?Sm9hcXXtbiBNIEzzcGV6IE118W96?=, Dec 31, 2004
    #7
  8. He Shiming

    He Shiming Guest

    Thanks, I'll check that out.

    --
    He Shiming

    "Joaquín M López Muñoz" <> wrote in message
    news:...
    >You could also use two containers. The first one
    >would be a set or a map for fast lookups and to
    >avoid duplicates and the second one would be
    >sequential, like a list or vector to store
    >iterators of the set. The thing is, that's
    >complicated to manage because the tree will change
    >its structure while you add elements and you need
    >to synchronize the iterators.


    The Boost Multi-index Containers library
    (http://boost.org/libs/multi_index)
    serves this purpose. The particular case of a list-like container
    with duplicates banning can be achieved by combining
    so-called sequenced and ordered indices. Please check the tutorial
    for examples covering this and other cases.
    HTH

    Joaquín M López Muñoz
    Telefónica, Investigación y Desarrollo
    He Shiming, Jan 1, 2005
    #8
  9. He Shiming

    Stephen Howe Guest

    > Hi, thank you both for the answer. But, the reason why I'm using std::set
    > here is because it need to avoid duplicated values.


    Then you are stuffed.

    If you want to preserve insertion order _AND_ avoid duplication of values
    then you want one of
    vector, list, deque. But note the price you pay is you have to search all N
    items to be sure that there is no duplication of value every time you do an
    insert. That is slow when N gets big.

    There is no such thing as container that is fast on insertion, deletion,
    preservation of order, find, random iterators etc.
    You have to decide what is important and work on that basis.
    Sometimes application requirements dictate which container to use. For
    example if you need fast lookup and inserts occur at the start but
    afterwards almost never, then a sorted vector will beat map/set. And if N is
    small, a vector may also win over map/set. But if for the duration of a
    program running, inserts/deletes occur often and N is large, map/set will
    beat vector.

    Stephen Howe









    And actual concept of
    > this string-value pair is "a collection (set) of values". I'm afraid that
    > if I go with std::list or std::vector, I'll need to do a lot of extra
    > duplication-check. Does deque have an internal optimization on it? Or is
    > there any other suggestions?
    >
    > --
    > He Shiming
    >
    > "He Shiming" <mailbill(NOSPAM)@21cn.com.nospam> wrote in message
    > news:...
    >> Hi Folks,
    >>
    >> I've been using map<wstring, set<wstring> > to manage the internal
    >> string-value pairs in my program. Lately, I discovered that the
    >> set<wstring> doesn't preserve the insertion order when I try to fetch
    >> values. Here is what I do to push values into the map:
    >>
    >> for (...) { // inserting wstring values in a predefined order
    >> mymap[L"Field"].insert(L"Stuff");
    >> }
    >>
    >> And I'm trying to read out values by:
    >>
    >> set<wstring> sszwContent = mymap[L"Field"];
    >> set<wstring>::const_iterator si;
    >> for(si = sszwContent.begin(); si!=sszwContent.end(); ++si)
    >> ;// output "si" as a wstring
    >>
    >> It's wierd that the order of output got messed up and it appears that the
    >> output order isn't really random. But it's just not the insertion order I
    >> wanted. How can I keep the insertion order in this scenario? Or is it me
    >> who's messed up the order somewhere else?
    >>
    >> Thanks and best wishes,
    >> --
    >> He Shiming
    >>
    >>

    >
    >
    Stephen Howe, Jan 3, 2005
    #9
    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. TTroy
    Replies:
    16
    Views:
    777
    Peter Nilsson
    Jan 31, 2005
  2. Naveen
    Replies:
    5
    Views:
    367
    Andrey Tarasevich
    Oct 17, 2006
  3. Replies:
    4
    Views:
    498
  4. Mosfet
    Replies:
    6
    Views:
    4,865
  5. Owner
    Replies:
    14
    Views:
    958
Loading...

Share This Page