c++ - std::vector 在 move 元素时做额外的操作

Question

我需要在内存中连续存储已排序的元素，所以我想到了 std::vector 和 boost::flat_set。我都试过了，我检查了它们的性能，虽然使用 std::vector 向后插入要快一点，但使用 boost::flat_set 前向插入要快得多。这是我的测试代码:

#include <iostream>
#include <vector>
#include <boost/container/flat_set.hpp>
#include <boost/chrono.hpp>
#include <windows.h>

// Just a basic movable object for my tests
class Component
{
public :
    Component( void ) :
        id( 0 ),
        name( "default" ),
        data( 100 )
    {
    }

    Component( uint32_t id ) :
        id( id ),
        name( "default" ),
        data( 100 )
    {
    }

    Component( Component&& component ) throw() :
        id( std::move( component.id ) ),
        name( std::move( component.name ) ),
        data( std::move( component.data ) )
    {
    }

    Component& operator=( Component&& component ) throw()
    {
        id = std::move( component.id );
        name = std::move( component.name );
        data = std::move( component.data );
        return ( *this );
    }

    uint32_t    get_id( void ) const
    {
        return ( id );
    }

private :
    uint32_t                id;
    std::string             name;
    std::vector< uint32_t > data;
};

// This object can be sorted
inline bool operator<( const Component& component1, const Component& component2 )
{
    return ( component1.get_id() < component2.get_id() );
}

#define COMP_NB 1000000

int main( void )
{
    /*******************************/
    /* Test vector insertion speed */
    /*******************************/
    std::vector< Component > vector;

    vector.reserve( COMP_NB + 1 );

    std::cout << "Push back components in the vector: ";
    auto startTime = boost::chrono::steady_clock::now();

    // Back insertion
    for ( uint32_t i = 0; i < COMP_NB; ++i )
    {
        vector.push_back( Component( i + 1 ) );
    }

    auto thisTime = boost::chrono::steady_clock::now();
    std::cout << boost::chrono::duration_cast< boost::chrono::milliseconds >( thisTime - startTime ).count() << "ms" << std::endl;

    std::cout << "Insert one component at the beginning of the vector: ";
    startTime = boost::chrono::steady_clock::now();

    // Front insertion (all components are shifted)
    vector.insert( vector.begin(), Component( 0 ) );

    thisTime = boost::chrono::steady_clock::now();
    std::cout << boost::chrono::duration_cast< boost::chrono::milliseconds >( thisTime - startTime ).count() << "ms" << std::endl;

    /*********************************/
    /* Test flat_set insertion speed */
    /*********************************/
    boost::container::flat_set< Component > flat_set;

    flat_set.reserve( COMP_NB + 1 );

    std::cout << "Push back components in the flat_set: ";
    startTime = boost::chrono::steady_clock::now();

    // Back insertion
    for ( uint32_t i = 0; i < COMP_NB; ++i )
    {
        flat_set.insert( Component( i + 1 ) );
    }

    thisTime = boost::chrono::steady_clock::now();
    std::cout << boost::chrono::duration_cast< boost::chrono::milliseconds >( thisTime - startTime ).count() << "ms" << std::endl;

    std::cout << "Insert one component at the beginning of the flat_set: ";
    startTime = boost::chrono::steady_clock::now();

    // Front insertion (all components are shifted)
    flat_set.insert( Component( 0 ) );

    thisTime = boost::chrono::steady_clock::now();
    std::cout << boost::chrono::duration_cast< boost::chrono::milliseconds >( thisTime - startTime ).count() << "ms" << std::endl;

    system( "PAUSE" );

    return ( 0 );
}

输出:

Push back components in the vector: 852ms
Insert one component at the beginning of the vector: 59ms
Push back components in the flat_set: 912ms
Insert one component at the beginning of the flat_set: 16ms

使用 flat_set 前插入速度 boost 了 3.6 倍!所以我又进行了一次测试，因为我想看看我的 move 功能是否被使用，我发现了一些奇怪的东西。这是新代码:

#include <iostream>
#include <vector>
#include <boost/container/flat_set.hpp>
#include <boost/chrono.hpp>
#include <windows.h>

// Just a basic movable object for my tests
class Component
{
public :
    Component( void ) :
        id( 0 ),
        name( "default" ),
        data( 100 )
    {
        std::cout << "Default constructor" << std::endl;
    }

    Component( uint32_t id ) :
        id( id ),
        name( "default" ),
        data( 100 )
    {
        std::cout << "Custom constructor" << std::endl;
    }

    Component( Component&& component ) throw() :
        id( std::move( component.id ) ),
        name( std::move( component.name ) ),
        data( std::move( component.data ) )
    {
        std::cout << "Move constructor" << std::endl;
    }

    Component& operator=( Component&& component ) throw()
    {
        std::cout << "Move assignment operator" << std::endl;
        id = std::move( component.id );
        name = std::move( component.name );
        data = std::move( component.data );
        return ( *this );
    }

