Correct use of unordered_map
Consider this loop: const my_map_t::iterator end= my_map.end(); for (my_map_t::iterator it= my_map.begin(); it != end; ++it) { if (is_to_be_removed(it->first)) global_map.erase (it); } The documentation I've seen for unordered_map says that removing doesn't invalidate iterators except those referring to the element being deleted. But that's the case for it itself! Also, what does removing one element do to the ordering of the elements -- is there any guarantee that the iterator will visit exactly the ones that were not visited before? What is the correct, standards-conforming, way to perform this? Thanks, --John TradeStation Group, Inc. is a publicly-traded holding company (NASDAQ GS: TRAD) of three operating subsidiaries, TradeStation Securities, Inc. (Member NYSE, FINRA, SIPC and NFA), TradeStation Technologies, Inc., a trading software and subscription company, and TradeStation Europe Limited, a United Kingdom, FSA-authorized introducing brokerage firm. None of these companies provides trading or investment advice, recommendations or endorsements of any kind. The information transmitted is intended only for the person or entity to which it is addressed and may contain confidential and/or privileged material. Any review, retransmission, dissemination or other use of, or taking of any action in reliance upon, this information by persons or entities other than the intended recipient is prohibited. If you received this in error, please contact the sender and delete the material from any computer.
I believe one solution would look something like: const my_map_t::iterator end= my_map.end(); for (my_map_t::iterator it= my_map.begin(); it != end; ) { if (is_to_be_removed(it->first)) it = global_map.erase (it); else ++it; } -z John Dlugosz wrote:
Consider this loop:
const my_map_t::iterator end= my_map.end(); for (my_map_t::iterator it= my_map.begin(); it != end; ++it) { if (is_to_be_removed(it->first)) global_map.erase (it); }
The documentation I've seen for unordered_map says that removing doesn't invalidate iterators except those referring to the element being deleted. But that's the case for it itself! Also, what does removing one element do to the ordering of the elements -- is there any guarantee that the iterator will visit exactly the ones that were not visited before?
What is the correct, standards-conforming, way to perform this?
Thanks, --John
TradeStation Group, Inc. is a publicly-traded holding company (NASDAQ GS: TRAD) of three operating subsidiaries, TradeStation Securities, Inc. (Member NYSE, FINRA, SIPC and NFA), TradeStation Technologies, Inc., a trading software and subscription company, and TradeStation Europe Limited, a United Kingdom, FSA-authorized introducing brokerage firm. None of these companies provides trading or investment advice, recommendations or endorsements of any kind. The information transmitted is intended only for the person or entity to which it is addressed and may contain confidential and/or privileged material. Any review, retransmission, dissemination or other use of, or taking of any action in reliance upon, this information by persons or entities other than the intended recipient is prohibited. If you received this in error, please contact the sender and delete the material from any computer.
John Dlugosz wrote:
Consider this loop:
const my_map_t::iterator end= my_map.end(); for (my_map_t::iterator it= my_map.begin(); it != end; ++it) { if (is_to_be_removed(it->first)) global_map.erase (it); }
The documentation I've seen for unordered_map says that removing doesn't invalidate iterators except those referring to the element being deleted. But that's the case for it itself! Also, what does removing one element do to the ordering of the elements -- is there any guarantee that the iterator will visit exactly the ones that were not visited before?
What is the correct, standards-conforming, way to perform this?
I use one of these 2 ways: for (my_map_t::iterator it= my_map.begin(); it != end; ) { if (is_to_be_removed(it->first)) it = global_map.erase (it); else ++it; } for (my_map_t::iterator it= my_map.begin(); it != end; ) { my_map_t::iterator itx = it++; if (is_to_be_removed(itx->first)) global_map.erase (itx); } -- Dick Hadsell 203-992-6320 Fax: 203-992-6001 Reply-to: hadsell@blueskystudios.com Blue Sky Studios http://www.blueskystudios.com 1 American Lane, Greenwich, CT 06831-2560
Richard Hadsell wrote:
I use one of these 2 ways:
for (my_map_t::iterator it= my_map.begin(); it != end; ) { if (is_to_be_removed(it->first)) it = global_map.erase (it); else ++it; }
for (my_map_t::iterator it= my_map.begin(); it != end; ) { my_map_t::iterator itx = it++; if (is_to_be_removed(itx->first)) global_map.erase (itx); } I should add that the second way is useful, when you are not executing 'erase' but rather some arbitrary code that may or may not actually erase the element from the container.
-- Dick Hadsell 203-992-6320 Fax: 203-992-6001 Reply-to: hadsell@blueskystudios.com Blue Sky Studios http://www.blueskystudios.com 1 American Lane, Greenwich, CT 06831-2560
Richard Hadsell wrote:
I use one of these 2 ways:
for (my_map_t::iterator it= my_map.begin(); it != end; ) { if (is_to_be_removed(it->first)) it = global_map.erase (it); else ++it; }
for (my_map_t::iterator it= my_map.begin(); it != end; ) { my_map_t::iterator itx = it++; if (is_to_be_removed(itx->first)) global_map.erase (itx); }
I should add that the second way is useful, when you are not executing 'erase' but rather some arbitrary code that may or may not actually erase the element from the container.
nod I can't resist pointing out Scott Meyers's "Effective STL," Item 9, p. 43: "Choose carefully among erasing options." :-)
Thanks Richard and zap. After posting, I did notice the return value from erase, and decided to use a while loop. However, I still wonder about the details of the standard and what is correct. 1) is end unchanging, or must you call end() every time rather than remembering it? 2) does resuming iteration from the "successor" traverse the remaining elements? The wording is copied from the plain map class, which is ordered and the ordering definition of the iterators makes #2 well defined. That is not the case for the unordered_map. I might argue that even "successor" is not defined on this type. I understand that the intent is to work like map, but have the ordering be opaque to the user. But, as documented, and now in the standard that I found online, I'm afraid that a conforming implementation could be different. E.g. removing an element could totally re-order the apparent traversal order, and even though the iterators are still valid, will not pick up exactly those elements that were not already seen. --John
-----Original Message----- From: boost-users-bounces@lists.boost.org [mailto:boost-users- bounces@lists.boost.org] On Behalf Of Richard Hadsell Sent: Monday, August 31, 2009 6:12 PM To: boost-users@lists.boost.org Subject: Re: [Boost-users] Correct use of unordered_map
John Dlugosz wrote:
Consider this loop:
const my_map_t::iterator end= my_map.end(); for (my_map_t::iterator it= my_map.begin(); it != end; ++it) { if (is_to_be_removed(it->first)) global_map.erase (it); }
The documentation I've seen for unordered_map says that removing doesn't invalidate iterators except those referring to the element being deleted. But that's the case for it itself! Also, what does removing one element do to the ordering of the elements -- is there any guarantee that the iterator will visit exactly the ones that were not visited before?
What is the correct, standards-conforming, way to perform this?
I use one of these 2 ways:
for (my_map_t::iterator it= my_map.begin(); it != end; ) { if (is_to_be_removed(it->first)) it = global_map.erase (it); else ++it; }
for (my_map_t::iterator it= my_map.begin(); it != end; ) { my_map_t::iterator itx = it++; if (is_to_be_removed(itx->first)) global_map.erase (itx); }
-- Dick Hadsell 203-992-6320 Fax: 203-992-6001 Reply-to: hadsell@blueskystudios.com Blue Sky Studios http://www.blueskystudios.com 1 American Lane, Greenwich, CT 06831-2560
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
TradeStation Group, Inc. is a publicly-traded holding company (NASDAQ GS: TRAD) of three operating subsidiaries, TradeStation Securities, Inc. (Member NYSE, FINRA, SIPC and NFA), TradeStation Technologies, Inc., a trading software and subscription company, and TradeStation Europe Limited, a United Kingdom, FSA-authorized introducing brokerage firm. None of these companies provides trading or investment advice, recommendations or endorsements of any kind. The information transmitted is intended only for the person or entity to which it is addressed and may contain confidential and/or privileged material. Any review, retransmission, dissemination or other use of, or taking of any action in reliance upon, this information by persons or entities other than the intended recipient is prohibited. If you received this in error, please contact the sender and delete the material from any computer.
2009/9/1 John Dlugosz
1) is end unchanging, or must you call end() every time rather than remembering it?
As long as you don't call a method which can invalidate it, it's fine. Erase won't invalidate the end iterator.
2) does resuming iteration from the "successor" traverse the remaining elements?
The wording is copied from the plain map class, which is ordered and the ordering definition of the iterators makes #2 well defined. That is not the case for the unordered_map.
Changing the order of the elements would invalidate iterators so it's safe to say that the order of elements that haven't been erased will remain the same. But be careful with other methods.
I might argue that even "successor" is not defined on this type.
You might, but you probably shouldn't. Daniel
Changing the order of the elements would invalidate iterators so it's safe to say that the order of elements that haven't been erased will remain the same. But be careful with other methods.
I might argue that even "successor" is not defined on this type.
You might, but you probably shouldn't.
Daniel
So the key would be a suitable definition for a "valid iterator". Each iterator for an "unordered" collection that nevertheless can proceed to end() is logically a state that contains a current element and a set of future to-be-traversed elements. Stepping will select one element from that remaining set, and produce an iterator with that as the current element and the future set reduced by that element. Erasing an element removes it from all outstanding iterator's future sets, if present. Inserting an element may or may not add it to the future set each outstanding iterator. The future set is not "ordered" and any change might affect which element it picks next, compared to what it would have picked had you not done that. But that does not change the "validity". The docs with Boost and with Microsoft's MSDN does not explain it properly. It's just copied from the regular map documentation, and saying it's "unordered" spoils the meaning of the copied phrasing. Who might I talk to, concerning tightening up the Boost documentation or the ultimate C++ Standard documentation? --John TradeStation Group, Inc. is a publicly-traded holding company (NASDAQ GS: TRAD) of three operating subsidiaries, TradeStation Securities, Inc. (Member NYSE, FINRA, SIPC and NFA), TradeStation Technologies, Inc., a trading software and subscription company, and TradeStation Europe Limited, a United Kingdom, FSA-authorized introducing brokerage firm. None of these companies provides trading or investment advice, recommendations or endorsements of any kind. The information transmitted is intended only for the person or entity to which it is addressed and may contain confidential and/or privileged material. Any review, retransmission, dissemination or other use of, or taking of any action in reliance upon, this information by persons or entities other than the intended recipient is prohibited. If you received this in error, please contact the sender and delete the material from any computer.
2009/9/2 John Dlugosz
So the key would be a suitable definition for a "valid iterator". Each iterator for an "unordered" collection that nevertheless can proceed to end() is logically a state that contains a current element and a set of future to-be-traversed elements. Stepping will select one element from that remaining set, and produce an iterator with that as the current element and the future set reduced by that element. Erasing an element removes it from all outstanding iterator's future sets, if present.
Sort of, but you're missing the important point that a range (the STL jargon for what you call set, it's less confusing if we stick to STL jargon) can be defined by two iterators - so not up to the end of the container. If the order of elements changed such that the start iterator was after the end iterator then that range would become invalid which is why the order of elements can't change after an erase.
Inserting an element may or may not add it to the future set each outstanding iterator.
Not sure what you mean there, but remember that insert can invalidate iterators
The future set is not "ordered" and any change might affect which element it picks next, compared to what it would have picked had you not done that. But that does not change the "validity".
Not really, an insert may insert an element after your iterator, an erase may erase the next element - that's the same as the ordered containers. But if your iterators are invalidated (which insert can do, I think the exact conditions are explained in the documentation) you can't use them.
The docs with Boost and with Microsoft's MSDN does not explain it properly. It's just copied from the regular map documentation, and saying it's "unordered" spoils the meaning of the copied phrasing.
Who might I talk to, concerning tightening up the Boost documentation or the ultimate C++ Standard documentation?
I'm the person for the boost documentation. But you should remember that all this documentation assumes familiarity with the STL concepts - which most of what you're talking about comes from. Looking at the documentation it probably could do with a bit more of a discussion of what it means to be 'unordered' but I don't think it's the correct place to document how iterators work - it should be enough to say they're forward iterators and perhaps link to an explanation of what a forward iterator is. Daniel
Sort of, but you're missing the important point that a range (the STL jargon for what you call set,
I thought the STL was going to be adopting the "range" concepts from the STL range library. That is, a range will be a begin-end iterator pair or something that behaves like that.
...but remember that insert can invalidate iterators
OK, I missed that.
I'm the person for the boost documentation. But you should remember that all this documentation assumes familiarity with the STL concepts - which most of what you're talking about comes from. Looking at the documentation it probably could do with a bit more of a discussion of what it means to be 'unordered' but I don't think it's the correct place to document how iterators work - it should be enough to say they're forward iterators and perhaps link to an explanation of what a forward iterator is.
Daniel
Reading it through from the beginning... "An unordered associative container that associates unique keys with another value." Key has equivalence relation (only). member begin returns "An iterator referring to the first element of the container" "first" contradicts "unordered". There is no meaning for first. The iterator has a difference type. It doesn't say what kind of iterator it is, but I assume forward_iterator as the broadest, since input_iterator and output_iterator would not be applicable. So, do elements have a definite and unchanging order in the container, or can different iterations produce different orders? The latter gives maximum freedom to the implementation, but is more difficult to define properly. If the former, just saying that would fix the issues I have with the current definitions. (BTW, the HREF to n2691 is dead) To suggest a concrete example, you might insert, "Although no relation is supplied for the key type, for purposes of iteration the elements will appear to have a definite order that is determined by the implementation. This order may be changed by any function that invalidates iterators, including insert and rehash." That certainly describes the Boost class. But should the C++ standard have more freedom? The draft standard I've seen does include the bucket exposing functions, so maybe it is locked into this one implementation. TradeStation Group, Inc. is a publicly-traded holding company (NASDAQ GS: TRAD) of three operating subsidiaries, TradeStation Securities, Inc. (Member NYSE, FINRA, SIPC and NFA), TradeStation Technologies, Inc., a trading software and subscription company, and TradeStation Europe Limited, a United Kingdom, FSA-authorized introducing brokerage firm. None of these companies provides trading or investment advice, recommendations or endorsements of any kind. The information transmitted is intended only for the person or entity to which it is addressed and may contain confidential and/or privileged material. Any review, retransmission, dissemination or other use of, or taking of any action in reliance upon, this information by persons or entities other than the intended recipient is prohibited. If you received this in error, please contact the sender and delete the material from any computer.
2009/9/3 John Dlugosz
Sort of, but you're missing the important point that a range (the STL jargon for what you call set,
I thought the STL was going to be adopting the "range" concepts from the STL range library. That is, a range will be a begin-end iterator pair or something that behaves like that.
Sorry, I don't see what you're getting at. As far as I know, STL ranges are the same as they've alway been (two iterators defining a half-open range).
Reading it through from the beginning...
In the future, can you include the url or path of the page you're referring to? It'd make it a lot easier.
"An unordered associative container that associates unique keys with another value."
Key has equivalence relation (only).
To be pedantic, they might have other relations. Perhaps, 'The only required relation is an equivalence relation'.
member begin returns "An iterator referring to the first element of the container"
"first" contradicts "unordered". There is no meaning for first.
Not really. In this context, unordered means that the order of elements doesn't follow a predetermined order, and can change under certain conditions. There is a first element, but it isn't deterministic.
The iterator has a difference type. It doesn't say what kind of iterator it is, but I assume forward_iterator as the broadest, since input_iterator and output_iterator would not be applicable.
So, do elements have a definite and unchanging order in the container, or can different iterations produce different orders? The latter gives maximum freedom to the implementation, but is more difficult to define properly. If the former, just saying that would fix the issues I have with the current definitions.
I don't think the standard explicitly says so. It does state that rehashing changes the order, I'm not sure if that implies that the order remains constant under all other conditions. If a container tracked the existence of iterators I don't know if it could change the order of elements when there are no existing iterators. You'd probably get a more informed answer on comp.std.c++ or comp.lang.c++.moderated. I'm not much of a language lawyer.
(BTW, the HREF to n2691 is dead)
Thanks, I'll fix that. I should probably change the wording as well as that version is now out of date. Although I don't quite conform to the latest version - and I'm not going to catch up until the version without concepts is released.
To suggest a concrete example, you might insert, "Although no relation is supplied for the key type, for purposes of iteration the elements will appear to have a definite order that is determined by the implementation. This order may be changed by any function that invalidates iterators, including insert and rehash."
I think I'd write 'Although no ordering is supplied for the key type' since there's an equivalence relation.
That certainly describes the Boost class. But should the C++ standard have more freedom? The draft standard I've seen does include the bucket exposing functions, so maybe it is locked into this one implementation.
There isn't much freedom. It might be possible to use another structure and fake the buckets. Although that would be pretty dubious. Intersetingly, I don't think there's a requirement that the iteration order corresponds to the buckets - it isn't specified that local iterators and normal iterators have to follow the same order. Although it is required that equivalent keys are adjacent in unordered_multimap and unordered_multiset. Daniel
Sorry, I don't see what you're getting at. As far as I know, STL ranges are the same as they've alway been (two iterators defining a half-open range).
In my earlier post which started this particular sub-discussion, I was trying to describe how to iterate a collection without any ordering. A "range" is two points in an ordered list. Now, we're focusing on describing an internal ordering, so don't worry about that.
Reading it through from the beginning...
In the future, can you include the url or path of the page you're referring to? It'd make it a lot easier.
Yes.
"An unordered associative container that associates unique keys with another value."
Key has equivalence relation (only).
To be pedantic, they might have other relations. Perhaps, 'The only required relation is an equivalence relation'.
Yes.
member begin returns "An iterator referring to the first element of the container"
"first" contradicts "unordered". There is no meaning for first.
Not really. In this context, unordered means that the order of elements doesn't follow a predetermined order, and can change under certain conditions. There is a first element, but it isn't deterministic.
Ah, here is where we differ. You know what it is supposed to mean; e.g. how the container actually works. But that's not what it says. I started from the top of the document -- there is no context that establishes this. That is what I suggested adding. In any case, why not make it clearer and better? My published magazine articles have always been much improved by circulating a first draft and getting back comments, especially where some point was unclear to someone but I "knew" what it was putting it in.
I don't think the standard explicitly says so. It does state that rehashing changes the order, I'm not sure if that implies that the order remains constant under all other conditions. If a container tracked the existence of iterators I don't know if it could change the order of elements when there are no existing iterators. You'd probably get a more informed answer on comp.std.c++ or comp.lang.c++.moderated. I'm not much of a language lawyer.
The hash function is the only place in unordered_map.htm where "order" is mentioned at all. As it stands, it's also a non sequitur like "begin", since this is "an unordered associative container". (I am something of a language lawyer, BTW)
(BTW, the HREF to n2691 is dead)
Thanks, I'll fix that. I should probably change the wording as well as that version is now out of date. Although I don't quite conform to the latest version - and I'm not going to catch up until the version without concepts is released.
Personally, I'm more interested in how it may differ from the implementation that Microsoft supplies in Visual Studio 2008's update (I presume it is from Dinkumware), then in the ideal that no compiler supports yet. That's my engineering interest for work, anyway.
To suggest a concrete example, you might insert, "Although no relation is supplied for the key type, for purposes of iteration the elements will appear to have a definite order that is determined by the implementation. This order may be changed by any function that invalidates iterators, including insert and rehash."
I think I'd write 'Although no ordering is supplied for the key type' since there's an equivalence relation.
Yes, I tend to forget that "relation" does include the equivalence, since I normally see and use "equality operator ...(later)... relational operations" as separate parts.
There isn't much freedom. It might be possible to use another structure and fake the buckets. Although that would be pretty dubious.
Intersetingly, I don't think there's a requirement that the iteration order corresponds to the buckets - it isn't specified that local iterators and normal iterators have to follow the same order. Although it is required that equivalent keys are adjacent in unordered_multimap and unordered_multiset.
Daniel
I wonder, why are "local iterators" and buckets exposed at all? A non-order-preserving (experimenting with alternative to "unordered" that better describes the situation--in Perl for example they point out that the order of keys is not the order in which you added them, but they don't feel the need to explain that they are not sorted either) associative container doesn't *need* that to work. I pretty much ignored their existence. --John TradeStation Group, Inc. is a publicly-traded holding company (NASDAQ GS: TRAD) of three operating subsidiaries, TradeStation Securities, Inc. (Member NYSE, FINRA, SIPC and NFA), TradeStation Technologies, Inc., a trading software and subscription company, and TradeStation Europe Limited, a United Kingdom, FSA-authorized introducing brokerage firm. None of these companies provides trading or investment advice, recommendations or endorsements of any kind. The information transmitted is intended only for the person or entity to which it is addressed and may contain confidential and/or privileged material. Any review, retransmission, dissemination or other use of, or taking of any action in reliance upon, this information by persons or entities other than the intended recipient is prohibited. If you received this in error, please contact the sender and delete the material from any computer.
I'm the person for the boost documentation.
Daniel
typedef implementation-defined iterator; A iterator whose value type is value_type. Any iterator category except output iterator. It can't be an input_iterator either, right? --John TradeStation Group, Inc. is a publicly-traded holding company (NASDAQ GS: TRAD) of three operating subsidiaries, TradeStation Securities, Inc. (Member NYSE, FINRA, SIPC and NFA), TradeStation Technologies, Inc., a trading software and subscription company, and TradeStation Europe Limited, a United Kingdom, FSA-authorized introducing brokerage firm. None of these companies provides trading or investment advice, recommendations or endorsements of any kind. The information transmitted is intended only for the person or entity to which it is addressed and may contain confidential and/or privileged material. Any review, retransmission, dissemination or other use of, or taking of any action in reliance upon, this information by persons or entities other than the intended recipient is prohibited. If you received this in error, please contact the sender and delete the material from any computer.
participants (5)
-
Daniel James -
John Dlugosz -
Nat Goodspeed -
Richard Hadsell -
zap.foster