Home > Archive > VC STL > March 2006 > STL map order
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
|
|
|
| Is it possible to let the elements in the map keep the inserted order?
| |
| Stephen Howe 2006-03-16, 7:01 pm |
| > Is it possible to let the elements in the map keep the inserted order?
No. To do so would break the map. map always places inserted elements in the
order specified on creation of the map. And it will keep that order until
the map is destroyed. It is how map guarantees its fast lookup of elements
based on key. The same is true for multimap, set, multiset.
If you want to preserve inserted order, you want one of vector, deque or
list and use push_back().
Stephen Howe
| |
|
| I see, thanks. However, i need to lookup
mymap["mykey"]
vector seems not able to implement this.
"Stephen Howe" wrote:
>
> No. To do so would break the map. map always places inserted elements in the
> order specified on creation of the map. And it will keep that order until
> the map is destroyed. It is how map guarantees its fast lookup of elements
> based on key. The same is true for multimap, set, multiset.
>
> If you want to preserve inserted order, you want one of vector, deque or
> list and use push_back().
>
> Stephen Howe
>
>
>
| |
| Igor Tandetnik 2006-03-16, 7:01 pm |
| nick <nick@discussions.microsoft.com> wrote:
> I see, thanks. However, i need to lookup
>
> mymap["mykey"]
>
> vector seems not able to implement this.
Keep all elements twice - once in the map for fast lookup, the second
copy in the vector to preserve insertion order. To avoid two copies, you
can have a vector of iterators into the map (luckily map does not
invalidate iterators when elements are inserted or removed).
--
With best wishes,
Igor Tandetnik
With sufficient thrust, pigs fly just fine. However, this is not
necessarily a good idea. It is hard to be sure where they are going to
land, and it could be dangerous sitting under them as they fly
overhead. -- RFC 1925
| |
| Carl Daniel [VC++ MVP] 2006-03-16, 7:01 pm |
| "nick" <nick@discussions.microsoft.com> wrote in message
news:AFEDCDF1-868D-4C5B-BB71-15360139586A@microsoft.com...
>I see, thanks. However, i need to lookup
>
> mymap["mykey"]
>
> vector seems not able to implement this.
Then you probably need both a map and a vector. You could push
map::iterators into a vector as items are added to the map, or redundantly
store the key in both the vector and the map.
-cd
| |
| Jason Winnebeck 2006-03-16, 7:01 pm |
| In order to search/lookup by key, you will need to sort by that key.
Even if you tried to "hack" the insert order by having it sorted by some
sequential count, you can't look it up that way.
I don't think there is a solution in the STL to do what you need to do.
So I think you have two options:
1. Create a class encapsulates a vector or list and a map and mirrors
the operations in both.
2. Create a new class from scratch that is a mix of a map and a list,
similar to java.util.LinkedHashMap in Java that keeps links to maintain
iteration in insertion order.
Jason
nick wrote:[color=darkred]
> I see, thanks. However, i need to lookup
>
> mymap["mykey"]
>
> vector seems not able to implement this.
>
> "Stephen Howe" wrote:
>
| |
| Ulrich Eckhardt 2006-03-17, 3:58 am |
| nick wrote:
> I see, thanks. However, i need to lookup
>
> mymap["mykey"]
>
> vector seems not able to implement this.
Use a generic search algorithm on an unsorted container like vector, list or
deque:
container::iterator it =
std::find( mymap.begin(), mymap.end(),
first_equals("mykey"));
Uli
| |
| Jerry Coffin 2006-03-17, 3:58 am |
| In article <AFEDCDF1-868D-4C5B-BB71-
15360139586A@microsoft.com>,
nick@discussions.microsoft.com says...
> I see, thanks. However, i need to lookup
>
> mymap["mykey"]
>
> vector seems not able to implement this.
It sounds like you need to access the elements based on
the key AND based on the original insertion.
In this case, I'd consider putting the elements
themselves into a vector. Then create a map of pointers
to the elements that are stored in the vector. To make
that work, you'll have to supply a comparison functor (or
function) to do the comparisons based on what the
pointers refer to rather than comparing the pointers
themselves.
--
Later,
Jerry.
The universe is a figment of its own imagination.
| |
|
|
| Igor Tandetnik 2006-03-17, 7:01 pm |
| Jerry Coffin <jcoffin@taeus.com> wrote:
> In article <AFEDCDF1-868D-4C5B-BB71-
> 15360139586A@microsoft.com>,
> nick@discussions.microsoft.com says...
>
> It sounds like you need to access the elements based on
> the key AND based on the original insertion.
>
> In this case, I'd consider putting the elements
> themselves into a vector. Then create a map of pointers
> to the elements that are stored in the vector.
Bad idea, unless the vector is read-only after being populated. Pointers
or iterators into the vector tend to become invalid when you insert or
erase any element.
--
With best wishes,
Igor Tandetnik
With sufficient thrust, pigs fly just fine. However, this is not
necessarily a good idea. It is hard to be sure where they are going to
land, and it could be dangerous sitting under them as they fly
overhead. -- RFC 1925
| |
| Jerry Coffin 2006-03-18, 3:57 am |
| In article <#r5t7kdSGHA.256@TK2MSFTNGP14.phx.gbl>,
itandetnik@mvps.org says...
[ ... ]
> Bad idea, unless the vector is read-only after being populated. Pointers
> or iterators into the vector tend to become invalid when you insert or
> erase any element.
Quite true. I was taking for granted that wanting to
retain the original order meant you'd only ever add
elements to the end.
Even in that case, however, you're right: pointers can
become invalid when the vector's data gets reallocated,
so you should really store indices instead.
--
Later,
Jerry.
The universe is a figment of its own imagination.
| |
| Ismo Salonen 2006-03-20, 7:58 am |
| Jerry Coffin wrote:
> In article <#r5t7kdSGHA.256@TK2MSFTNGP14.phx.gbl>,
> itandetnik@mvps.org says...
>
> [ ... ]
>
>
> Quite true. I was taking for granted that wanting to
> retain the original order meant you'd only ever add
> elements to the end.
>
> Even in that case, however, you're right: pointers can
> become invalid when the vector's data gets reallocated,
> so you should really store indices instead.
But one could store indexes to the map. Or course this all should be
sealed in own class which handles needed methods internally.
ismo
|
|
|
|
|