«

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

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

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 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:air<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

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

>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

Thanks, I'll check that out.

--
He Shiming

"Joaquín M López Muñoz" <> wrote in message
news: ups.com...
>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

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