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 邪恶的,即如果insert如上所述进行优化,它是否会导致UB /不符合行为？

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

编辑2:添加了呼叫reserve.现在,我在做邪恶:)

试图做恶; 上限:6,大小:2,成功>:]
试图做恶; 上限:6,大小:3,成功>:]
试图做恶; 上限:6,大小:4,成功>:]
试图做恶; 上限:6,大小:9,失败>:[
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.现在的容量不足以容纳要复制的其余元素.

也许您必须reserve在示例中明确capacity使用才能在使用之前强制更新observable do_evil.目前,insert可以保留一些容量,但capacity只有在复制完成后才能改变返回值(即可观察容量).

---

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

[sequence.reqmts]/3

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

要求:T应该是来自*i的EmplaceConstructible到X.

对于vector,如果迭代器不满足前向迭代器要求(24.2.5),则T也应该是MoveInsertable到X和MoveAssignable中.范围[i,j)中的每个迭代器只需解除引用一次.

pre:i和j不是迭代器.在p之前插入[i,j]中的元素副本

[vector.modifiers]上 insert

1备注:如果新大小大于旧容量,则会导致重新分配.如果没有重新分配,插入点之前的所有迭代器和引用仍然有效.如果除了复制构造函数之外抛出异常,移动构造函数,赋值运算符或T的移动赋值运算符,或者通过任何InputIterator操作都没有效果.如果非CopyInsertable T的移动构造函数抛出异常,则不指定效果.

2复杂性:插入元素的数量加上到向量末尾的距离是复杂的.

Answer 1

以下是我的看法：

1. 是的; 取消引用可能会对向量产生副作用（例证），在某些情况下可能会导致未定义的行为，但对于符合标准的迭代器来说，情况不应如此。
2. 不; 迭代器旨在作为指针的泛化 - 因为指针取消引用可能不会产生副作用（找不到引用），迭代器的情况也应该如此[iterator.requirements.general]。鉴于这种解释，“插入优化”(1) 是有效的。