c++11 boost - 容器(2) unordered_set、unordered_map、bitmap

2018-07-12 10:29:37

unordered_set 内部使用 hash 实现,是无序的集合。

unordered_map 内部使用 hash 实现,是无序的映射。

// Copyright (c) 2015
// Author: Chrono Law
#include <iostream>
using namespace std;

#include <boost/assign.hpp>
#include <boost/unordered_set.hpp>
#include <boost/unordered_map.hpp>
using namespace boost;

void case1()
{
    unordered_set<int > s = {1,2,3,4,5};

    for (auto x : s)
    {   cout << x << " ";   }
    cout << endl;
    cout << s.size() << endl;

    s.clear();
    cout << s.empty() << endl;

    s.insert(8);
    s.insert(45);
    cout << s.size() << endl;
    cout << *s.find(8) << endl;

    s.erase(45);

    using namespace boost::assign;
    unordered_set<int> us1 = list_of(1)(2)(3);
    unordered_set<int> us2 = list_of(3)(2)(1);
    assert(us1 == us2 );

}

//emplace直接创建对象插入到容器,避免拷贝对象
void case2()
{
    typedef complex<double> complex_t;
    unordered_set<complex_t> s;

    s.emplace(1.0, 2.0);
    s.emplace(3.0, 4.0);

    for(auto& x : s)
    {    cout << x << ",";}
    cout << endl;

    s.emplace_hint(s.begin(), 5.0, 6.0);  //多提供插入的位置
    for(auto& x : s)
    {    cout << x << ",";}

}


void case3()
{
    using namespace boost::assign;

    unordered_map<int, string> um =
        map_list_of(1,"one")(2, "two")(3, "three");

    um.insert(make_pair(10,"ten"));
    cout << um[10] << endl;
    um[11] = "eleven";
    um[15] = "fifteen";

    auto p = um.begin();
    for (; p != um.end(); ++p)
    {   cout << p->first << "-" << p->second << ",";    }
    cout << endl;

    um.erase(11);
    cout << um.size() << endl;

    unordered_map<int, string> um1 = map_list_of(1,"11")(2,"22");
    unordered_map<int, string> um2 = map_list_of(1,"one")(2,"two");
    assert(um1 != um2);

}

void case4()
{
    typedef complex<double> complex_t;  //标准复数类型
    typedef unordered_map<int,complex_t> um_t;
    um_t s;

    s.emplace(boost::unordered::piecewise_construct,  //分段构造pair
        make_tuple(1),make_tuple(1.0, 2.0));
    s.emplace(boost::unordered::piecewise_construct,
        make_tuple(3),make_tuple(3.0, 4.0));

    for(auto& x: s)
    {
            cout << x.first << "<->" << x.second << ",";
    }
    cout << endl;

    s.emplace_hint(s.begin(),
    boost::unordered::piecewise_construct,
        make_tuple(5),make_tuple(5.0, 6.0));
    for(auto& x: s)
    {
            cout << x.first << "<->" << x.second << ",";
    }
	cout << endl;
}

//unordered 内部有桶的概念,hash值相同的会放进同一个桶。
void case5()
{
    using namespace boost::assign;

    unordered_set<int> us = (list_of(1),2,3,4);
    cout << us.bucket_count() << endl;

    for (size_t i = 0; i < us.bucket_count(); ++i)
    {   cout << us.bucket_size(i) << ",";   }

}

int main()
{
    case1();
    case2();
    case3();
    case4();
    case5();
}
[root@192 c++]# g++ -std=c++11 main.cpp 
[root@192 c++]# 
[root@192 c++]# 
[root@192 c++]# ./a.out 
5 4 3 2 1 
5
1
2
8
(3,4),(1,2),
(3,4),(5,6),(1,2),ten
15-fifteen,11-eleven,10-ten,3-three,2-two,1-one,
5
3<->(3,4),1<->(1,2),
5<->(5,6),3<->(3,4),1<->(1,2),17
0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,


c++标准中的map和 multi_map 它们能通过 key 映射到 value。但这种映射时单向的。

bitmap 提供双向映射能力,可以容纳两个类型的元素,是这两个关系的集合,这是 bitmap 的基本视图。此外,这个关系还可以有两个视图,左视图和右视图。

提供了集合类型如下:

set_of:相当于map
multiset_of:相当于multimap
unordered_set_of:相当于 unordered_map
unordered_multiset_of:相当于 unordered_multimap
list_of:不能用作索引,序列集合,无对应标准容器
vector_of:不能用作索引,随机访问集合,无对应标准容器
unconstrained_set_of:不能用作索引,无任何约束关系,无对应标准容器

用法相对复杂,如果不是特别需求,可以使用std::map 或 std::unordered_map

// Copyright (c) 2015
// Author: Chrono Law
#include <iostream>
using namespace std;

#include <boost/bimap.hpp>
#include <boost/bimap/vector_of.hpp>
#include <boost/bimap/list_of.hpp>
#include <boost/bimap/multiset_of.hpp>
#include <boost/bimap/unordered_set_of.hpp>
#include <boost/bimap/unordered_multiset_of.hpp>
#include <boost/bimap/unconstrained_set_of.hpp>
using namespace boost;

void case1()
{
    bimap<int, string> bm;


    bm.left.insert(make_pair(1, "111"));
    bm.left.insert(make_pair(2, "222"));


    bm.right.insert(make_pair("string", 10));
    bm.right.insert(make_pair("bimap", 20));


    for (auto pos = bm.left.begin();
            pos != bm.left.end();++pos)
    {
        cout << "left[" << pos->first << "]="
            << pos->second << endl;
    }

    //bm.right.begin()->second = 234;

    {
        bimap<int, string> bm;
        typedef decltype(bm)::value_type vt;
        bm.insert(vt(3, "333"));

    }
}

