C++ vector 实现 push_front 错误

Question

在用 C++ 实现基本 vector 时，我在 push_front 问题(下)中遇到问题 _Alloc 是分配器类，content_ 是指向数据的指针，size_ 和capacity_ 是他们所说的，而 empty() 是检查指针是否为空的函数或不。 (指针类型为value_type *)

测试:

vector<int> v;
for (int i = 1; i <= 25; ++i)
{
    v.push_front(i);
}
for (auto &a : v)
{
    std::cout << a << "\n";
}

输出:

25

24

24

24

24

24

24

24

24

24

24

24

24

24

24

24

24

24

24

24

24

24

24

24

24

---

_Myt &push_front(const value_type &_Value)
{
    if (++size_ >= capacity_)
    {
        reserve(capacity_ * 2);
    }
    int pos = 1;
    if (!empty())
    {
        pointer tmp = content_; // for the values
        for (iterator i = begin(); i != end(); ++i, ++pos)
        {
            _Alloc().destroy(i); // destroy the current
            _Alloc().construct(&content_[pos], buf[pos - 1]); // add the value in into the next position
        }
    }
    _Alloc().construct(&content_[0], _Value); // put _Value to the front
    return *this;
}

---

问题是什么(我的代码)？

Answer 1

首先，您的代码非常困惑，因为您使用了两个复制循环中的变量。因为 pos 总是索引一个在迭代器 i 后面，你在复制之前破坏了值它了一个。如果类型有一个微不足道的，哪个会起作用析构函数，但一般不会工作。做循环正确地，当两个目标都必须使用赋值源是构造元素，拷贝否则构造函数。

但最大的问题是你抄错了方向。为此，您需要从最高到最低复制重叠复制工作。

编辑:

粗略地说:最简单的实现将包含三个指针:begin、end和top，对应start数据，初始化数据的末尾和顶部可用(已分配)内存。把一切都移回去一个元素(假设不为空):

std::uninitialized_copy( end - 1, end, end );
++ end;
std::copy_backward( begin, end - 2, end - 1 );

(请注意，这是通用的。将 1 更改为您拥有的任意数量向后移动，然后 begin 到插入点，您就得到了通用插件。另一方面，它不使用construct 分配器函数；为此，你必须实现您自己的 uninitialized_copy 版本。)

另请注意，end 在新元素之后发生了变化构建，但在 copy_backward 之前。对于推理这背后:想想如果 build 新元素抛出异常。或者，如果其中一个分配抛出异常。然后您尝试破坏该对象。如果您过早地增加 end，您将尝试破坏一个未完全构建的对象；迟到了，你不会销毁所有已完全构建的对象。

如果您想写出拷贝(出于教学原因):

_Alloc().construct( end, *(end - 1) );
++ end;
for ( auto current = end - 2; current != begin; -- current ) {
    *(current + 1) = (current);
}

重要的是1)构造到新分配的元素，但在将一个元素移动到时分配 (copy)另一个已经构建的元素，以及 2) 确保你永远不要将一个值移动到一个本身还没有的元素中感动了。这第二点意味着当向下移动时，你从较低的地址开始(这将对应于元素被删除，因此可以被覆盖)，以及何时向上移动，你从更高的元素开始(最高的它将被移动到新的内存中，从而复制构造)。