Open timsnyder opened 8 months ago
Looking more at the code, Sparta::Buffer::erase(iterator&)
does seem to invalidate the iterator and I don't know how one would write an iterator loop of Sparta::Buffer
that uses erase(iterator&)
without it returning a reference to the subsequent element.
I'm also struggling to understand https://github.com/sparcians/map/blob/8b16b216de9960cacdc22d78820165ab86d6de58/sparta/sparta/resources/Buffer.hpp#L280
Why isn't the assertion firing based on IsValid()
? I would think that trying to increment or decrement an invalid iterator would be an indication of a usage error. I definitely don't understand needing free elements in the attached buffer when incrementing an invalid iterator...
Also the warning comment at: https://github.com/sparcians/map/blob/8b16b216de9960cacdc22d78820165ab86d6de58/sparta/sparta/resources/Buffer.hpp#L44-L46
should probably have been removed at the same time the appendEntry
method was removed from the class. It's confusing.
I started work on this, but since you've taken it on, I'll abandon the 5 minutes of effort I put into it. There are other changes to other resources I'd like to bundle with your changes, so I'll work on those separately (see #463 ).
Glad you're looking into this. Admittedly, I've never really looked at this code since Steven built it many years ago. Ain't broke...don't fix.
I only added some more detail and created the bug. Probably won't be able to look into a fix anytime soon. I've told people to work around it for now by not using the iterators and just use integer indices.
So, don't let my comments keep you from looking at this. If I get a chance to actually work on it, I'll assign it to myself
Ok, I started branch knutel/issue_464_resource_enhancements
with the basics of returning an iterator from erase, but it's not quite right yet. I added testing and it works, but the semantics are wrong. For example, if given a const_iterator
,erase
isn't supposed to return a const_iterator
me thinks, but a standard iterator
instead.
Yeah. If only based on what std:::vector::erase()
does, iterator erase(const_iterator)
would be aligned but I have to admit I'm not sure I understand why the STL does it that way out why it would be correct...
const_iterator
prevents you from changing the element pointed to but not from erasing that element from the container. Why if you are iterating a container with a const_iterator
would you want erase(const_iterator)
to give you back a iterator
that can be used to modify the element after the erased one? How does this not violate the point of having const_iterator
?
I totally agree with your observations; it confused me too. Here are my thoughts on why erase
has this signature:
erase
is technically only changing the container, not the object being pointed toiterator
can be cast to a const_iterator
, but not the other way arounderase
take a const_iterator
and returning a regular iterator
allows a for
loop with either type.
erase
returned a const_iterator
, the user cannot re-assign to a non-const iteratorTo make Buffer
work this way requires a little C++ magic. I'm still pondering on this, but probably will need to add a little metafunction magic to make it work.
I follow the fact that erase
is modifying the container and the const_iterator
is const
on the thing it is pointing to. You can only call erase
on a non-const container.
Second bullet is a helpful reminder, yes, const casting is uni-directional.
Third bullet would make sense to me if there was only a single implementation of erase
that takes a const_iterator
and returns iterator
but in the sparta code, there is... OH WAIT, I'm confusing my implementations, we only have two implementations of erase
that take iterators (const_iterator
and const_reverse_iterator
) and one that takes an integer index.
The thing I was really getting confused by is why C++Reference was seeming to imply that there are two implementations of std::vector::erase
, one that takes iterator
and returns iterator
and another that takes const_iterator
and returns iterator
. However, I was missing their annotations on the right side of the page that says allowing const_iterator
as a parameter is since C++11 and the iterator
parameter only is before C++11. I've read up on that change and it relates to your first point that erase
is modifying the container, not the element const_iterator
points to.
I also looked at the latest doxygen for GNU libstdc++ at https://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/a08551.html and it does seem to indicate that there is only constexpr iterator erase(const_iterator)
.
At this point, I'm only confused as to why you wouldn't have const_iterator erase(const_iterator)
AND iterator erase(iterator)
. It makes sense to me that the typical pattern will likely be something like:
for (const_iterator itr = buffer.start(); itr != buffer.end();) {
if (something) {
itr = buffer.erase(itr);
} else {
itr++;
}
}
and the assignment of itr = buffer.erase(itr)
will implicitly cast the returned iterator
to const_iterator
and everything is fine.
What prevents someone from doing something really idiotic like:
for (const_iterator itr = buffer.start(); itr != buffer.end();) {
if (something) {
iterator mutable_itr = buffer.erase(itr);
// aha! Now I can be nefarious and modify the element mutable_itr points to!
itr = mutable_itr;
} else {
itr++;
}
}
Any thoughts on why you wouldn't have two implementations of erase
in order to maintain the const
correctness of their context?
Why isn't the assertion firing based on
IsValid()
? I would think that trying to increment or decrement an invalid iterator would be an indication of a usage error. I definitely don't understand needing free elements in the attached buffer when incrementing an invalid iterator...
I have no idea why the code was written this way. Maybe Steven had something in mind, then changed gears half way through? :man_shrugging: I think the better approach to this method -- if the iterator isn't valid, you can' increment it. Period. The way the code is written allows a user to increment a invalid iterator all day long, but NOTHING happens if the buffer has valid entries. It's ... weird.
To your second points...
At this point, I'm only confused as to why you wouldn't have const_iterator erase(const_iterator) AND iterator erase(iterator).
I think it might be pure laziness. To erase an element from a container, you just need the reference to the item you want to erase (for the container to find it). It can be const or not -- doesn't matter. The return also doesn't matter. Heck, if you can call erase
you can easily muck with the contents of the container. And since erase
is a non-const method, its safe to return non-const stuff all day long.
I tried following the STL pattern for erase, but this will take a little more effort than I thought. I need to make a non-const iterator given a const one. Ech.
Thanks for your replies. I'm glad it's not just me missing something.
For the record, I think Dilip added to the goofiness to the increment operator when he added the reverse iterators.
I managed to get erase
to working following the pattern in STL. I also added testing, but I'm not 100% convinced yet. I'm battling the reverse_iterator
version now, but will take a break. Maybe you or someone else might want to continue hammering on this?
Looking at the code on https://github.com/sparcians/map/tree/knutel/issue_464_resource_enhancements, I think it might be an improvement if void erase(uint32_t)
became uint32_t erase(uint32_t)
and the integer indexed erase()
returns the index of the next item in the container when you erase it. Doing this would free the caller of needing to know whether erase(uint_32t)
shifts the indices or not. Just a thought. I have no idea of whether the STL does this for erase()
by index.
Update: std::vector::erase()
only erases via iterators, so it isn't any help here. If my thoughts about erase(uint32_t)
needing to return the index for the next element (which for Sparta::Buffer
is the same index it was called with) don't make sense to others, I think there needs to at least be a comment about why constructing the returned iterator
with the same index makes sense for Sparta::Buffer()
(since it collapses and indexes based on only the valid entries).
Discussed in https://github.com/sparcians/map/discussions/459