Poor performance of the stl list on vs2015 when deleting nodes that contain an iterator for an independent position in the list

Question

I just keep a list of nodes, and each node contains an iterator pointing to its position in the list. Then I compare the time taken to insert and remove nodes for the std and boost list.

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

Helper function for printing average insert or delete duration

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

Acceleration List

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

home

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

I just keep a list of nodes, and each node contains an iterator pointing to its position in the list.

The output for the code above is:

measure_list_insert_std: 4830 nano s

measure_list_delete_std: 431.624 micro s

measure_list_insert_boost: 4462 nano s

measure_list_delete_boost: 4248 nano s

node "", , . VS2015 - <

Answer 1

. emplace_back , push_back?, , .

IDE Release, ( ) g++, , .