如何在C ++中实现对向量的擦除 [英] How to implement erase on vector in c++

问题描述

从Accelerated C++: Practical Programming by Example中学习，在第11章中，有一个STL矢量容器的实现(仅具有基本功能).之后，就像std :: vector一样，练习实现erase函数.我尝试过的:

Learning from Accelerated C++: Practical Programming by Example, in chapter 11, there was an implementation (only with basic features) of vector container from STL. After that was an exercise for implementing erase function just as std::vector does. What I have tried:

#include <memory>
template<class T>
class Vec{
private:
   T *data;
   T *avail;
   T *limit;
   std::allocator<T> alloc;
   ...

public:
   explicit Vec(size_t n, const T &val = T())
   {
      create(n, val);
   }
   T *const begin()
   {
      return data;
   }
   T *const end()
   {
      return avail;
   }
   T *erase(T* const pos);
   ...
};

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

// 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())
   {
      size_t member = i-data;
      size_t size = limit-data;
      T* new_data = alloc.allocate(size);
      std::uninitialized_copy(data, i, new_data);
      T* new_avail = std::uninitialized_copy(i+1, avail, i);
      data = new_data;
      avail = new_avail;
      limit = data + size;
      return &data[member];
   }
   else
   {
      return 0;
   }
}

现在，如果我想检查一下，该功能是否正常工作:

Now If I want to check, if that function works correctly:

#include "vec.hpp"
int main()
{
    Vec<int> v(5, 2);
    if (v.erase(v.begin()+2))
    {
        for (int i:v)
        {
            cout << i << endl;
        }
    }
}

我知道

...
0
0
0
0
Segmentation fault

我以某种方式制作了无限分配循环，但我不知道如何.无论如何，如何通过std::uninitialized_copy进行擦除功能(或换句话说，如何将元素从左移到左)?

I have somehow made infinity allocation-loop, but I have no idea how. Anyway, How can I make the erase function (or in another words, how to shift elements after the erased one to left), via std::uninitialized_copy?

整个类的定义在那里:

the whole class definition is there:

https://www.codepile.net/pile/rLmz8wRq

推荐答案

在此处创建矢量的新存储:

Here you create new storage for vector:

 T* new_data = alloc.allocate(size);

，然后在这里写入由参数指向的数组，该数组(据说)指向旧存储上的位置. new_avail会指向旧存储.

and here you write to array pointed by argument, which (supposedly) points to location on old storage. new_avail would point to old storage.

 T* new_avail = std::uninitialized_copy(i+1, avail, i);
                                                    ^ that's destination
                                        ^ that's source

那你甚至会泄漏内存:

 data = new_data;   // old storage pointed by data is lost along with the "tail" of array

此向量状态完全破坏后，指针算法将转到未定义的区域:

After this vector state is completely broken, pointer arithmetic go to undefined area:

 avail = new_avail;  // avail points to old storage, data points to new one.
                     // (data < avail) no longer guaranteed to be true

由于data可能大于avail，因此您不会遇到无限循环，可能会遇到很长的循环.或可能不会.尝试在此擦除"之后遍历向量.等于未定义行为.

Because in all likelihood data would be greater than avail, you don't get an infinite loop, you may get a very long one. OR may not. Attempt to iterate through vector after this "erase" amounts to Undefined Behavior.

这篇关于如何在C ++中实现对向量的擦除的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！