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

Question

libc ++ 的std::vector 实现具有以下重载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++ 解决相同的问题.

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;

rvalue引用重载没有进行相同的检查,因为允许实现假定rvalue引用引用的任何对象都是唯一引用的,因此尝试使用对insert已经存在的元素的rvalue引用执行a vectoris undefined行为.

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

除非另有明确说明,否则以下各项均适用于C++标准库中定义的函数的所有参数.
- ...
- 如果函数参数绑定到右值引用参数,则实现可以假定此参数是对此参数的唯一引用.

以下是上述条款的缺陷报告和基本原理.