    uint32_t    get_id( void ) const
    {
        return ( id );
    }

private :
    uint32_t                id;
    std::string             name;
    std::vector< uint32_t > data;
};

// This object can be sorted
inline bool operator<( const Component& component1, const Component& component2 )
{
    return ( component1.get_id() < component2.get_id() );
}

#define COMP_NB 1

int main( void )
{
    /*******************************/
    /* Test vector insertion speed */
    /*******************************/
    std::vector< Component > vector;

    vector.reserve( COMP_NB + 1 );

    std::cout << "-- Push back one component in the vector: " << std::endl;

    // Back insertion
    for ( uint32_t i = 0; i < COMP_NB; ++i )
    {
        vector.push_back( Component( i + 1 ) );
    }

    std::cout << "-- Insert one component at the beginning of the vector: " << std::endl;

    // Front insertion (the other component is shifted)
    vector.insert( vector.begin(), Component( 0 ) );

    std::cout << std::endl;

    /*********************************/
    /* Test flat_set insertion speed */
    /*********************************/
    boost::container::flat_set< Component > flat_set;

    flat_set.reserve( COMP_NB + 1 );

    std::cout << "-- Push back one component in the flat_set: " << std::endl;

    // Back insertion
    for ( uint32_t i = 0; i < COMP_NB; ++i )
    {
        flat_set.insert( Component( i + 1 ) );
    }

    std::cout << "-- Insert one component at the beginning of the flat_set: " << std::endl;

    // Front insertion (the other component is shifted)
    flat_set.insert( Component( 0 ) );

    system( "PAUSE" );

    return ( 0 );
}

新的输出:

-- Push back one component in the vector:
Custom constructor
Move constructor
-- Insert one component at the beginning of the vector:
Custom constructor
Move constructor
Move constructor
Move assignment operator
Move assignment operator

-- Push back one component in the flat_set:
Custom constructor
Move constructor
-- Insert one component at the beginning of the flat_set:
Custom constructor
Move constructor
Move assignment operator

这里有些奇怪。 Flat_set 行为似乎很正常:

-- Insert one component at the beginning of the flat_set:
Custom constructor //Ok, I asked the creation of a new component
Move constructor //Ok, the flat_set need to shift the previous component in a new position
Move assignment operator //OK, the new component need to be moved to the front of the flat_set

但是 vector 呢？

-- Insert one component at the beginning of the vector:
Custom constructor //Ok, I asked the creation of a new component
Move constructor //Ok, the vector need to shift the previous component in a new position
Move constructor //Wait... what?
Move assignment operator //OK, the new component need to be moved to the front of the vector
Move assignment operator //Wtf?

我尝试了更多的组件， vector 行为是一样的:它一直执行所有 move 操作两次。为什么？可以避免吗？如果不是，我应该坚持使用 flat_set(我有时需要 move 我的数据)吗？

[编辑] :这是在后面插入 10 个组件，在前面插入 1 个组件的输出，以及正在构建或 move 的组件的 id: http://pastebin.com/SzT5M8yP

[编辑 2]:我用 boost::container::vector 做了同样的测试，输出(和速度!)与 flag_set 相同。它是 vector 的 Microsoft 实现的问题吗？哦

[编辑 3]:提交给 Microsoft 的问题:https://connect.microsoft.com/VisualStudio/feedback/details/801205/std-vector-do-extra-operations-when-shifting-elements

Answer 1

它不会对所有 move 操作执行两次，如果您的 vector 中有多个元素，您会看到只有一些 操作发生了两次。

要在 N 个元素的 vector (具有足够的容量)的开头插入一个右值，典型的方法是:

1. 从索引 N-1 的元素 move 到索引 N 的新元素
   new (_M_data+N) T(_M_data[N-1]);
_M_size += 1;
2. 将索引 0 到 N-2 处的分配元素 move 到索引 1 到 N-1
   for (int i = N-1; i > 0; --i)
_M_data[i] = std::move(_M_data[i-1]);
3. move 临时构造并将其分配给索引 0
   _M_data[0] = T(std::move(arg));

这意味着您将看到一个 move 构造，然后是 (N-1) 个 move 分配(在您的情况下， vector 只有一个元素，因此您在第 2 步中看不到任何内容)，然后是一个 move 构造和一个 move 分配。

在第 3 步中构造了临时文件，因为 emplace 使用了与 insert 相同的插入逻辑，因此它实际上执行了 T(std::move( args)...) 具有零个或多个 args，在只有一个类型为 T 的参数的情况下，可以只执行 _M_data[0] = std::move(arg); 并避免 move 构造。

我不确定为什么您会在末尾看到一个额外的 move 分配，GCC 的标准库实现不会这样做，而且我不确定为什么需要它。您可以很容易地修改您的代码以打印构造/分配的被 move 对象的标识，以查看哪些元素被 move 了两次，这可能会更清楚地说明这一点。