在扩展期间将向量成员推入向量：vector.push_back(vector[0])。

Question

我正在C++中编写自定义向量类。我有一个关于以下代码的问题：

    vector<T> vec;
    vec.push_back(one);
    vec.push_back(two);
    vec.push_back(vec[0]);

push_back的定义如下：

    void push_back(const T & v)

为避免不必要的复制。它的实现看起来像是：

    if (size == capacity)
    {
        allocate new storage
        copy old values into new storage
        // 2
        delete old storage
        fix pointers and counters
    }
    // 1
    copy v at the end of storage

如果我们想要推送已经存在于向量中且向量需要扩展（大小等于其容量）的元素，问题就会出现。如果我们这样做（vec.push_back(vec[0])），那么在// 1处它已经被释放了。因此，我们需要有一个副本。另一种选择是在扩展期间添加它，例如在// 2处，但这看起来不太美观。

你会如何解决这个问题？

- John

---

我会在你的 //2 处处理它 - 有什么不好的呢？一个代码路径用于“正常”情况，另一个用于异常。 - Erik

在函数的最后一刻之前，请不要删除旧存储。 - user2100815

顺便问一句，你为什么不重新分配内存呢？ realloc（）保证会保留旧块的数据，所以如果你正在使用索引而不是指针，那么应该没问题。 - Gunther Piez

@drhirsch：只有在使用malloc和free管理内存，并且对象被限制为POD类型时，才能使用realloc。 - Mike Seymour

@drhirsh - realloc 只有在可能的情况下才会保留数据位置。当堆的下一个部分已经被占用时，它将重新分配并复制数据（以一种与非 POD 类型不兼容的方式）。 - Bo Persson

@Bo Persson: 我没有写任何关于保留数据的内容。当然，我知道它可能随意移动数据。 - Gunther Piez

Answer 1

在某些STL实现中（例如当前的VS2010），它们首先会检查要添加的新数据项的指针是否在向量缓冲区的当前范围内。

如果是，将找到数据在向量中的索引位置（而不是指针！）。即使基础缓冲区被重新分配，这也不会改变。一旦扩展缓冲区（无论是否涉及实际重新分配），数据项就可以安全地从索引位置复制。

另一个选择是，在重新分配缓冲区之前，仅取要添加的数据项的本地（堆栈）副本，以防项目位于向量内部。显然，如果数据类型非常难以复制（例如另一个向量？？），那么这可能不是一个好主意。

希望这有所帮助。

- Darren Engwirda

---

我在思考并发现保留索引位置的一个缺陷。考虑结构体向量 struct foo { int a, b, c, d; }。Foo 的长度为 16 字节。使用强制类型转换，我可以在 ((char*)vector_start + 8) 处添加对象 -- 其中 a = v[0].c, b = v[0].d, c = v[1].a, d = v[1].b。这很粗糙但是可行的。 - John

是的，我认为这很粗糙。我不太了解标准，但如果允许这种容器的使用方式，我会很惊讶。我认为您应该只push_back()真正的数据项，而不仅仅是任意字节。像这样的C样式转换（顺便说一下，你还需要将其转换回vector::value_type！）即使对于一般的C++对象类型也会产生问题，尽管它可能对于你构造的特殊情况有意义。 - Darren Engwirda

Answer 2

考虑异常安全性：如果内存分配或对象复制失败会发生什么？您应该尽可能使您的类在这种情况下表现得尽可能好。考虑以下保证：

- 没有保证：如果出现问题，则对象可能处于无效状态。 - 弱保证：如果出现问题，则对象处于未定义但有效的状态。 - 强保证：如果出现问题，则对象不变。 - “无异常”保证：不会出现任何问题。

由于您无法控制内存分配器或要复制的对象，因此无法实现最后一个。然而，使用两阶段方法可以实现“强”保证：以不影响可见状态的方式完成可能失败的工作；一旦成功，使用无法失败的操作（例如更新指针和删除旧内存 - 如果删除提供“无异常”保证，通常应该这样做）来更新持久状态。

因此，更具异常安全性的版本可能如下所示：

if (new_size > capacity) {
    allocate new storage, controlled by a local smart pointer
    copy old values
    copy new values
    update state, releasing the smart pointer
    delete old storage
} else {
    copy new values
}

这里的“else”情况只提供“弱”保证：如果任何对象无法复制，则可能已复制部分但不是全部新数据。要改进这一点将会有成本，无论是在复杂性方面（提供一种在失败时“撤销”更改的方法），还是在速度和内存方面（使用重新分配版本，无论是否已经有足够的内存）。

- Mike Seymour

Answer 3

我建议暂时不要删除旧存储：

if (size == capacity)
    {
        allocate new storage
        copy old values into new storage
        fix pointers and counters, but keep one pointer at the old storage
    }
    copy v at the end of storage
    delete old storage

- Gunther Piez