c++ - vector::insert 是否只允许保留一次并避免进一步的容量检查？

Question

vector::insert(dst_iterator, src_begin, src_end)(插入范围)可以针对随机访问迭代器进行优化，以保留所需的容量 src_end - src_begin 首先，然后执行复制。

主要问题我有:标准是否还允许 vector::insert 避免对每个复制元素进行容量检查？ (即不在要插入的每个元素上使用 push_back 或类似的)

我将避免这种容量检查称为“insert 的优化”。

---

可能出了什么问题:我可以想象一个在取消引用时会产生副作用的迭代器:

注意:标准保证传递给 insert 的迭代器将被取消引用一次(见问题结尾)。

#include <vector>
#include <iterator>
#include <iostream>

template < typename T >
struct evil_iterator : std::iterator < std::random_access_iterator_tag, T >
{
    using base = std::iterator < std::random_access_iterator_tag, T >;

    std::vector<T>* evil_feedback;
    typename std::vector<T>::iterator innocent_iterator;

    evil_iterator( std::vector<T>* c,
                   typename std::vector<T>::iterator i )
        : evil_feedback{c}
        , innocent_iterator{i}
    {}

    void do_evil()
    {
        std::cout << "trying to do evil; ";
        std::cout << "cap: " << evil_feedback->capacity() << ", ";
        std::cout << "size: " << evil_feedback->size() << ", ";

        // better not invalidate the iterators of `*evil_feedback`
        // passed to the `insert` call (see example below)
        if( evil_feedback->capacity() > evil_feedback->size() )
        {
            evil_feedback->push_back( T{} );
            // capacity() might be == size() now
            std::cout << "successful >:]" << std::endl;
        }else
        {
            std::cout << "failed >:[" << std::endl;
        }
    }

    T& operator*()
    {
        do_evil();  // <----------------------------------------
        return *innocent_iterator;
    }


    // non-evil iterator member functions-----------------------

    evil_iterator& operator++()
    {
        ++innocent_iterator;
        return *this;
    }
    evil_iterator& operator++(int)
    {
        evil_iterator temp(*this);
        ++(*this);
        return temp;
    }


    evil_iterator& operator+=(typename base::difference_type p)
    {
        innocent_iterator += p;
        return *this;
    }
    evil_iterator& operator-=(typename base::difference_type p)
    {
        innocent_iterator -= p;
        return *this;
    }

    evil_iterator& operator=(evil_iterator const& other)
    {
        evil_feedback = other.evil_feedback;
        innocent_iterator = other.innocent_iterator;
        return *this;
    }

    evil_iterator operator+(typename base::difference_type p)
    {
        evil_iterator temp(*this);
        temp += p;
        return temp;
    }
    evil_iterator operator-(typename base::difference_type p)
    {
        evil_iterator temp(*this);
        temp -= p;
        return temp;
    }

    typename base::difference_type operator-(evil_iterator const& p)
    {
        return this->innocent_iterator - p.innocent_iterator;
    }

    bool operator!=(evil_iterator const& other) const
    {  return innocent_iterator != other.innocent_iterator;  }
};

例子:

int main()
{
    std::vector<int> src = {3, 4, 5, 6};
    std::vector<int> dst = {1, 2};

    evil_iterator<int> beg = {&dst, src.begin()};
    evil_iterator<int> end = {&dst, src.end()};

    // explicit call to reserve, see below
    dst.reserve( dst.size() + src.size() );
    // using dst.end()-1, which stays valid during `push_back`,
    //   thanks to Ben Voigt pointing this out
    dst.insert(dst.end()-1, beg, end);  // <--------------- doing evil?

    std::copy(dst.begin(), dst.end(), 
              std::ostream_iterator<int>{std::cout, ", "});
}

---

问题:

1. 能否优化 vector::insert 以避免对每个插入元素进行容量检查？
2. evil_iterator 仍然是有效的迭代器吗？
3. 如果是，是 evil_iterator evil，即如果 insert 如上所述进行优化，是否会导致 UB/不合规行为？

也许我的 do_evil 不够邪恶.. 在 clang++ 3.2 上没有问题(使用 libstdc++):

编辑 2:添加了对 reserve 的调用。现在，我在做坏事:)

trying to do evil; cap: 6, size: 2, successful >:]
trying to do evil; cap: 6, size: 3, successful >:]
trying to do evil; cap: 6, size: 4, successful >:]
trying to do evil; cap: 6, size: 9, failed >:[
1, 3, 4, 5, 6, 0, 0, 135097, 2,

编辑:为什么我认为优化会破坏这一点:

1. 在开头考虑 dst.size() == dst.capacity() == 2。
2. 对 insert 的调用需要 6 个新容量。
3. 优化将容量扩大到正好 6，然后通过从 src 迭代器(beg，end)复制开始插入元素.
4. 此复制是在不进行容量检查的循环中完成的。 (这就是优化。)
5. 在复制过程中，在 do_evil 中将更多元素添加到 vector 中(不会使迭代器无效)。现在的容量已不足以容纳其余要复制的元素。

也许您必须在示例中明确使用 reserve 来强制更新可观察的 capacity，然后再使用 do_evil。目前，insert 可以保留一些容量，但只有在复制完成后才能更改 capacity 返回的内容(即可观察容量)。

---

到目前为止，我在标准中发现的内容似乎允许优化 insert:

[sequence.reqmts]/3

a.insert(p,i,j) [...]

Requires: T shall be EmplaceConstructible into X from *i.

For vector, if the iterator does not meet the forward iterator requirements (24.2.5), T shall also be MoveInsertable into X and MoveAssignable. Each iterator in the range [i,j) shall be dereferenced exactly once.

pre: i and j are not iterators into a. Inserts copies of elements in [i, j) before p

[vector.modifiers] on insert

1 Remarks: Causes reallocation if the new size is greater than the old capacity. If no reallocation happens, all the iterators and references before the insertion point remain valid. If an exception is thrown other than by the copy constructor, move constructor, assignment operator, or move assignment operator of T or by any InputIterator operation there are no effects. If an exception is thrown by the move constructor of a non-CopyInsertable T, the effects are unspecified.

2 Complexity: The complexity is linear in the number of elements inserted plus the distance to the end of the vector.

Answer 1

再看一遍，我认为这条规则(第 17.6.4.9 节)更明确地禁止了你试图做的事情:

Each of the following applies to all arguments to functions defined in the C++ standard library, unless explicitly stated otherwise.

• If an argument to a function has an invalid value (such as a value outside the domain of the function or a pointer invalid for its intended use), the behavior is undefined.

我认为这条规则在函数调用的整个过程中都适用，而不仅仅是在函数入口处。

此外，push_back() 保证 (23.3.7.5):

If no reallocation happens, all the iterators and references before the insertion point remain valid.

您的 position 传递给 insert，即 dst.end() 在 insert 调用之前进行评估, 不在第一个 evil_feedback->push_back() 调用的插入点之前，因此它不会保持有效(您在这里小心避免重新分配的事实并没有保存你，因为你只满足了一半的条件)。这意味着您传递给 C++ 标准库中定义的函数 std::vector::insert 的参数在该调用期间无效，从而使您直接进入未定义行为的领域。

---

上一个答案:

我认为你违反了你引用的这个先决条件:

pre: i and j are not iterators into a.