0

我需要将排序后的元素连续存储在内存中，所以我想到了 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 );
}

和输出：

推回vector中的分量：852ms 在vector开头
插入一个分量：59ms
推回flat_set中的分量：912ms 在flat_set开头
插入一个分量：16ms

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

#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 );
}

新输出：

-- 推回向量中的一个组件：
自定义构造函数
移动构造函数
--在向量开头插入一个组件：
自定义构造
函数移动构造函数移动构造
函数
移动赋值运算符
移动赋值运算符

--推回 flat_set 中的一个组件：
自定义构造函数
移动构造函数
——在flat_set开头插入一个组件：
自定义构造函数
移动构造函数
移动赋值运算符

这里有一些奇怪的东西。Flat_set 行为似乎很正常：

-- 在flat_set开头插入一个组件:
自定义构造函数 //Ok, 我要求创建一个新组件
Move构造函数 //Ok, flat_set需要将前一个组件移到一个新位置
Move assignment operator //OK , 新组件需要移动到 flat_set 的前面

但是向量呢？

-- 在向量的开头插入一个组件：
自定义构造函数 // 好的，我要求创建一个新的组件
移动构造函数 // 好的，向量需要将前一个组件移到一个新的位置
移动构造函数 // 等等。 .. 什么？
移动赋值运算符 //OK，新组件需要移动到向量前面
移动赋值运算符 //Wtf?

我尝试了更多组件，并且矢量行为是相同的：它继续执行所有移动操作两次。为什么？可以避免吗？如果没有，我应该坚持 flat_set （我有时需要转移我的数据）？

[编辑]：这是输出，其中 10 个组件被插入到后面，1 个组件被插入到前面，并且组件的 id 正在构建或移动： http: //pastebin.com/SzT5M8yP

[编辑 2]：我用 boost::container::vector 做了同样的测试，输出（和速度！）与 flag_set 相同。微软实现vector有问题吗？哦

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

4

3 回答 3

2

它不会将所有移动操作都执行两次，如果您的向量中有多个元素，您会看到只有一些操作发生两次。

要在 N 个元素（具有足够容量）的向量的开头插入一个右值，典型的方法是：

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

这意味着您将看到一个移动构造，然后是 (N-1) 个移动分配（在您的情况下，向量只有一个元素，因此您在步骤 2 中什么也看不到），然后是移动构造和移动分配。

emplace在第 3 步中，由于as使用了相同的插入逻辑，因此构造了临时变量insert，因此它实际上T(std::move(args)...)使用零个或多个 args，在只有一个类型参数的情况下，T可以只做_M_data[0] = std::move(arg);并避免移动建造。

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

于 2013-09-17T12:37:13.223 回答
0

3 年后，这是我在邮箱中收到的内容：

来自 Microsoft Connect 的问候！

此通知是针对反馈项生成的：std::vector 在移动您在 Microsoft Connect 站点提交的元素时执行额外操作。

你好，

感谢您报告此错误。我已经通过彻底检查向量的正确性和性能来修复它，这个修复将在 VS“15”RC 中可用。以前，在某些情况下，插入/放置调用 rotate()。现在我们更智能地对动作进行排序，避免了旋转元素的需要。

Stephan T. Lavavej 首席软件工程师，Visual C++ 库 stl@microsoft.com

如果 Microsoft 进行了任何其他更改，您也可能会收到一般的“已更新反馈项目”通知。

感谢您使用 Microsoft Connect！

问候，

Microsoft Connect 团队

请不要直接回复此消息，因为它是由不受监控的电子邮件帐户生成的。如果您有与您的反馈相关的评论，请通过导航到上面链接中的反馈项目，在您的反馈项目的评论部分（向 Microsoft 发表评论）输入它。

如果您在访问上面的反馈链接时遇到问题，请到http://connect.microsoft.com/help/default.aspx页面报告问题，在提交时，请务必粘贴上面的链接副本进入报告。

欢呼！很快就会修复。:D 确实有点晚了，但这仍然是一件好事。

于 2016-11-03T19:08:06.937 回答
-1

我的猜测是std::vector通过分配一个新向量，将当前奇异值复制到新向量中，然后插入新值来增加向量的大小。尝试删除调用以reserve使内存管理std::vector为您工作。

于 2013-09-17T11:45:51.963 回答