Sparta::Buffer::erase(const iter&) should return updated iter reference

[timsnyder]

Discussed in #459

^{Originally posted by timsnyder December 18, 2023}
In

map/sparta/sparta/resources/Buffer.hpp

Lines 663 to 683 in e876f58

	/**
	* \brief erase the index at which the entry exists in the Buffer.
	* \param entry a reference to the entry to be erased.
	*/
	void erase(const const_iterator& entry)
	{
	sparta_assert(entry.attached_buffer_ == this, "Cannot erase an entry created by another Buffer");
	// erase the index in the actual buffer.
	erase(entry.getIndex_());
	}
	/**
	* \brief erase the index at which the entry exists in the Buffer.
	* \param entry a reference to the entry to be erased.
	*/
	void erase(const const_reverse_iterator& entry)
	{
	sparta_assert(entry.base().attached_buffer_ == this, "Cannot erase an entry created by another Buffer");
	// erase the index in the actual buffer.
	erase(entry.base().getIndex_());
	}

The return types of Sparta::Buffer::erase(const iter&) are void. Based on the STL semantics for erase(), I would expect them to return a copy of the iterator adjusted for the erasure. Does Sparta::Buffer::erase() invalidate the iterator?

For example, with a std::vector, I would expect to need to handle iterator invalidation something like:

#include <vector>


int main() {
    std::vector<int> junk = {1,3,5,7,9};

    for(auto itr = junk.begin(); itr != junk.end();) {
        if (*itr == 5) {
            itr = junk.erase(itr);
        } else {
            itr++;
        }
    }
}

Do I need to worry about the same type of thing with Sparta::Buffer or is the iterator somehow not invalidated by Sparta::Buffer::erase()?

[timsnyder]

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

map/sparta/sparta/resources/Buffer.hpp

Line 280 in 8b16b21

sparta_assert(attached_buffer_->numFree() > 0, "Incrementing the iterator to entry that is not valid");

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...

[timsnyder]

Also the warning comment at:

map/sparta/sparta/resources/Buffer.hpp

Lines 44 to 46 in 8b16b21

	* \warning Once an entry has been appended with appendEntry
	* method, the index with that data can only be erased via
	* the erase(BufferIterator&), and not the erase(uint32_t).

should probably have been removed at the same time the appendEntry method was removed from the class. It's confusing.

[klingaard]

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.

[timsnyder]

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

[klingaard]

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.

[timsnyder]

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?

[klingaard]

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 to
• An iterator can be cast to a const_iterator, but not the other way around
• Having erase take a const_iterator and returning a regular iterator allows a for loop with either type.
  • If erase returned a const_iterator, the user cannot re-assign to a non-const iterator

To 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.

[timsnyder]

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?

[klingaard]

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? 🤷‍♂️ 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.

[timsnyder]

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.

[klingaard]

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?

[klingaard]

Branch: knutel/issue_464_resource_enhancements

[klingaard]

Related issues:
#236
#238
#247

[timsnyder]

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).