Calling Erase with Iterator VS Const_Iterator

How can I implements erase( iterator erase(const_iterator first, const_iterator last)) of vector in c++

You don't need to reallocate the array; use move semantics instead. Even if you use the current implementation, you benefit from moving the values from the old array instead of copying them.

Furthermore it's more efficient for erase(const_iterator, const_iterator) to receive its own implementation.

Your actual problem here is the fact that you're invalidating the iterators by calling erase as noted by @UlrichEckhardt and even if you didn't reallocate the array, you'd need to call erase with first instead of it, since erasing the element at the current position of it shifts the remaining elements left by one resuling in the next element to be erased to be placed at the current position of it, not at the next position.

Here's a simplified vector implementation that should work:

template<class T>
class Vector
{
public:
    using iterator = T*;
    using const_iterator = T const*;

    Vector(std::initializer_list<T>&& list)
        : size(list.size()),
        objects(size == 0 ? nullptr : new T[size])
    {
        auto out = objects;
        for (auto& e : list)
        {
            *out = std::move(e);
            ++out;
        }
    }

    ~Vector()
    {
        delete[] objects;
    }

    iterator begin() noexcept
    {
        return objects;
    }

    iterator end() noexcept
    {
        return objects + size;
    }

    const_iterator cbegin() const noexcept
    {
        return objects;
    }

    const_iterator cend() const noexcept
    {
        return objects + size;
    }

    iterator erase(const_iterator pos)
    {
        auto const result = objects + std::distance(cbegin(), pos);
        auto const endIter = end();
        for (auto p = result; p != endIter;)
        {
            auto& lhs = *p;
            ++p;
            lhs = std::move(*p);
        }
        --size;
        return result;
    }

    iterator erase(const_iterator first, const_iterator last)
    {
        auto const result = objects + std::distance(cbegin(), first);
        if (first == last)
        {
            // empty delete sequence
            return result;
        }

        // shift the elements after last
        auto writeIter = result;
        auto readIter = objects + std::distance(cbegin(), last);

        for (auto const endIter = end(); readIter != endIter; ++writeIter, ++readIter)
        {
            *writeIter = std::move(*readIter);
        }
        // remove extra elements from the end
        size = std::distance(objects, writeIter);
        return result;
    }

private:
    size_t size;
    T* objects;
};

int main()
{
    {
        Vector<int> a = { 1, 2, 3, 4, 5 };

        auto iter = a.erase(a.cbegin() + 1, a.cend() - 1);
        std::cout << "element pointed to by returned value: " << *iter << '\n';
        for (auto i : a)
        {
            std::cout << i << '\n';
        }
    }

    {
        Vector<int> a = { 1, 2, 3, 4, 5 };

        auto iter = a.erase(a.cbegin() + 1);
        std::cout << "element pointed to by returned value: " << *iter << '\n';
        for (auto i : a)
        {
            std::cout << i << '\n';
        }
    }
}

Note: The loops in the member functions can be replaced by the overload of std::move taking iterators.

Why const_iterator could be used with std::map::erase

The behavior has changed from C++11; std::map::erase takes const_iterator as its parameter.

void erase( iterator pos );           // (until C++11)
iterator erase( const_iterator pos ); // (since C++11)
iterator erase( iterator pos );       // (since C++17)

For std::map::erase, the passed iterator is just used as the position where the element would be deleted, not for modifying the element through it. That means const_iterator would be fine. Before C++11, the support for const_iterator was not very good, but the situation has changed from C++11. You should use const_iterator instead of iterator when possible now.

Why is erasing via a const_iterator allowed in C++11?

erase and insert are non-const member functions of the collection. Non-const member functions are the right way to expose mutating operations.

The constness of the arguments are irrelevant; they aren't being used to modify anything. The collection can be modified because the collection is non-const (held in the hidden this argument).

Compare:

template <typename T>
std::vector<T>::iterator std::vector<T>::erase( std::vector<T>::const_iterator pos );
                                                                ^^^^^ ok

to a similar overload that is NOT allowed

template <typename T>
std::vector<T>::iterator std::vector<T>::erase( std::vector<T>::iterator pos ) const;
                                                                         wrong ^^^^^

Why were the std::vector::erase parameters changed to const_iterator?

The iterator just says where. The vector is non-const, and is from which it is erased.

This lets you find the location to be erased in a cost manner, and only when you actually erase it do you need a non const container.

Should I prefer iterators over const_iterators?

I totally agree with you.
I think the answer is simple:
Use const_iterators where const values are the right thing to use, and vice versa.
Seems to me that those who are against const_iterators must be against const in general...

Erasing an element of a vector that uses const_iterator

The error message:

no matching function for call to 'std::vector::erase(std::vector::const_iterator) const'

implies that vCars.begin() yields a const_iterator, which in turn implies that vCars is a constant object or reference. You are not allowed to modify the vector through that reference. If the function needs to modify the vector, it cannot take a constant reference.

Note that in a member function declared as const the implicit this pointer is of type T const * (i.e. you cannot modify the object inside a const function). If this is your case, you will need to drop the const qualifier from the function.

How to remove constness of const_iterator?

There is a solution with constant time complexity in C++11: for any sequence, associative, or unordered associative container (including all of the Standard Library containers), you can call the range-erase member function with an empty range:

template <typename Container, typename ConstIterator>
typename Container::iterator remove_constness(Container& c, ConstIterator it)
{
    return c.erase(it, it);
}

The range-erase member functions have a pair of const_iterator parameters, but they return an iterator. Because an empty range is provided, the call to erase does not change the contents of the container.

Hat tip to Howard Hinnant and Jon Kalb for this trick.

erase gets const_iterator but is called with iterator (non-const)

Yes, iterator of std containers is (and must be) convertible to const_iterator.

From the standard, $23.2.1/4 General container requirements [container.requirements.general] Table 100 — Container requirements:

(Emphasis mine)

X::iterator

any iterator category that meets the forward iterator requirements.
convertible to X::const_iterator.

What is the difference between const_iterator and non-const iterator in the C++ STL?

const_iterators don't allow you to change the values that they point to, regular iterators do.

As with all things in C++, always prefer const, unless there's a good reason to use regular iterators (i.e. you want to use the fact that they're not const to change the pointed-to value).

---

Related Topics