在删除包含指向自身在列表中位置的迭代器的节点时，vs2015 上的 stl 列表性能较差

我只是存储一个节点列表，每个节点都包含一个指向其在列表中位置的迭代器。然后我对插入和删除 std 列表和 boost 列表节点所需的时间进行基准测试。

Includes

#include <iostream>
#include <memory>
#include <list>
#include <chrono>    
#include "boost/container/list.hpp"
#include "boost/shared_ptr.hpp"
#include "boost/make_shared.hpp"

#define ONE_BILLION             1000000000
#define ONE_HUNDRED_MILLION     100000000
#define TEN_MILLION             10000000
#define ONE_MILLION             1000000
#define ONE_HUNDRED_THOUSAND    100000
#define TEN_THOUSAND            10000

帮助函数打印插入或删除的平均持续时间

void print_duration(std::ostream &out, const std::string& str, const std::chrono::high_resolution_clock::duration &d)
{
    out << str << ": ";

    if (d < std::chrono::microseconds(10))
        out << std::chrono::duration_cast<std::chrono::duration<float, std::nano>>(d).count() << " nano s";
    else if (d < std::chrono::milliseconds(10))
        out << std::chrono::duration_cast<std::chrono::duration<float, std::micro>>(d).count() << " micro s";
    else if (d < std::chrono::seconds(10))
        out << std::chrono::duration_cast<std::chrono::duration<float, std::milli>>(d).count() << " milli s";
    else if (d < std::chrono::minutes(10))
        out << std::chrono::duration_cast<std::chrono::duration<float>>(d).count() << " s";

    out << std::endl;
}

STL list

struct node
{
    std::list<std::shared_ptr<node>>::iterator iter;
};

void measure_list_insert_std(std::list<std::shared_ptr<node>>& l)
{
    const size_t count = TEN_THOUSAND;
    size_t i = 0;



    auto begin = std::chrono::high_resolution_clock::now();
    for (; i < count; ++i)
    {
        std::shared_ptr<node> temp = std::make_shared<node>();
        l.push_back(temp);
        temp->iter = --l.end();
    }

    std::chrono::high_resolution_clock::duration total = std::chrono::high_resolution_clock::now() - begin;
    print_duration(std::cout, "measure_list_insert_std  ", total / i);
}

void measure_list_delete_std(std::list<std::shared_ptr<node>>& l)
{
    const size_t count = TEN_THOUSAND;
    size_t i = 0;

    auto begin = std::chrono::high_resolution_clock::now();
    for (; i < count; ++i)
    {
        //std::list<std::shared_ptr<node>>::iterator it = (l.front())->iter;
        l.erase((l.front())->iter);
        //l.pop_back();
        //std::cout << l.size() << std::endl;
    }

    std::chrono::high_resolution_clock::duration total = std::chrono::high_resolution_clock::now() - begin;
    print_duration(std::cout, "measure_list_delete_std  ", total / i);
    //std::cout << l.size() << std::endl;
}

提升列表

struct node_boost
{
    boost::container::list<boost::shared_ptr<node_boost>>::iterator iter;
};

void measure_list_insert_boost(boost::container::list<boost::shared_ptr<node_boost>>& l)
{
    const size_t count = ONE_MILLION;
    size_t i = 0;



    auto begin = std::chrono::high_resolution_clock::now();
    for (; i < count; ++i)
    {
        boost::shared_ptr<node_boost> temp = boost::make_shared<node_boost>();
        l.push_back(temp);
        temp->iter = --l.end();
    }

    std::chrono::high_resolution_clock::duration total = std::chrono::high_resolution_clock::now() - begin;
    print_duration(std::cout, "measure_list_insert_boost  ", total / i);
}

void measure_list_delete_boost(boost::container::list<boost::shared_ptr<node_boost>>& l)
{
    const size_t count = ONE_MILLION;
    size_t i = 0;

    auto begin = std::chrono::high_resolution_clock::now();
    for (; i < count; ++i)
    {
        //std::list<std::shared_ptr<node>>::iterator it = (l.front())->iter;
        l.erase((l.front())->iter);
        //l.pop_back();
        //std::cout << l.size() << std::endl;
    }

    std::chrono::high_resolution_clock::duration total = std::chrono::high_resolution_clock::now() - begin;
    print_duration(std::cout, "measure_list_delete_boost  ", total / i);
    //std::cout << l.size() << std::endl;
}

Main

int main()
{
    std::list < std::shared_ptr<node>> l;

    measure_list_insert_std(l);
    measure_list_delete_std(l);

    boost::container::list<boost::shared_ptr<node_boost>> l2;
    measure_list_insert_boost(l2);
    measure_list_delete_boost(l2);

    return 0;
}

我只是存储一个节点列表，每个节点都包含一个指向其在列表中位置的迭代器。

上述代码的输出是：

测量列表插入标准：4830 纳秒

measure_list_delete_std : 431.624 微秒

measure_list_insert_boost：4462 纳秒

measure_list_delete_boost : 4248 纳秒

如果节点不包含“迭代器”元素，则一切正常，所有输出大致相似。为什么在 VS2015 实现列表中会出现此问题？

当运行代码来测试性能时，always use 优化标志。我也有同样的问题为什么 emplace_back 比 push_back 快？，所以你不是第一个面对这个问题的人。

在 IDE 上，为了进行基准测试，您必须使用发布方式，但仍然使用（始终可靠）终端和优化标志g++例如，应该记住。