circular_buffer, debug and invalid iterator checking
The invalid iterator checking in the circular_buffer library is excessively strict. It checks not when an iterator is dereferenced, but whenever any operator involving that iterator is used. I have an class defined to keep the last few data points, up to either a maximum number, or some condition on the stored data (e.g. the sum must be below a threshold) is met. So I figured I'd store the data in a circular buffer, and push new data onto the front, and store my own iterator into it to use as the end. If my end iterator is pointing to the next to last element in the buffer, when a new item is pushed onto the front of the circular buffer, that iterator becomes invalid. But that's not a problem for me, because I don't read past it. _Except_ the validity of the iterator is checked even when using it in operator== (and other iterator comparison operators), so my lopp condition tests now throw because the end of my ranges are no longer valid. Why isn't iterator invalidation only checked on dereferencing? Is there any suggested convention for changing my code to work under debug? I would try checking for BOOST_CB_ENABLE_DEBUG and catching these cases before the push_front occurs, but that macro is undefined at the end of the header. Or I could try something more complicated without the macro check, such as storing my ends in reverse iterators, and converting them whenever I need to do comparisons, though that is rather painful. I've attached a simple example which demonstrates the problem, not that it fails when the distance from my_end to end and the next element is pushed into the front. -- Anthony Foglia Princeton Consultants (609) 987-8787 x233
maximum number, or some condition on the stored data (e.g. the sum must be below a threshold) is met. So I figured I'd store the data in a circular buffer, and push new data onto the front, and store my own iterator into it to use as the end.
Anthony, Would it be viable to simply erase the remaining items, rather than storing the iterator my_end?
From an efficiency point of view it seems like the sum could be updated for each push, and then iteration over the items that need removing (from the end), rather than re-traversing the items at the front that need to be kept.
Just a thought. - Nigel
Nigel Stewart wrote:
maximum number, or some condition on the stored data (e.g. the sum must be below a threshold) is met. So I figured I'd store the data in a circular buffer, and push new data onto the front, and store my own iterator into it to use as the end.
Anthony,
Would it be viable to simply erase the remaining items, rather than storing the iterator my_end?
I realized that after I pressed send, but I'm storing my iterators as const_iterators because I wasn't expecting to need to change the buffer with them.
From an efficiency point of view it seems like the sum could be updated for each push, and then iteration over the items that need removing (from the end), rather than re-traversing the items at the front that need to be kept.
My actual problem is more complicated, with not just one iterator, but three, and not just ints, but a struct with multiple data members (though my code is only currently interested in one). The total number of items in the buffer is only 12, so the bookkeeping of three sums probably not worth the gain in speed in my situation. (This code is not the bottleneck.) -- Anthony Foglia Princeton Consultants (609) 987-8787 x233
So I figured I'd store the data in a circular buffer, and push new data onto the front, and store my own iterator into it to use as the end.
Anthony, Since the iterator is random access, perhaps they could be converted to integers via operator - and converted back to integers via operator + or operator +=. - Nigel
On 11/8/2010 2:58 PM, Nigel Stewart wrote:
Since the iterator is random access, perhaps they could be converted to integers via operator - and converted back to integers via operator + or operator +=.
That's what I did, but I used std::distance and std::advance instead, as per Meyer's suggestion in Effective STL. -- Anthony Foglia Princeton Consultants (609) 987-8787 x233
Still working on my circular_buffer iterator invalidation problems, and another issue arose. As I mentioned before my class is roughly class MyContainer { private: circular_buffer<T> my_buffer; vector<circular_buffer<T>::const_iterator> my_range_ends; // omitted } I'm trying to add a swap method, and the obvious approach does not work: void MyContainter::swap(MyContainer & other) { using std::swap; swap(my_buffer, other.my_buffer); swap(my_range_ends, other.my_range_ends); } This is unsurprising, because of the iterator invalidation rules. So I'll need to manually figure out the distances and create temporary vectors to hold my_range_ends. But this just seems like too much trouble if I'm not in debug mode. If the BOOST_CB_ENABLE_DEBUG macro hadn't been undefined by circular_buffer.hpp I could wrap my hand-coded iterator swapping in #if...#endif, and otherwise just use std::swap. I think this is a valid use case for leaving that macro defined. Any reasons I should not file a ticket requesting the change? -- Anthony Foglia Princeton Consultants (609) 987-8787 x233
You can achieve the same by relying on #if defined(NDEBUG) || defined(BOOST_CB_DISABLE_DEBUG) ... #else ... #endif Jan ________________________________ From: Anthony Foglia <AFoglia@princeton.com> To: boost-users@lists.boost.org Sent: Wed, 17 November, 2010 21:40:45 Subject: Re: [Boost-users] circular_buffer, debug and invalid iterator checking Still working on my circular_buffer iterator invalidation problems, and another issue arose. As I mentioned before my class is roughly class MyContainer { private: circular_buffer<T> my_buffer; vector<circular_buffer<T>::const_iterator> my_range_ends; // omitted } I'm trying to add a swap method, and the obvious approach does not work: void MyContainter::swap(MyContainer & other) { using std::swap; swap(my_buffer, other.my_buffer); swap(my_range_ends, other.my_range_ends); } This is unsurprising, because of the iterator invalidation rules. So I'll need to manually figure out the distances and create temporary vectors to hold my_range_ends. But this just seems like too much trouble if I'm not in debug mode. If the BOOST_CB_ENABLE_DEBUG macro hadn't been undefined by circular_buffer.hpp I could wrap my hand-coded iterator swapping in #if...#endif, and otherwise just use std::swap. I think this is a valid use case for leaving that macro defined. Any reasons I should not file a ticket requesting the change? -- Anthony Foglia Princeton Consultants (609) 987-8787 x233 _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
participants (4)
-
Anthony Foglia -
Anthony Foglia
-
Jan Gaspar -
Nigel Stewart