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

H

He Shiming

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

KPB

He said:
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
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
 
V

Victor Bazarov

He said:
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
 
H

He Shiming

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

Victor Bazarov

He said:
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
 
J

Jonathan Mcdougall

He said:
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
 
?

=?iso-8859-1?B?Sm9hcXXtbiBNIEzzcGV6IE118W96?=

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
 
H

He Shiming

Thanks, I'll check that out.

--
He Shiming

Joaquín M López Muñoz said:
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
 
S

Stephen Howe

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 said:
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,
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,480
Members
44,900
Latest member
Nell636132

Latest Threads

Top