//////////////////////////////////////////
using namespace boost::bimaps;

//左组是有序集合,右组是无序集合
bimap<int, unordered_set_of< string> > bm1;

//两边都是有序多值集合
bimap< multiset_of<int>, multiset_of< string> > bm2;

//左组是无序集合,有组是序列,只能由左视图
bimap< unordered_set_of<int>, list_of< string> > bm3;

//左组是随机访问集合,有组无约束
bimap< vector_of<int>, unconstrained_set_of< string> > bm4;

template<typename T>
void print_map(T &m)
{
    for (auto& x : m)
    {   cout << x.first << "<-->"<< x.second << endl;   }
}


void case2()
{
    bimap<unordered_multiset_of<int>, unordered_multiset_of< string> > bm;

    bm.left.insert(make_pair(1, "111"));
    bm.left.insert(make_pair(2, "222"));
    bm.left.insert(make_pair(2, "555"));

    bm.right.insert(make_pair("string", 10));
    bm.right.insert(make_pair("bimap", 20));
    bm.right.insert(make_pair("bimap", 2));

    print_map(bm.left);

    {
        bimap<set_of<int>, vector_of<string> > bm;

        bm.left.insert(make_pair(1, "111"));
        bm.left[2] = "222";
        bm.left[300] = "bimap";

        //bm.right.insert(make_pair("string", 10));

        print_map(bm.left);

    }
}

//添加标签,避免造成混乱
bimap<tagged<int, struct id>, vector_of<string> >       bm11;
bimap<multiset_of<tagged<int, struct id> >,
        unordered_set_of<tagged< string, struct name> > >       bm12;

void case3()
{
    bimap<tagged<int, struct id>, tagged< string, struct name> > bm;

    bm.by<id>().insert(make_pair(1, "samus"));
    bm.by<id>().insert(make_pair(2, "adam"));

    bm.by<name>().insert(make_pair("link", 10));
    bm.by<name>().insert(make_pair("zelda", 11));

    print_map(bm.by<name>());
}

//查找替换
#include <boost/assign.hpp>
void case4()
{
    using namespace boost::bimaps;
    typedef bimap<multiset_of<int>, vector_of<string> > bm_t;

    bm_t bm = assign::list_of<bm_t::relation>(1, "111")(2, "222");
    //bm_t bm = {{1, "111"},{2, "222"}};

    assign::insert(bm.left)(3, "333")(4, "444");
    assign::push_back(bm.right)("555", 5)("666", 6);

    auto left_pos  = bm.left.find(3);
    auto right_pos = bm.project_right(left_pos);
    cout << "right:[" << right_pos->first 
        << "]=" << right_pos->second;

}

#include <boost/bimap/support/lambda.hpp>
void case5()
{
    using namespace boost::bimaps;
    typedef bimap<int, string > bm_t;

    using namespace boost::assign;
    bm_t bm = assign::list_of<bm_t::relation>
        (1, "mario")(2, "peach");

    auto pos = bm.left.find(1);
    cout << "[" << pos->first
        << "]=" << pos->second << endl;
    auto pos2 = bm.right.find("peach");
    cout << "[" << pos2->first
        << "]=" << pos2->second << endl;

    //pos = bm.left.find(1);
    //bm.left.replace_key(pos, 111);
    //bm.left.replace_data(pos, "luigi");

    pos = bm.left.find(1);
    bm.left.modify_key(pos,_key = 111);
    bm.left.modify_data(pos,_data = "luigi");
}

//投射
void case6()
{
    using namespace boost::bimaps;
    typedef bimap<set_of<tagged<int,struct id> >, 
            multiset_of< tagged<string,struct name> > > bm_t;

    using namespace boost::assign;

    bm_t bm = assign::list_of<bm_t::relation>(1, "mario")(2, "peach");
        insert(bm.by<id>())(3, "wario")(4, "luigi");
        insert(bm.by<name>())("yoshi", 5)("olima", 6);

    auto right_pos = bm.by<name>().find("yoshi");
    auto left_pos  = bm.project<id>(right_pos);
    ++left_pos;
    cout << "left:[" << left_pos->get<id>() 
        << "]=" << left_pos->get<name>();

}

void case7()
{
    typedef bimap<int, string> bm_t;
    bm_t bm;
    bm.left.insert(bm_t::left_value_type(1, "one"));
    bm.right.insert(bm_t::right_value_type("two", 222));

}

int main()
{
    case1();
    case2();
    case3();
    case4();
    case5();
    case6();
    case7();
}


0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,[root@192 c++]# g++ -std=c++11 main.cpp 
[root@192 c++]# 
[root@192 c++]# 
[root@192 c++]# 
[root@192 c++]# ./a.out 
left[1]=111
left[2]=222
left[10]=string
left[20]=bimap
1<-->111
2<-->bimap
2<-->555
2<-->222
10<-->string
20<-->bimap
1<-->111
2<-->222
300<-->bimap
adam<-->2
link<-->10
samus<-->1
zelda<-->11
right:[333]=3[1]=mario
[peach]=2
left:[6]=olima


 备注

1.编译器版本gcc4.8.5,运行环境centos7 64位
2.本文只做简单记录用,详细用法请参考 Boost Library,或者是罗剑锋的 boost程序库完全开发指南 书本
3..原文地址http://www.freecls.com/a/2712/a6


©著作权归作者所有
收藏
推荐阅读
简介
天降大任于斯人也,必先苦其心志。