c++ - std::erase 如何为 vector 实现？

Question

我有一个自定义的 Vec 类，复制了 std::vector 的功能，但我无法实现一个删除函数，它采用与标准库实现相同的参数(并优雅地处理它们)。具体来说，在 C++11 中，vector::erase具有签名iterator erase (const_iterator position);，其中返回的迭代器指向元素删除后元素的新位置。我唯一的解决方案是传递一个非常量迭代器，用第二个迭代器将给定迭代器之后的所有元素复制回一个位置，并使用第三个迭代器存储原始指针位置。这需要三个非常量迭代器。

template <class T> typename Vec<T>::iterator Vec<T>::erase(iterator it)
{
    iterator copy_iterator = it; // used to shift elements one position to the left past the deleted element.

    iterator return_iterator = it; // holds original it position, per std implementation

    while (it != (this -> end() - 1)) { // copies elements one position left
        *copy_iterator++ = *++it;
    }

    alloc.destroy(it); // destroy last element in vector

    avail = it; // shortens the vector by 1

    return return_iterator;
}

这里的 avail 是一个迭代器，它指向一个 vector 的末尾，即 iterator end() { return avail; }。如果它必须将每个元素左移一个，我不明白任何这样的函数怎么可能采用 const_iterator，而且我真的不喜欢有三个迭代器。有更好的解决方案吗？

附加标准问题:

Up until C++98 , vector::erase 接受了一个迭代器参数。我很好奇为什么要更改此标准。在 C++11 中，删除函数包括看起来从 const_iterator 到迭代器的直接转换，而没有进一步解释为什么它现在是 const。

template <class T> typename vector<T>::iterator erase(const_iterator __position) {
    difference_type __ps = __position - cbegin();
    pointer __p = this->__begin_ + __ps;
    iterator __r = __make_iter(__p);
    this->__destruct_at_end(_VSTD::move(__p + 1, this->__end_, __p));
    return __r;
}

这是 Vec 类的部分实现:

template <class T> class Vec {
public:
    // typedefs

    Vec() { create(); }

    explicit Vec(std::size_t n, const T& val = T()) { create(n, val); }

    Vec(const Vec& v) { create(v.begin(), v.end()); } // copy constructor
    Vec& operator=(const Vec&);
    ~Vec() { uncreate(); } // destructor

    T& operator[](size_type i) { return data[i]; }
    const T& operator[](size_type i) const { return data[i]; }

    void push_back(const T& val) {
        if (avail == limit)
            grow();
        unchecked_append(val);
    }

    size_type size() const { return avail - data; }

    iterator begin() { return data; }
    const_iterator begin() const { return data; }

    iterator end() { return avail; }
    const_iterator end() const { return avail; }

    iterator erase(iterator);

private:
    iterator data;
    iterator avail;
    iterator limit;

    allocator<T> alloc;

    void create();
    void create(size_type, const T&);
    void create(const_iterator, const_iterator); // calls alloc.allocate, then copies without default initialization

    void uncreate(); // calls alloc.destroy on everything, then deallocates

    void grow(); // allocates twice the memory
    void unchecked_append(const T&);
};

Answer 1

只需将您的const_iterator 转换为函数内的iterator。现在，通常情况下，这是一个禁忌。但是因为我们知道 Vec 不是 const(因为 erase 是一个非常量函数)，这是安全的，除非用户传递了一个不属于的迭代器到 Vec(无论如何都不安全)。

那么，如何从 const_iterator 得到一个非常量 iterator 呢？您可以在 const_iterator 类中实现一个私有(private)成员来执行此操作并使 Vec 类成为友元。但由于我们正在处理随机访问迭代器，因此没有必要这样做，因为我们可以只使用迭代器算法。

// given a const_iterator cit
iterator it = begin() + (cit - begin());