c++ - 自制 vector 容器中的新c++放置

Question

这里有一些非常相似的问题，但是它们无法帮助我解决这个问题。
另外，我提供了完整的示例代码，因此其他人可能更容易理解。

我制作了一个 vector 容器(出于内存原因，不能使用STL)，过去只将operator =用于push_back *，一旦遇到新的放置位置，我便决定为其添加一个额外的“emplace_back” **。

*(T::operator =应该处理内存管理)

**(该名称取自我以后遇到的std::vector中的类似函数，我给它的原始名称是一个烂摊子)。

我读到一些有关在操作符new []上使用new放置的危险的东西，但无法弄清楚以下内容是否正确，如果不行，那是什么问题，我应该用什么代替，所以我d感谢您的帮助。

这可能是一个简化的代码，没有迭代器，也没有扩展功能，但这很重要:

template <class T>
class myVector {
public :
    myVector(int capacity_) {
        _capacity = capacity_;
        _data = new T[_capacity];
        _size = 0;
    }

    ~myVector() {
        delete[] _data;
    }

    bool push_back(T const & t) {
        if (_size >= _capacity) { return false; }
        _data[_size++] = t;
        return true;
    }

    template <class... Args>
    bool emplace_back(Args const & ... args) {
        if (_size >= _capacity) { return false; }
        _data[_size].~T();
        new (&_data[_size++]) T(args...);
        return true;
    }

    T * erase (T * p) {
        //assert(/*p is not aligned*/);
        if (p < begin() || p >= end()) { return end(); }
        if (p == &back()) { --_size; return end(); }
        *p = back();
        --_size;
        return p;
    }

    // The usual stuff (and more)
    int capacity()          { return _capacity;             }
    int size()              { return _size;                 }
    T * begin()             { return _data;                 }
    T * end()               { return _data + _size;         }
    T const * begin() const { return _data;                 }
    T const * end()   const { return _data + _size;         }
    T & front()             { return *begin();              }
    T & back()              { return *(end() - 1);          }
    T const & front() const { return *begin();              }
    T const & back() const  { return *(end() - 1);          }
    T & operator[] (int i)  { return _data[i];              }
    T const & operator[] (int i) const { return _data[i];   }
private:
    T * _data;
    int _capacity;
    int _size;
};

谢谢

Answer 1

I read some stuff about the danger of using placement new over operator new[] but couldn't figure out if the following is ok or not, and if not, what's wrong with it [...]

对于 operator new[]和new的放置，如果将这两种策略混合在一起，则只会非常糟糕(就像通常的疯狂类型的未定义行为一样)。

通常，您必须做出的主要选择是使用一个或另一个。如果使用 operator new[]，那么您将预先为容器的整个容量构造所有元素，并使用 push_back之类的方法覆盖它们。使用 erase之类的方法删除它们时，您不会销毁它们，只是将它们保留在其中并调整大小，覆盖元素等等。您都可以使用 operator new[]一次性构造并分配多个元素，并使用 operator delete[]一次性销毁和取消分配它们。

为什么将新的展示位置用于标准容器

首先要了解的是，如果要开始滚动自己的 vector 或其他符合标准的序列(不是简单地将结构与每个节点的一个元素链接在一起)，而实际上是在删除元素时破坏它们，那就构造元素(而不仅仅是覆盖)(添加时)是为了分开为容器分配内存并为它构造元素的想法。因此，恰恰相反，在这种情况下，新的放置位置还不错。达到标准容器的一般质量是基本必要。但是在这种情况下，我们不能将其与 operator new[]和 operator delete[]混合使用。

例如，您可能分配了内存以在 reserve中容纳100个T实例，但是您也不想默认构造它们。您想使用 push_back， insert， resize， fill ctor， range ctor， copy ctor等方法来构造它们-这些方法实际上会添加元素，而不仅仅是添加它们的能力。这就是为什么我们需要新的位置。

否则，我们将失去 std::vector的通用性，它避免了构建不存在的元素，可以在 push_backs中复制构造，而不是简单地用 operator=覆盖现有元素，等等。

因此，让我们从构造函数开始:

_data = new T[_capacity];

...这将为所有元素调用默认构造函数。我们不希望这样做(默认的ctor要求和费用都没有)，因为使用 placement new的全部目的是在分配的内存中构造元素，而这已经构造了所有元素。否则，任何在任何地方使用new的放置都将尝试第二次构造已经构造的元素，并将其称为UB。

相反，您想要这样的事情:

_data = static_cast<T*>(malloc(_capacity * sizeof(T)));

这只是给我们一个原始的字节块。

其次，对于 push_back，您正在执行以下操作:

_data[_size++] = t;

尝试使用赋值运算符，并在我们先前的修改之后，在尚未构造的未初始化/无效元素上使用。所以我们想要:

new(_data + _size) T(t);
++size;

...使其使用拷贝构造函数。它使其与 push_back实际应该执行的操作相匹配:在序列中创建新元素，而不是简单地覆盖现有元素。

如果要处理从容器中间移出的内容，则擦除方法甚至需要在基本逻辑级别上进行一些工作。但是仅从资源管理的角度来看，如果您使用new放置，则要手动为删除的元素调用析构函数。例如:

if (p == &back()) { --_size; return end(); }

...应该更像是:

if (p == &back())
{
    --size;
    (_data + _size)->~T();
    return end(); 
}

您的 emplace_back手动调用析构函数，但不应这样做。 emplace_back应该仅添加而不是删除(并销毁)现有元素。它应该与 push_back非常相似，但只需调用move ctor。

您的析构函数将执行以下操作:

~myVector() {
   delete[] _data;
}

但是，当我们采用这种方法时，那就是UB。我们想要更多类似的东西:

~myVector() {
   for (int j=0; j < _size; ++j)
      (_data + j)->~T();
   free(_data);
}

像异常安全这样的蠕虫完全不同，还有很多要覆盖的内容。

但这应该使您开始着手正确使用数据结构中的某些内存分配器(本例中为 malloc/free)。

最后但并非最不重要的:

(couldn't use stl for memory reasons)

...这可能是不寻常的原因。您的实现不一定要比事先调用了 vector的 reserve为其分配适当的 capacity所使用的内存少。您可以通过选择32位整数而无需为每个容器级别(而不是每个元素级别)节省一些字节，而无需存储分配器，但这将节省非常小的内存换来很多工作。

这种事情可能是有用的学习练习，尽管它可以帮助您以更符合标准的方式在标准之外构建一些数据结构(例如:展开列表，我觉得非常有用)。

由于ABI的原因，我最终不得不重新发明一些 vectors和类似 vector 的容器(我们想要一个可以通过我们的API传递的容器，无论使用什么编译器来构建插件，我们都必须保证该容器具有相同的ABI)。即使那样，我也更愿意仅使用 std::vector。

请注意，如果只想控制 vector分配内存的方式，则可以通过使用兼容接口(interface)指定自己的分配器来实现。例如，如果您想要一个 vector来分配128位对齐的内存以便与使用SIMD的对齐移动指令一起使用，这可能会很有用。