|  | order preserved in a std::map ? | | |
| | | Daniel |  |
|  Posted: Wed Jun 25, 2008 11:59 pm Post subject: order preserved in a std::map ? |  |
When deleting elements in a map is the ordering preserved. For
example say I have elements A, B and C (order A, B, C) in a map and B
is deleted, is the resulting ordering always A, C.
--
[ See LINK for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
| |
| | | Seungbeom Kim | |
| | Posted: Thu Jun 26, 2008 9:23 am Post subject: Re: order preserved in a std::map ? | |
Daniel wrote:
| Quote: | When deleting elements in a map is the ordering preserved. For
example say I have elements A, B and C (order A, B, C) in a map and B
is deleted, is the resulting ordering always A, C.
|
A map maintains its internal ordering by comparing the keys, and it is
required roughly that if A<B and B<C then A<C. Therefore, deleting an
element does not affect the others' ordering.
--
Seungbeom Kim
[ See LINK for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
| |
| | | Sarang | |
| | Posted: Thu Jun 26, 2008 9:44 am Post subject: Re: order preserved in a std::map ? | |
On Jun 26, 4:59 am, Daniel <danwgr...@gmail.com> wrote:
| Quote: | When deleting elements in a map is the ordering preserved. For
example say I have elements A, B and C (order A, B, C) in a map and B
is deleted, is the resulting ordering always A, C.
|
If we are talking about std::map, which are typically implemented as
trees, then the ordering is preserved if you access these by
iterators. This will not be the case for std::tr1::unordered_map
though.
Please correct me if I'm mistaken.
Best,
Sarang
--
[ See LINK for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
| |
| | | Saurabh Gupta | |
| | Posted: Thu Jun 26, 2008 9:45 am Post subject: Re: order preserved in a std::map ? | |
On Jun 26, 4:59 am, Daniel <danwgr...@gmail.com> wrote:
| Quote: | When deleting elements in a map is the ordering preserved. For
example say I have elements A, B and C (order A, B, C) in a map and B
is deleted, is the resulting ordering always A, C.
|
{ Edits: quoted clc++m banner removed. The banner is appended to every article
including this one (see below). Please don't quote extraneous material. -mod }
STL’s map data structure is binary search tree (balanced tree), it’s
always maintain it without bothering which data has been deleted. When
you traverse the map via iterator it will traverse the tree as left-
root-right. Therefore the out is always in the ascending order.
--
[ See LINK for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
| |
| | | Chris Uzdavinis | |
| | Posted: Thu Jun 26, 2008 9:57 am Post subject: Re: order preserved in a std::map ? | |
On Jun 25, 7:59 pm, Daniel <danwgr...@gmail.com> wrote:
| Quote: | When deleting elements in a map is the ordering preserved. For
example say I have elements A, B and C (order A, B, C) in a map and B
is deleted, is the resulting ordering always A, C.
|
Yes, the order is guaranteed to be maintained.
However, if you have buggy code, you may get undefined behavior, in
which case the guarantee is revoked. Elements in an associative
container must have a strict weak ordering defined for their key,
either directly or parameterized with a template argument used for
comparisons. Most of the common types (strings, numbers, etc) already
have this ordering defined, so most of the time everything is just
fine--but if the user provides a key type whose comparisons do not
define a strict weak ordering, that's when there is a problem.
--
Chris
--
[ See LINK for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
| |
|
|
