首页 文章

如何为向量实现std :: erase？

提问于
浏览 次
0

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

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;
}

这里有一个迭代器，它指向一个超过向量末尾的迭代器，即 iterator end() { return avail; } . 我不喜欢有三个迭代器 . 有更好的解决方案吗？

Additional Standards Question:

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&);
};
c++ c++11 vector stl iterator

2 回答

  • 1

    只需将 const_iterator 转换为函数内的 iterator 即可 . 现在，通常情况下，这将是禁忌 . 但是因为我们知道 Vec 不是const（因为 erase 是一个非const函数），所以这是安全的，除非用户传递的迭代器不属于 Vec （无论如何都不安全） .

    那么，如何从 const_iterator 获得非const iterator ？您可以在 const_iterator 类中实现一个私有成员来执行此操作，并使 Vec 类成为朋友 . 但是因为我们正在处理随机访问迭代器，所以这是不必要的，因为我们可以只使用迭代器算法 .

    // given a const_iterator cit
iterator it = begin() + (cit - begin());
    回复于
  • 3

    我不知道最好的答案，但从我可以看到你可以使用指针算法将非常量指针/迭代器重新导出到擦除位置，或者在知道你的数组实际上是真实的时候做一个合法的 const_cast 安全（创建 non-const ）因为erase是一个非const函数，无法在const对象上调用 .

    template <class T> typename Vec<T>::iterator Vec<T>::erase(const_iterator it)
{
    iterator non_const_it = this->begin() + std::distance(this->cbegin(), it);

    iterator copy_iterator = non_const_it;

    // etc...

    return non_const_it;
}
    回复于

相关问题