vector::insert 重载之间的 libc++ 区别

Question

libc++的std::vectorimplementation有以下insert重载：

template <class _Tp, class _Allocator>
typename vector<_Tp, _Allocator>::iterator
vector<_Tp, _Allocator>::insert(const_iterator __position, const_reference __x)
{
    pointer __p = this->__begin_ + (__position - begin());
    if (this->__end_ < this->__end_cap())
    {
        __RAII_IncreaseAnnotator __annotator(*this);
        if (__p == this->__end_)
        {
            __alloc_traits::construct(this->__alloc(),
                                      _VSTD::__to_raw_pointer(this->__end_), __x);
            ++this->__end_;
        }
        else
        {
            __move_range(__p, this->__end_, __p + 1);
            const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x);
            if (__p <= __xr && __xr < this->__end_) // [*]
                ++__xr;
            *__p = *__xr;
        }
        __annotator.__done();
    }
    else
    {
        allocator_type& __a = this->__alloc();
        __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
        __v.push_back(__x);
        __p = __swap_out_circular_buffer(__v, __p);
    }
    return __make_iter(__p);
}

...和类似的，采用右值参考：

template <class _Tp, class _Allocator>
typename vector<_Tp, _Allocator>::iterator
vector<_Tp, _Allocator>::insert(const_iterator __position, value_type&& __x)
{
    pointer __p = this->__begin_ + (__position - begin());
    if (this->__end_ < this->__end_cap())
    {
        __RAII_IncreaseAnnotator __annotator(*this);
        if (__p == this->__end_)
        {
            __alloc_traits::construct(this->__alloc(),
                                      _VSTD::__to_raw_pointer(this->__end_),
                                      _VSTD::move(__x));
            ++this->__end_;
        }
        else
        {
            __move_range(__p, this->__end_, __p + 1);
            *__p = _VSTD::move(__x);
        }
        __annotator.__done();
    }
    else
    {
        allocator_type& __a = this->__alloc();
        __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
        __v.push_back(_VSTD::move(__x));
        __p = __swap_out_circular_buffer(__v, __p);
    }
    return __make_iter(__p);
}

第一个重载中标有[*]的分支的目的是什么？是标准要求的吗？为什么它在第二次超载中不存在？我在 libstdc++.

中找不到等效的构造

编辑: libstdc++ solves 创建临时副本同样的问题。

Answer 1

这是处理您要插入的元素已经存在于 vector 中的情况的条件。

为了解释这一点，让我们从定义函数中使用的变量开始。

__p是指向要插入新元素的位置的指针
__xr是指向要插入的元素地址的指针

当 vector 有足够的容量插入附加元素 (if (this->__end_ < this->__end_cap())) 时，将执行您询问的代码路径。此外，插入点不是 end() 迭代器（if (__p == this->__end_) — else 路径被执行）。

在这种情况下，实现首先将 [__p, end()) 范围内的所有内容移动一个位置 — __move_range(__p, this->__end_, __p + 1);

但是，如果您要插入的元素是刚刚移动的范围的一部分怎么办？如果是这样，您必须递增指向要插入的元素的指针。这就是下面几行所做的

if (__p <= __xr && __xr < this->__end_)
  ++__xr;

右值引用重载没有进行相同的检查，因为允许实现假定右值引用引用的任何对象都是唯一引用的，因此尝试使用右值引用执行 insert vector 中已经存在的元素是未定义的行为。

来自 N3337，§17.6.4.9/1 [res.on.arguments]

Each of the following applies to all arguments to functions defined in the C++ standard library, unless explicitly stated otherwise.
— ...
— If a function argument binds to an rvalue reference parameter, the implementation may assume that this parameter is a unique reference to this argument.

这是上述条款的 defect report 和基本原理。

vector::insert 重载之间的 libc++ 区别

libc++ difference between vector::insert overloads

c++

c++11

vector

libc++