Re: Clean ways to count remove_if() removals?
* Jerry Coffin:
In article <wrSdnTQaDuLqiN_XnZ2dnUVZ_tSdnZ2d@giganews.com>,
pete@versatilecoding.com says...
[ ... ]
The standard says it "should have constant complexity". That's a
recommendation, not a requirement. One issue here is the requirement
that list::splice have constant complexity, which can't be done if size
is also constant complexity.
I was looking at that, but after looking carefully, I believe size()
can be made constant complexity while meeting all the complexity
requirements for splice().
There are three overloads of splice:
void splice(iterator position, list<T, Allocator> &x);
Inserts the entirety of x at before position. The cached size can be
updated in constant time:
cached_size += x.size();
x.cached_size = 0;
void splice(iterator position, list<T, Allocator>& x, iterator i);
This removes x[i] and inserts it as this[position]. The sizes can be
updated in consant time:
++cached_size;
--x.cached_size;
void splice(iterator position, list<T, Allocator> &x, iterator first,
iterator last);
This is the (somewhat) tricky one: the requirement is:
Constant time if &x == this; otherwise, linear time
If &x==this, we're just moving elements around in the same container
-- so the container's size doesn't change. We can just modify the
pointers in constant time, and never have to touch the cached size at
all.
Well, the problem is making this last case O(1) when moving a sequence of
elements from from one list to another, while keeping size() as O(1).
Can't be done.
If we're moving elements from one container to another, linear time
is allowed. This allows walking the elements in the list from first
to last to count the elements.
Yeah, the standard's requirements are achievable, but the conflict between
size() and splice() still stands.
If there was no requirement for updating a cached count, all the
overloads of splice could always have constant complexity.
Yep, that's the conflict.
I'm leaning in the direction of having splice() as guaranteed constant time.
For without it a list doesn't support much more functionality than a vector
(disregarding possible C++0x relaxation of assignable requirement for elements).
After all, how often does one insert and/or delete via 2 or more iterators at
the same time in the same list? And when there's just one iterator then a
vector, used as a cursor gap array, offers O(1) insert/delete of elements at
iterator position (keeping the sequence for other elements), as well as O(1)
read/write random access, better than the list.
That is, I think the original STL had it right.
Provided I have it right that the original STL had O(1) splice.
Cheers & hth.,
- Alf
--
Due to hosting requirements I need visits to <url: http://alfps.izfree.com/>.
No ads, and there is some C++ stuff! :-) Just going there is good. Linking
to it is even better! Thanks in advance!