为什么Microsoft std::vector::insert使用rotate()？

Question

我用列表和向量做了一些实验，我注意到微软的std::vector的实现为.insert做了以下事情：

iterator insert(const_iterator _Where, _Ty&& _Val)
    {   // insert by moving _Val at _Where
    return (emplace(_Where, _STD move(_Val)));
    }

    iterator emplace(const_iterator _Where \
        COMMA LIST(_TYPE_REFREF_ARG)) \
    {   /* insert by moving _Val at _Where */ \
    size_type _Off = _VIPTR(_Where) - this->_Myfirst; \
    _VECTOR_EMPLACE_CHECK \
    emplace_back(LIST(_FORWARD_ARG)); \
    _STD rotate(begin() + _Off, end() - 1, end()); \
    return (begin() + _Off); \
    }

我不知道rotate在vs2012中是做什么的，但在2015年的时候我做到了：

template<class _RanIt> inline
    _RanIt _Rotate(_RanIt _First, _RanIt _Mid, _RanIt _Last,
        random_access_iterator_tag)
    {   // rotate [_First, _Last), random-access iterators
    _STD reverse(_First, _Mid);
    _STD reverse(_Mid, _Last);
    _STD reverse(_First, _Last);
    return (_First + (_Last - _Mid));
    }

// TEMPLATE FUNCTION reverse
template<class _BidIt> inline
    void _Reverse(_BidIt _First, _BidIt _Last, bidirectional_iterator_tag)
    {   // reverse elements in [_First, _Last), bidirectional iterators
    for (; _First != _Last && _First != --_Last; ++_First)
        _STD iter_swap(_First, _Last);
    }

如果我们考虑我们的缓存，这不是遍历内存的最佳方式。

我做了一些基准测试，我将元素保存在临时中，并用它来交换元素，速度更快:就是这样：

push_back(value); //My vector doesn't have resize/grow implemented
T tmp = *(end() - 1);
while(new_location != end())
{
    std::swap(tmp, *new_location);
    new_location++;
}

完整的代码和测试都是here。

第一个问题：

为什么要这样旋转，而不是我在这里介绍的第二个版本的插入？

与第一个版本相比，第二个版本是一个更适合缓存的替代方案。对于较大的向量，与向量中的最后一个元素交换会由于缓存而导致时间损失。

是为了避免存储另一个临时的吗？

第二个问题：

为什么不直接把元素向右移动一个位置呢？

有没有一个标准的要求，强制你交换元素而不是调用memmove?有趣的是，对于POD来说，没有专门的模板专门化，仅仅是memmove的东西。在任何情况下，我更感兴趣的是为什么旋转，而不是使用更好的缓存友好的替代方案。

在我的测试中，这甚至比前两个版本更快。

测试是这样进行的：

0) i=0进行计数

1)在向量中随机选取一个位置

2)触摸从0到该位置的每个元素(强制读取)

3)到达位置后调用insert

使用Visual Studio2012 x86，/O2编译。

For count = 100 000, element size = 4 bytes:

std::vector:                7.5 seconds   
std::list:                 19.6 seconds                            
MyVector:                   3.2 seconds                              
MyVector using memmove:     2.1 seconds

For count = 200 000, element size = 4 bytes:
std::vector:                30.3 seconds                          
std::list:                  45.5 seconds                          
MyVector:                   13.1 seconds
MyVector using memmove:      8.7 seconds   

For count = 20 000, element size = 128 bytes:
std::vector:                5.36 seconds
std::list:                  1.37 seconds
MyVector:                   5.12 seconds
MyVector (memmove)          1.68 seconds

我知道这不是现实生活中你会做的事情，这些是我做的一些实验，目的是为了证明缓存的重要性，我偶然发现了std向量插入的工作方式。

我也知道MyVector是一个糟糕的向量实现。我只是快速地写了它，以便测试我对插入的假设。我只想讨论insert()实现，而不是向量类设计:).

感谢你阅读这篇文章

Answer 1

事实证明，在std::vector::insert中调用rotate没有什么特别的原因。

我将在这里粘贴在insert()中使用的visual studio 2015的rotate实现：

template<class _RanIt> inline
    _RanIt _Rotate(_RanIt _First, _RanIt _Mid, _RanIt _Last,
        random_access_iterator_tag)
    {   // rotate [_First, _Last), random-access iterators
    _STD reverse(_First, _Mid);
    _STD reverse(_Mid, _Last);
    _STD reverse(_First, _Last);
    return (_First + (_Last - _Mid));
    }

// TEMPLATE FUNCTION reverse
template<class _BidIt> inline
    void _Reverse(_BidIt _First, _BidIt _Last, bidirectional_iterator_tag)
    {   // reverse elements in [_First, _Last), bidirectional iterators
    for (; _First != _Last && _First != --_Last; ++_First)
        _STD iter_swap(_First, _Last);
    }

对缓存更友好的实现将提高此方法的速度(vector::insert)。

我之所以知道，是因为微软STL的人意识到了这个问题:)

https://twitter.com/StephanTLavavej/status/695013465342083072