[Multi-Index] Design Rationale behind erase in ordered_index container
Hello Joaquín, the doc states in erase that an iterator or end-iterator is returned when erasing an element. What was the rationale behind returning the iterator? Where other members return the number of elements being removed. My point is that end-iterator is also returned when erasing an element where iterator points one before the end iterator. Now to be sure that the specified element was really removed my call must either use the key and search for that element again or compare the size before and after the erase call. Many thanks, Ovanes http://www.boost.org/doc/libs/1_47_0/libs/multi_index/doc/reference/ord_indi... iterator erase(iterator position); *Requires:* position is a valid dereferenceable iterator of the index. *Effects:* Deletes the element pointed to by position. *Returns:* An iterator pointing to the element immediately following the one that was deleted, or end() if no such element exists. *Complexity:* O(D(n)). *Exception safety:* nothrow.
Probably so that you may selectively erase elements within a loop based on some criteria. Kind Regards, Etienne Pretorius On 21 Feb 2012, at 5:29 PM, Ovanes Markarian wrote:
Hello Joaquín,
the doc states in erase that an iterator or end-iterator is returned when erasing an element. What was the rationale behind returning the iterator? Where other members return the number of elements being removed.
My point is that end-iterator is also returned when erasing an element where iterator points one before the end iterator. Now to be sure that the specified element was really removed my call must either use the key and search for that element again or compare the size before and after the erase call.
Many thanks, Ovanes
http://www.boost.org/doc/libs/1_47_0/libs/multi_index/doc/reference/ord_indi...
iterator erase(iterator position); Requires: position is a valid dereferenceable iterator of the index. Effects: Deletes the element pointed to by position. Returns: An iterator pointing to the element immediately following the one that was deleted, or end() if no such element exists. Complexity: O(D(n)). Exception safety: nothrow. _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Please don't top-post. I've taken the liberty of moving your reply to the bottom where it belongs. On Tuesday, February 21, 2012 10:33 AM, Etienne Pretorius wrote:
On 21 Feb 2012, at 5:29 PM, Ovanes Markarian wrote:
Hello Joaquín,
the doc states in erase that an iterator or end-iterator is returned when erasing an element. What was the rationale behind returning the iterator? Where other members return the number of elements being removed.
My point is that end-iterator is also returned when erasing an element where iterator points one before the end iterator. Now to be sure that the specified element was really removed my call must either use the key and search for that element again or compare the size before and after the erase call.
Many thanks, Ovanes
http://www.boost.org/doc/libs/1_47_0/libs/multi_index/doc/reference/ord_indi...
iterator erase(iterator position); Requires: position is a valid dereferenceable iterator of the index. Effects: Deletes the element pointed to by position. Returns: An iterator pointing to the element immediately following the one that was deleted, or end() if no such element exists. Complexity: O(D(n)). Exception safety: nothrow.
Probably so that you may selectively erase elements within a loop based on some criteria.
Kind Regards, Etienne Pretorius
I can think of three reasons for this behavior: 1: multi_index mimics the behavior of STL containers to the greatest extent possible, and their erase(iterator) functions return the iterator of the following element. 2: Returning the iterator allows programs to easily erase elements without losing their place in the container. 3: The erase function is guaranteed to succeed.
Etienne and Andrew thanks for your comments, please find my answers below... On Tue, Feb 21, 2012 at 5:00 PM, Andrew Holden < aholden@charteroaksystems.com> wrote:
Please don't top-post. I've taken the liberty of moving your reply to the bottom where it belongs.
On Tuesday, February 21, 2012 10:33 AM, Etienne Pretorius wrote:
On 21 Feb 2012, at 5:29 PM, Ovanes Markarian wrote:
Hello Joaquín,
the doc states in erase that an iterator or end-iterator is returned when erasing an element. What was the rationale behind returning the iterator? Where other members return the number of elements being removed.
My point is that end-iterator is also returned when erasing an element where iterator points one before the end iterator. Now to be sure that the specified element was really removed my call must either use the key and search for that element again or compare the size before and after the erase call. [...]
Probably so that you may selectively erase elements within a loop based on some criteria.
I can think of three reasons for this behavior:
1: multi_index mimics the behavior of STL containers to the greatest extent possible, and their erase(iterator) functions return the iterator of the following element.
Which ones? std::map<...>::erase either returns void or number of deleted elements.
2: Returning the iterator allows programs to easily erase elements without losing their place in the container.
Yes this is a good point, it might be possible to return a pair type containing the iterator and bool value.
3: The erase function is guaranteed to succeed.
What happens if some sw part mixes up the iterator from the other container instance? This might really be a clear case for assert, if the iterator and container know about each other... Thanks, Ovanes
1: multi_index mimics the behavior of STL containers to the greatest extent possible, and their erase(iterator) functions return the iterator of the following element.
Which ones? std::map<...>::erase either returns void or number of deleted elements.
It was just overlooked in final standard version, and fixed later: http://lists.boost.org/boost-users/2011/12/72162.php
On Tuesday, February 21, 2012 11:40 AM, Ovanes Markarian wrote:
On Tue, Feb 21, 2012 at 5:00 PM, Andrew Holden <aholden@charteroaksystems.com> wrote:
I can think of three reasons for this behavior:
1: multi_index mimics the behavior of STL containers to the greatest extent possible, and their erase(iterator) functions return the iterator of the following element. Which ones? std::map<...>::erase either returns void or number of deleted elements.
Hmm. It appears I shouldn't have been using the Microsoft documentation. Microsoft claims the variants that take 1 or 2 iterators return the iterator for the following element.
2: Returning the iterator allows programs to easily erase elements without losing their place in the container. Yes this is a good point, it might be possible to return a pair type containing the iterator and bool value.
3: The erase function is guaranteed to succeed. What happens if some sw part mixes up the iterator from the other container instance? This might really be a clear case for assert, if the iterator and container know about each other...
That would result in undefined behavior. If the iterator and container know about each other (usually via a gross violation of big-O), then an assert is possible. Otherwise, expect corruption of your containers, hopefully followed by a core dump.
On Tue, Feb 21, 2012 at 5:59 PM, Andrew Holden < aholden@charteroaksystems.com> wrote:
On Tuesday, February 21, 2012 11:40 AM, Ovanes Markarian wrote:
On Tue, Feb 21, 2012 at 5:00 PM, Andrew Holden < aholden@charteroaksystems.com> wrote:
I can think of three reasons for this behavior:
[...]
3: The erase function is guaranteed to succeed. What happens if some sw part mixes up the iterator from the other container instance? This might really be a clear case for assert, if the iterator and container know about each other...
That would result in undefined behavior. If the iterator and container know about each other (usually via a gross violation of big-O), then an assert is possible. Otherwise, expect corruption of your containers, hopefully followed by a core dump.
Actually this is what I am trying to prevent in my code. Just do an assertion that remove was successful, but finally, I got in the unit test an assertion failure, because I was deleting a last element in the ordered index and got end-iterator. And my comparison with the end-iterator returned false for removal, resulting in the failed assertion.
On Tuesday, February 21, 2012 12:13 PM, Ovanes Markarian wrote:
On Tue, Feb 21, 2012 at 5:59 PM, Andrew Holden <aholden@charteroaksystems.com> wrote:
On Tuesday, February 21, 2012 11:40 AM, Ovanes Markarian wrote:
On Tue, Feb 21, 2012 at 5:00 PM, Andrew Holden <aholden@charteroaksystems.com> wrote:
I can think of three reasons for this behavior:
[...]
3: The erase function is guaranteed to succeed. What happens if some sw part mixes up the iterator from the other container instance? This might really be a clear case for assert, if the iterator and container know about each other... That would result in undefined behavior. If the iterator and container know about each other (usually via a gross violation of big-O), then an assert is possible. Otherwise, expect corruption of your containers, hopefully followed by a core dump.
Actually this is what I am trying to prevent in my code. Just do an assertion that remove was successful, but finally, I got in the unit test an assertion failure, because I was deleting a last element in the ordered index and got end-iterator. And my comparison with the end-iterator returned false for removal, resulting in the failed assertion.
To clarify, are you saying that, when you deleted the last element in an index, you did *not* get the end iterator? Or are you saying your test considered end iterator an error? To clarify, end iterator from erase never indicates an error. It just means you deleted the last element. I found an old email from Joaquín Muñoz detailing some macros that enable iterator checking. Maybe this will help you? If I recall correctly, any of the checks these macros enable will cause an assert within the container's member functions. There is still nothing in erase(iterator)'s return value to indicate success or failure. On 24 September 2009, Joaquín M López Muñoz wrote: These macros are not documented in the reference for a very academic reason, they're details of this particular implementation rather than part of the public interface --this is admittedly a little too picky, maybe. The macros are documented through the tutorial, though. For your reference: BOOST_MULTI_INDEX_ENABLE_SAFE_MODE BOOST_MULTI_INDEX_SAFE_MODE_ASSERT http://www.boost.org/libs/multi_index/doc/tutorial/debug.html#safe_mode BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING BOOST_MULTI_INDEX_INVARIANT_ASSERT http://www.boost.org/libs/multi_index/doc/tutorial/debug.html#invariant_chec... BOOST_MULTI_INDEX_DISABLE_SERIALIZATION http://www.boost.org/libs/multi_index/doc/tutorial/creation.html#serializati... BOOST_MULTI_INDEX_DISABLE_COMPRESSED_ORDERED_INDEX_NODES http://www.boost.org/libs/multi_index/doc/tutorial/indices.html#ordered_node... BOOST_MULTI_INDEX_LIMIT_INDEXED_BY_SIZE BOOST_MULTI_INDEX_LIMIT_TAG_SIZE http://www.boost.org/libs/multi_index/doc/compiler_specifics.html#symbol_red... HTH, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
On Tue, Feb 21, 2012 at 6:55 PM, Andrew Holden < aholden@charteroaksystems.com> wrote:
On Tue, Feb 21, 2012 at 5:59 PM, Andrew Holden < aholden@charteroaksystems.com> wrote:
On Tuesday, February 21, 2012 11:40 AM, Ovanes Markarian wrote:
On Tue, Feb 21, 2012 at 5:00 PM, Andrew Holden < aholden@charteroaksystems.com> wrote:
I can think of three reasons for this behavior:
[...]
3: The erase function is guaranteed to succeed. What happens if some sw part mixes up the iterator from the other container instance? This might really be a clear case for assert, if the iterator and container know about each other... That would result in undefined behavior. If the iterator and container know about each other (usually via a gross violation of big-O), then an assert is
On Tuesday, February 21, 2012 12:13 PM, Ovanes Markarian wrote: possible.
Otherwise, expect corruption of your containers, hopefully followed by a core dump.
Actually this is what I am trying to prevent in my code. Just do an assertion that remove was successful, but finally, I got in the unit test an assertion failure, because I was deleting a last element in the ordered index and got end-iterator. And my comparison with the end-iterator returned false for removal, resulting in the failed assertion.
To clarify, are you saying that, when you deleted the last element in an index, you did *not* get the end iterator? Or are you saying your test considered end iterator an error? To clarify, end iterator from erase never indicates an error. It just means you deleted the last element.
I think I misread or misunderstood English... ;( "An iterator pointing to the element immediately following the one that was deleted, or end() if no such element exists." I considered if no such element exists to be the element the iterator parameter pointing to, but actually this means the next element succeeding the deleted one or end, if no succeeding element exists.
I found an old email from Joaquín Muñoz detailing some macros that enable iterator checking. Maybe this will help you? If I recall correctly, any of the checks these macros enable will cause an assert within the container's member functions. There is still nothing in erase(iterator)'s return value to indicate success or failure.
On 24 September 2009, Joaquín M López Muñoz wrote: These macros are not documented in the reference for a very academic reason, they're details of this particular implementation rather than part of the public interface --this is admittedly a little too picky, maybe.
The macros are documented through the tutorial, though. For your reference:
BOOST_MULTI_INDEX_ENABLE_SAFE_MODE BOOST_MULTI_INDEX_SAFE_MODE_ASSERT http://www.boost.org/libs/multi_index/doc/tutorial/debug.html#safe_mode
BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING BOOST_MULTI_INDEX_INVARIANT_ASSERT
http://www.boost.org/libs/multi_index/doc/tutorial/debug.html#invariant_chec...
BOOST_MULTI_INDEX_DISABLE_SERIALIZATION
http://www.boost.org/libs/multi_index/doc/tutorial/creation.html#serializati...
BOOST_MULTI_INDEX_DISABLE_COMPRESSED_ORDERED_INDEX_NODES
http://www.boost.org/libs/multi_index/doc/tutorial/indices.html#ordered_node...
BOOST_MULTI_INDEX_LIMIT_INDEXED_BY_SIZE BOOST_MULTI_INDEX_LIMIT_TAG_SIZE
http://www.boost.org/libs/multi_index/doc/compiler_specifics.html#symbol_red...
Thanks for the macros I will think enabling them Regards, ovanes
Ovanes Markarian <om_boost <at> keywallet.com> writes:
Hello Joaquín,
Hi Ovanes,
the doc states in erase that an iterator or end-iterator is returned when erasing an element. What was the rationale behind returning the iterator? Where other members return the number of elements being removed.
To be in accordance with the standard. As others have pointed out, prior versions of the standard incorrectly dictated that for some containers erase(iterator) return void, but this was later fixed, see http://www.boost.org/libs/multi_index/doc/release_notes.html#boost_1_33_1 for details.
My point is that end-iterator is also returned when erasing an element where iterator points one before the end iterator. Now to be sure that the specified element was really removed my call must either use the key and search for that element again or compare the size before and after the erase call.
erase(iterator) never fails if used legally: providing it with an iterator from another container, which is illegal, results in undefined behavior. Enabling the safe mode as Andrew suggests can help you *debug* your problem, but shouldn't be used as a library feature in production code --safe mode incurs a considerable runtime penalty. If you really need to call erase(iterator) with iterators from another container, the solution would be to refactor your code so as to store pair(iterator,container&)s rather than iterators and do the check before actually executing erase(). Joaquín M López Muñoz Telefónica Digital
Hello Joaquín, On Tue, Feb 21, 2012 at 9:29 PM, Joaquin M Lopez Munoz <joaquin@tid.es>wrote:
Ovanes Markarian <om_boost <at> keywallet.com> writes:
Hello Joaquín,
Hi Ovanes, [...]
If you really need to call erase(iterator) with iterators from another container, the solution would be to refactor your code so as to store pair(iterator,container&)s rather than iterators and do the check before actually executing erase().
Actually, I am just too carefull. That is not possible how it is used, but want to be sure. Anyway enabling additional diagnostics might be a good idea. With Kind Regards, Ovanes.
participants (5)
-
Andrew Holden -
Etienne Pretorius -
Igor R -
Joaquin M Lopez Munoz -
Ovanes Markarian