c++ - 如何在 C++ 容器中向左移动元素(以实现删除)？

Question

来自我之前的问题:How to implement erase on vector in c++ ，我已经尝试实现 erase通过分配新内存，并将除删除之外的所有元素复制到新数组。从答案来看，这不是 STL 中 vector 的标准方式，其中 vector 保持旧元素不变，并且仅在删除元素后将元素移回(这是先前迭代器“无效”的一部分。所以我试图使用 std::move():

#ifndef _vec_h
#define _vec_h

#include <stddef.h>
#include <memory>
#include <algorithm>

template<class T>
class Vec
{
public:
    typedef T* iterator;
    typedef T* const const_iterator;
    typedef T value_type;

    Vec() {
        create();
    }
    explicit Vec(size_t n, const T& val = T()) {
        create(n, val);
    }
    Vec(const Vec& v) {
        create(v.begin(), v.end());
    }
    Vec& operator=(const Vec& v);
    ~Vec() {
        uncreate();
    }
    T& operator[](size_t i) {
        return data[i];
    }
    const T& operator[](size_t i) const {
        return data[i];
    }
    void push_back(const T& val);
    size_t 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;
    }
    void clear() {
        if (data)
        {
            for (iterator i=avail; i!=data; i--)
                i->~T();
        }
        avail=data;
    }
    std::allocator<T> alloc;

private:
    iterator data;
    iterator avail;
    iterator limit;

    void create();
    void create(size_t n, const T& val);
    void create(const_iterator b, const_iterator e);
    void uncreate();
    void grow();
    void unchecked_append(const T& val);
};


template<class T> Vec<T>& Vec<T>::operator=(const Vec& rhs)
{
    if (&rhs != this)
    {
        uncreate();
        create(rhs.begin(), rhs.end());
    }
    return *this;
}

template<class T> void Vec<T>::push_back(const T& val)
{
    if (avail == limit)
    {
        grow();
    }
    unchecked_append(val);
}

template<class T> void Vec<T>::create()
{
    data = avail = limit = 0;
}

template<class T> void Vec<T>::create(size_t n, const T& val)
{
    data = alloc.allocate(n);
    limit = avail = data + n;
    std::uninitialized_fill(data, limit, val);
}

template<class T> void Vec<T>::create(const_iterator i, const_iterator j)
{
    data = alloc.allocate(j-i);
    limit = avail = std::uninitialized_copy(i, j, data);
}

template<class T> void Vec<T>::uncreate()
{
    if (data)
    {
        iterator i = avail;
        while (i!=data)
        {
            alloc.destroy(--i);
        }
        alloc.deallocate(data, limit-data);
    }
    data=limit=avail=0;
}

template<class T> void Vec<T>::grow()
{
    size_t new_size = std::max(2*(limit-data), ptrdiff_t(1));
    iterator new_data = alloc.allocate(new_size);
    iterator new_avail = std::uninitialized_copy(data, avail, new_data);
    uncreate();
    data = new_data;
    avail = new_avail;
    limit = data + new_size;
}

template<class T> void Vec<T>::unchecked_append(const T& val)
{
    alloc.construct(avail++, val);
}
    //---------------------------------------------------------
    // here I am trying to implement the erase function with 3 pointers (data, avail, limit)
    template<class T>
    T* Vec<T>::erase(T *const i)
    {
       if(i==end())
       {
           return end();
       }
       else if(i >= begin() && i < end())
       {
          std::move(i+1, avail, i); //shift elements to the left
          return i;
       }
       else
       {
          return 0;
       }
    }

#endif

这仍然会导致段错误。那么有什么办法，如何实现 erase ?

Answer 1

为了编译，我需要添加这个方法声明:

T* erase(T *const i);

我添加了一些快速测试代码来重新创建您的段错误:

int main()
{
  Vec<int> test;
  test.push_back(1);
  test.push_back(2);
  test.push_back(3);
  test.push_back(4);
  test.erase(test.begin() + 2);
  std::cout << test[2] << std::endl; // should output 4
}

但是，代码按预期输出了 4，我没有得到任何段错误。我尝试在 valgrind 中运行，也没有出现任何内存错误。它似乎按您的预期工作，但是如果您添加一些代码来重新创建段错误，我将使用修复程序更新答案。