C++ map node handle

考虑如下代码：

#include <iostream>
#include <map>
#include <string>
#include <boost/chrono.hpp>
#include <boost/timer/timer.hpp>

int main()
{
    std::map<int, std::string> a{ { 1, "one" }, { 2, "two" }, { 3, "buckle my shoe" } };
    std::map<int, std::string> b{ { 3, "three" } };

    //计算函数调用占用的时间
    boost::timer::cpu_timer timer;

    for (int i=0;i<10000;++i){

        {
        auto ite = a.find(2);
        auto [k,v] = *ite;
        b.emplace(std::make_pair(k, v));
        a.erase(ite);    
        }

        {
        auto ite = b.find(2);
        auto [k,v] = *ite;
        a.emplace(std::make_pair(k, v));
        b.erase(ite);
        }
    }

    boost::timer::cpu_times time = timer.elapsed();
    int wall_time_ = time.wall / 1000000; //纳秒转毫秒
    
    std::cout << "elasped time=" << wall_time_;

}

把元素2（key==2）在a,b两个容器之间移动。涉及到heap的内存分配和释放。当insert时，发生malloc，当erase时，发生free。
C++17开始，支持无heap动作的元素搬移：

#include <iostream>
#include <map>
#include <string>
#include <boost/chrono.hpp>
#include <boost/timer/timer.hpp>

int main()
{
    std::map<int, std::string> a{ { 1, "one" }, { 2, "two" }, { 3, "buckle my shoe" } };
    std::map<int, std::string> b{ { 3, "three" } };

    //计算函数调用占用的时间
    boost::timer::cpu_timer timer;

    for (int i=0;i<10000;++i){
        b.insert(a.extract(2)); 
        auto ite = b.find(2);
        a.insert(b.extract(ite)); 
    }

    boost::timer::cpu_times time = timer.elapsed();
    int wall_time_ = time.wall / 1000000; //纳秒转毫秒
    
    std::cout << "elasped time=" << wall_time_;

}

关键在于extract函数，它返回一个node handle。这个东西不是迭代器。参考：http://en.cppreference.com/w/cpp/container/node_handle

#include <iostream>
#include <map>
#include <string>
#include <boost/type_index.hpp>

int main()
{
    std::map<int, std::string> a{ { 1, "one" }, { 2, "two" }, { 3, "buckle my shoe" } };

    auto nh = a.extract(2); 

    auto type = boost::typeindex::type_id_with_cvr<decltype(nh)>();
    std::cout << type.pretty_name() << std::endl;

    if (!nh.empty()){
        nh.key()=4;
        nh.mapped()="four";   
        a.insert( std::move(nh) );
    }

    for(auto [k,v]:a){
        std::cout << "key=" << k << " value=" << v << std::endl;
    }
}

node handler持有map元素的所有权（指的是malloc出来的那个资源）。
可以通过key函数，mapped函数获取数据的引用，而是是非const的，允许修改。
必须通过右值插入map容器。因为a.insert(a.extract(2));中的a.extract(2)返回一个右值，所以不必用std::move强制转换。
nh是个左值，所以必须用std::move(nh)转成右值。

node handler的生存期与迭代器截然不同的地方是：node handler不需要同容器活的一样长，因为node handler是资源掠夺者，抢走容器的资源后，就同容器没关系了。
例如：

#include <iostream>
#include <set>

int main()
{
    auto generator = [ s = std::set<int>{2,4,6,8,10} ] () mutable {
        return s.extract(s.begin());
    };

    for(int i=0;i<5;++i){
        std::cout << generator().value() << " ";
    }
}

Splicing:

Node handles can be used to transfer ownership of an element between two associative containers with the same key, value, and allocator type (ignoring comparison or hash/equality), without invoking any copy/move operations on the container element (this kind of operation is known as "splicing").

这里需要注意的是，node handler存储的是容器的key（map类的），value，分配器。注意还有分配器，在free资源时，需要调用分配器的deallocate过程。思考一个问题：
如果两个容器的分配器类型不同，这两个容器的元素能spliceing吗？std::set<int, 分配器类型1> a， std::set<int, 分配器类型2> b ？

原文链接: https://www.cnblogs.com/thomas76/p/8723729.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/397502

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

C++ map node handle

相关推荐