51工具盒子Boost.Bimap 是 C++ Boost 库中的一个组件，它提供了一种双向映射的容器，即键和值之间的双向映射。这意味着可以通过键查找值，也可以通过值查找键。Boost.Bimap 提供了一种方便的方式来管理这种键-值对之间的关系，尤其适用于需要频繁进行双向查找的情况。
- 操作视图 {#title-0} ==================
Boost Bimap 的三种视图分别是左集合视图 (left set view)、右集合视图 (right set view) 和关系视图 (relation view)。
- 左集合视图：左集合中的元素为 key，右集合中的元素为 value
- 右集合视图：右集合中的元素为 key，左集合中的元素为 value
- 关系视图：key 和 value 作为一个整体元素存在
#if 1
#include <boost/bimap/bimap.hpp>
#include <iostream>
void test()
{
// 创建双向映射容器
using container_type = boost::bimaps::bimap<int, std::string>;
container_type map;
// bimap 容器添加、删除、查找等操作都分为三个视图
// 左视图
map.left.insert(container_type::left_value_type(1006, "张三"));
map.left.insert(std::make_pair(1005, "李四"));
for (container_type::left_const_iterator iter = map.left.begin(), end = map.left.end(); iter != end; ++iter)
{
std::cout << "key:" << iter->first << " value:" << iter->second << std::endl;
}
std::cout << "-------------------" << std::endl;
// 右视图
map.right.insert(container_type::right_value_type("王五", 1004));
map.right.insert(std::make_pair("赵六", 1003));
for (auto iter = map.right.begin(), end = map.right.end(); iter != end; ++iter)
{
std::cout << "key:" << iter->first << " value:" << iter->second << std::endl;
}
std::cout << "-------------------" << std::endl;
// 关系视图
map.insert(container_type::value_type(1002, "李七"));
map.insert({ 1001, "赵八" });
for (container_type::const_iterator iter = map.begin(), end = map.end(); iter != end; ++iter)
{
std::cout << "key:" << iter->left << " value:" << iter->right << std::endl;
}
std::cout << "-------------------" << std::endl;
}
int main()
{
test();
return 0;
}
#endif
程序输出结果：
key:1005 value:李四
key:1006 value:张三
-------------------
key:李四 value:1005
key:王五 value:1004
key:张三 value:1006
key:赵六 value:1003
-------------------
key:1001 value:赵八
key:1002 value:李七
key:1003 value:赵六
key:1004 value:王五
key:1005 value:李四
key:1006 value:张三
-------------------
**注意：**插入数据时，使用视图的 value_type 来构造插入对象，比 std::make_pair 效率高。这是因为 std::pair 需要转换为 bimap pair，而 value_type 则不需要。
- 集合类型 {#title-1} ==================
Boost Bimap 提供了多种集合类型 (collection types)，这些集合类型规定了不同的数据存储和访问方式，每种集合类型都有其特定的用途和优势，使开发者能够根据实际场景灵活的选择和组合。
2.1 使用方法 {#title-2}
Boost Bimap 支持的集合类型如下表所示，我们可以根据需求来选择不同的左右集合类型组合，默认左右集合都是使用 set_of 进行存储和访问。
#if 1
#include <boost/bimap/bimap.hpp>
#include <boost/bimap/set_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/list_of.hpp>
#include <boost/bimap/vector_of.hpp>
#include <boost/bimap/support/lambda.hpp>
#include <iostream>
#include <algorithm>
using namespace boost::bimaps;
using namespace std;
// 1. set_of multiset_of
void test01()
{
// 左视图有序，唯一、右视图有序，不唯一
using container_type = bimap<set_of<int>, multiset_of<string>>;
container_type map;
// 注意: 添加的元素必须满足所有视图的约束(左视图、右视图、关系视图)
map.left.insert(container_type::left_value_type(1001, "张三"));
map.left.insert(container_type::left_value_type(1001, "李四"));
map.right.insert(container_type::right_value_type("王五", 1003));
map.right.insert(container_type::right_value_type("王五", 1004));
map.right.insert(container_type::right_value_type("赵六", 1005));
for_each(map.begin(), map.end(), [](auto& item) { cout << item.left << " " << item.right << endl; });
cout << "------------" << endl;
// 查找指定 key 元素
// 查找失败返回 end 迭代器
auto position = map.left.find(1001);
if (position != map.left.end())
{
cout << position->first << " " << position->second << endl;
cout << "------------" << endl;
}
// 删除元素
map.left.erase(position);
for_each(map.begin(), map.end(), [](auto& item) { cout << item.left << " " << item.right << endl; });
cout << "------------" << endl;
// 查找全部相同元素
auto pair = map.right.equal_range("王五");
for_each(pair.first, pair.second, [](auto& item) {cout << item.first << " " << item.second << endl; });
cout << "------------" << endl;
// 查找区间元素 [
// 1003, 1004]
auto iter_beg = map.left.lower_bound(1003); // 大于等于
auto iter_end = map.left.upper_bound(1004); // 大于
for_each(iter_beg, iter_end, [](auto& item) {cout << item.first << " " << item.second << endl; });
cout << "------------" << endl;
// auto pair = map.left.range(1001 <= _key, _key <= 1003); // [1001, 1003]
auto range_pair = map.left.range(unbounded, _key < 1005); // (-inf, 1005)
cout << range_pair.first->first << " " << range_pair.second->first << endl;
cout << "------------" << endl;
}
void test02()
{
// 左视图无序，唯一、右视图无序，不唯一
using container_type = bimap<unordered_set_of<int>, unordered_multiset_of<string>>;
container_type map;
map.left.insert(container_type::left_value_type(1001, "张三"));
map.left.insert(container_type::left_value_type(1001, "李四"));
map.right.insert(container_type::right_value_type("王五", 1003));
map.right.insert(container_type::right_value_type("王五", 1004));
map.right.insert(container_type::right_value_type("赵六", 1005));
for_each(map.begin(), map.end(), [](auto& item) { cout << item.left << " " << item.right << endl; });
cout << "------------" << endl;
// 查找指定 key 元素
// 查找失败返回 end 迭代器
auto position = map.left.find(1001);
if (position != map.left.end())
{
cout << position->first << " " << position->second << endl;
cout << "------------" << endl;
}
// unordered_set 不存在 lower_bound 、upper_bound、range 函数
auto pair = map.right.equal_range("王五");
for_each(pair.first, pair.second, [](auto& item) {cout << item.first << " " << item.second << endl; });
cout << "------------" << endl;
}
void test03()
{
// 左视图顺序、右视图随机访问
using container_type = bimap<list_of<int>, vector_of<string>>;
container_type map;
map.left.push_back(container_type::left_value_type(1001, "张三"));
map.left.push_back(container_type::left_value_type(1001, "李四"));
map.right.push_front(container_type::right_value_type("王五", 1003));
map.right.push_front(container_type::right_value_type("王五", 1004));
for_each(map.begin(), map.end(), [](auto& item) { cout << item.left << " " << item.right << endl; });
cout << "------------" << endl;
// 修改元素
map.left.begin()->second = "GGG";
// 排序
map.left.sort(std::greater<int>());
for_each(map.begin(), map.end(), [](auto& item) { cout << item.left << " " << item.right << endl; });
cout << "------------" << endl;
// 删除元素
map.left.erase(map.left.begin());
for_each(map.begin(), map.end(), [](auto& item) { cout << item.left << " " << item.right << endl; });
cout << "------------" << endl;
container_type temp;
temp.push_back(container_type::value_type(2001, "aaa"));
temp.push_back(container_type::value_type(2002, "bbb"));
temp.push_back(container_type::value_type(2003, "ccc"));
temp.push_back(container_type::value_type(2004, "ddd"));
temp.push_back(container_type::value_type(2005, "ddd"));
// 合并容器
map.left.merge(temp.left);
cout << "------------" << endl;
for_each(map.begin(), map.end(), [](auto& item) { cout << item.left << " " << item.right << endl; });
cout << "------------" << endl;
// 右视图访问
cout << map.right[0].first << " " << map.right[0].second << endl;
}
int main()
{
test03();
return 0;
}
#endif
2.2 集合参数 {#title-3}
#if 1
#include <boost/bimap/bimap.hpp>
#include <boost/bimap/set_of.hpp>
#include <boost/bimap/unordered_set_of.hpp>
#include <boost/functional/hash.hpp>
#include <iostream>
using namespace std;
using namespace boost::bimaps;
class Person
{
public:
Person(string name, int age)
{
m_name = name;
m_age = age;
}
public:
std::string m_name;
int m_age;
};
struct LessPerson
{
bool operator()(const Person& p1, const Person& p2) const
{
return p1.m_age < p2.m_age;
}
};
void test01()
{
using container_type = bimap<int, set_of<Person, LessPerson>>;
container_type map;
// 由于右集合使用 set 容器，该容器会自动排序，对自定义类型要重载 < 运算符或者一个谓词作为模板参数
map.insert(container_type::value_type(1001, { "Smith", 100 }));
map.insert(container_type::value_type(1002, { "Obama", 200 }));
map.insert(container_type::value_type(1003, { "Polly", 150 }));
for_each(map.begin(), map.end(), [](const auto& item) {
cout << item.left << " " << item.right.m_name << " " << item.right.m_age << endl;
});
}
struct EqualPerson
{
bool operator()(const Person& p1, const Person& p2) const
{
return p1.m_name == p2.m_name && p1.m_age == p2.m_age;
}
};
struct HashPerson
{
size_t operator()(const Person& person) const
{
return boost::hash<string>()(person.m_name);
}
};
void test02()
{
using container_type = bimap<int, unordered_set_of<Person, HashPerson, EqualPerson>>;
container_type map;
// 由于右集合使用哈希表，该容器要求元素能够被哈希，能够使用 < 比较，所以需要提供一个针对该类型的哈希函数，以及==比较规则
map.insert(container_type::value_type(1001, { "Smith", 100 }));
map.insert(container_type::value_type(1002, { "Obama", 200 }));
map.insert(container_type::value_type(1003, { "Polly", 150 }));
for_each(map.begin(), map.end(), [](const auto& item) {
cout << item.left << " " << item.right.m_name << " " << item.right.m_age << endl;
});
}
int main()
{
test01();
cout << "------------" << endl;
test02();
return 0;
}
#endif
程序执行结果：
1001 Smith 100
1002 Obama 200
1003 Polly 150
------------
1001 Smith 100
1002 Obama 200
1003 Polly 150
2.3 无约束类型 {#title-4}
unconstrained_set_of 称作无约束集合类型，该集合类型并不提供任何对数据的操作。所以，将左视图或者右视图设置为无约束集合类型，可以实现：
- 禁用某个视图：禁用 bimap 中的一个视图可以提高操作的执行速度并减少内存消耗
- 实现单向映射：通过禁用一个视图，bimap 变成单向映射，而不是双向映射
#if 1
#include <boost/bimap/bimap.hpp>
#include <boost/bimap/unconstrained_set_of.hpp>
#include <iostream>
using namespace std;
using namespace boost::bimaps;
void test()
{
// 相当于单向容器
using container_type = bimap<int, unconstrained_set_of<std::string>>;
container_type map;
map.insert(container_type::value_type(1001, "张三"));
map.left.insert(container_type::left_value_type(1002, "李四"));
// 无法使用右视图执行插入操作
for_each(map.begin(), map.end(), [](const auto& item) {
cout << item.left << " " << item.right << endl;
});
}
int main()
{
test();
return 0;
}
#endif
程序执行结果：
1001 张三
1002 李四
- 关系类型 {#title-5} ==================
Boost Bimap 容器的关系视图就是将键值对作为一个整体，一个元素对待，关系类型则是考虑如何存储这些关系（键值对）。
3.1 基本使用 {#title-6}
默认情况下，Boost.Bimap 会基于其中一侧（左侧或右侧）的集合类型来确定关系集合的类型。例如：左集合类型是 set，那么关系集合的类型也会是具有相同顺序的 set。
然而，在某些情况下，用户可能希望对关系集合施加不同的约束或使用不同的排序方式。
- left_based：基于左侧集合类型。
- right_based：基于右侧集合类型。
- set_of_relation<>：有序集合。
- multiset_of_relation<>：有序多重集合，允许重复元素。
- unordered_set_of_relation<>：无序集合。
- unordered_multiset_of_relation<>：无序多重集合，允许重复元素。
- list_of_relation：列表形式的集合，保持插入顺序。
- vector_of_relation：向量形式的集合，允许快速随机访问。
- unconstrained_set_of_relation：不受约束的集合，可以在性能和内存使用方面进行优化。
#if 1
#include <boost/bimap/bimap.hpp>
#include <boost/bimap/set_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/vector_of.hpp>
#include <boost/bimap/list_of.hpp>
#include <boost/bimap/unconstrained_set_of.hpp>
#include <iostream>
using namespace std;
using namespace boost::bimaps;
void test01()
{
// 使用 set 存储键值对
using container_type = bimap<unconstrained_set_of<int>, unconstrained_set_of<string>, set_of_relation<>>;
container_type map;
// 插入元素必须满足三个视图的约束
map.insert(container_type::value_type(1001, "张三"));
map.insert(container_type::value_type(1002, "李四"));
map.insert(container_type::value_type(1001, "李四"));
map.insert(container_type::value_type(1002, "李四"));
for_each(map.begin(), map.end(), [](const auto& item) {
cout << item.left << " " << item.right << endl;
});
cout << "-------------" << endl;
}
void test02()
{
// 使用哈希表存储键值对
using container_type = bimap<unconstrained_set_of<int>, unconstrained_set_of<string>, unordered_set_of_relation<>>;
container_type map;
map.insert(container_type::value_type(1001, "张三"));
map.insert(container_type::value_type(1002, "李四"));
map.insert(container_type::value_type(1001, "李四"));
map.insert(container_type::value_type(1002, "李四"));
for_each(map.begin(), map.end(), [](const auto& item) {
cout << item.left << " " << item.right << endl;
});
cout << "-------------" << endl;
}
void test03()
{
// 使用 vector 存储键值对
using container_type = bimap<unconstrained_set_of<int>, unconstrained_set_of<string>, vector_of_relation>;
container_type map;
map.push_back(container_type::value_type(1001, "张三"));
map.push_back(container_type::value_type(1002, "李四"));
map.push_back(container_type::value_type(1001, "李四"));
map.push_back(container_type::value_type(1002, "李四"));
for (int i = 0; i < map.size(); ++i)
{
cout << map[i].left << " " << map[i].right << endl;
}
cout << "-------------" << endl;
}
void test04()
{
// 移除关系视图，则无法使用关系视图进行操作
using container_type = bimap<int, string, unconstrained_set_of_relation>;
container_type map;
map.left.insert(container_type::left_value_type(1001, "张三"));
map.left.insert(container_type::left_value_type(1002, "李四"));
map.left.insert(container_type::left_value_type(1001, "李四"));
map.left.insert(container_type::left_value_type(1002, "李四"));
for_each(map.left.begin(), map.left.end(), [](const auto& item) {
cout << item.first << " " << item.second << endl;
});
cout << "-------------" << endl;
}
int main()
{
test01();
test02();
test03();
test04();
return 0;
}
#endif
3.2 关系参数 {#title-7}
#if 1
#include <boost/bimap/bimap.hpp>
#include <boost/bimap/set_of.hpp>
#include <boost/bimap/unordered_set_of.hpp>
#include <iostream>
using namespace std;
using namespace boost::bimaps;
class Person
{
public:
Person(string name, int age)
{
m_name = name;
m_age = age;
}
public:
string m_name;
int m_age;
};
template<class Rel>
struct CompareRelation
{
bool operator()(Rel r1, Rel r2) const
{
cout << r1.left << " " << r1.right.m_name << " " << r1.right.m_age << endl;
cout << r2.left << " " << r2.right.m_name << " " << r2.right.m_age << endl;
cout << "------------" << endl;
return r1.left < r2.left;
}
};
struct ComparePerson
{
bool operator()(const Person& p1, const Person& p2) const
{
return p1.m_age < p2.m_age;
}
};
void test01()
{
// 对于右视图：由于使用 set，所以需要提供 Person 的 < 比较规则
// 对于关系视图：由于使用 set，所以需要提供 relation 的 < 比较规则
// _relation 是一个占位符，当模板实例化时，占位符会被实际的 relation 类型替换
using container_type = bimap<int, set_of<Person, ComparePerson>, set_of_relation< CompareRelation<_relation> >>;
container_type map;
map.insert(container_type::value_type(1001, { "张三", 18 }));
map.insert(container_type::value_type(1002, { "李四", 20 }));
// 查找
map.find(container_type::value_type(1001, { "张三", 18 }));
}
template<class Rel>
struct EqualRelation
{
bool operator()(Rel r1, Rel r2) const
{
return r1.left == r2.left && r1.right.m_name == r2.right.m_name && r1.right.m_age == r2.right.m_age;
}
};
template <class Rel>
struct HashRelation
{
size_t operator()(Rel rel) const
{
// 将 {1001, {"张三", 20}} 封装成 tuple 对象
// 使用内 hash 函数对 tuple 对象进行 hash
return boost::hash<std::tuple<int, int, string>>()(std::tuple<int, int, string>(rel.left, rel.right.m_age, rel.right.m_name));
}
};
void test02()
{
using container_type = bimap<int, unconstrained_set_of<Person>, unordered_set_of_relation< HashRelation<_relation>, EqualRelation<_relation> >>;
container_type map;
map.insert(container_type::value_type(1001, { "张三", 18 }));
map.insert(container_type::value_type(1002, { "李四", 20 }));
// 查找
auto it = map.find(container_type::value_type(1002, { "李四", 20 }));
if (it != map.end())
{
cout << "find:" << it->left << " " << it->right.m_name << " " << it->right.m_age << endl;
}
}
int main()
{
test01();
test02();
return 0;
}
#endif
程序执行结果：
1002 李四 20
1001 张三 18
------------
1001 张三 18
1002 李四 20
------------
1001 张三 18
1001 张三 18
------------
1001 张三 18
1001 张三 18
------------
find:1002 李四 20
- 视图标签 {#title-8} ==================
默认情况下，我们使用
#if 1
#include <boost/bimap/bimap.hpp>
#include <boost/bimap/set_of.hpp>
#include <iostream>
using namespace std;
using namespace boost::bimaps;
void test()
{
// 给左右集合设置标签
using container_type = bimap<tagged<int, struct id>, set_of<tagged<string, struct name>>>;
container_type map;
// map.left
// map.right
map.by<id>();
map.by<name>();
// container_type::left_value_type
// container_type::right_value_type
map.by<id>().insert(container_type::map_by<id>::value_type(1001, "张三"));
map.by<name>().insert(container_type::map_by<name>::value_type("李四", 1002));
// container_type::left_const_iterator
// container_type::right_const_iterator
for (container_type::map_by<id>::const_iterator it = map.by<id>().begin(); it != map.by<id>().end(); ++it)
{
// it->first
// it->second
cout << it->get<id>() << " " << it->get<name>() << endl;
}
cout << "---------" << endl;
for (container_type::const_iterator it = map.begin(); it != map.end(); ++it)
{
// it->left
// it->right
cout << it->get<id>() << " " << it->get<name>() << endl;
}
}
int main()
{
test();
return 0;
}
#endif
程序执行结果：
1001 张三
1002 李四
---------
1001 张三
1002 李四
- 附加信息 {#title-9} ==================
Boost Bimap 支持为每一个 relation 增加一个附加消息。
#if 1
#include <boost/bimap/bimap.hpp>
#include <iostream>
using namespace std;
using namespace boost::bimaps;
void test()
{
// using container_type = bimap<int, std::string, with_info<string>>;
// using container_type = bimap<int, std::string, set_of_relation<>, with_info<string>>;
using container_type = bimap<tagged<int, struct id>, tagged<string, struct name>, with_info<tagged<string, struct extra>>>;
container_type map;
map.insert(container_type::value_type(1001, "张三", "学生1信息"));
map.insert(container_type::value_type(1002, "李四", "学生2信息"));
map.insert(container_type::value_type(1003, "王五", "学生3信息"));
// 修改附加信息
map.begin()->info = "修改信息";
for (auto& student : map)
{
cout << student.left << " " << student.right << " " << student.info << endl;
cout << student.get<id>() << " " << student.get<name>() << " " << student.get<extra>() << endl;
}
}
int main()
{
test();
return 0;
}
#endif
程序执行结果：
1001 张三 修改信息
1001 张三 修改信息
1002 李四 学生2信息
1002 李四 学生2信息
1003 王五 学生3信息
1003 王五 学生3信息
- 实用函数 {#title-10} ===================
#if 1
#include <boost/bimap/bimap.hpp>
#include <boost/bimap/support/lambda.hpp>
#include <iostream>
#include <type_traits>
using namespace std;
using namespace boost::bimaps;
// 1. 修改 key 或者 data
void test01()
{
using container_type = boost::bimaps::bimap<int, string>;
container_type map;
map.insert(container_type::value_type(1001, "张三"));
map.insert(container_type::value_type(1002, "李四"));
map.insert(container_type::value_type(1003, "王五"));
for_each(map.begin(), map.end(), [](const auto& item) { cout << item.left << " " << item.right << endl; });
cout << "---------" << endl;
// 1. replace 修改 key 和 data
map.left.replace_key(map.left.begin(), 2002);
for_each(map.begin(), map.end(), [](const auto& item) { cout << item.left << " " << item.right << endl; });
cout << "---------" << endl;
map.left.replace_data(map.left.begin(), "王五-修改");
for_each(map.begin(), map.end(), [](const auto& item) { cout << item.left << " " << item.right << endl; });
cout << "---------" << endl;
// 2. modify 修改 key 和 data
map.left.modify_key(map.left.begin(), _key = 1111);
for_each(map.begin(), map.end(), [](const auto& item) { cout << item.left << " " << item.right << endl; });
cout << "---------" << endl;
map.left.modify_data(map.left.begin(), _data = "王五-修改");
for_each(map.begin(), map.end(), [](const auto& item) { cout << item.left << " " << item.right << endl; });
cout << "---------" << endl;
// 注意：迭代器类型要选择对应视图类型的迭代器
}
// 2. 迭代器视图类型转换
void test02()
{
using container_type = boost::bimaps::bimap<int, string>;
container_type map;
map.insert(container_type::value_type(1001, "张三"));
map.insert(container_type::value_type(1002, "李四"));
map.insert(container_type::value_type(1003, "王五"));
auto iter = map.begin();
auto left_iter = map.left.begin();
auto right_iter = map.right.begin();
// 转换到视图迭代器
auto up1 = map.project_up(left_iter);
auto up2 = map.project_up(right_iter);
cout << is_same<decltype(up1), container_type::iterator>::value << endl;
cout << is_same<decltype(up2), container_type::iterator>::value << endl;
// 转换到左视图迭代器
auto left1 = map.project_left(iter);
auto left2 = map.project_left(right_iter);
cout << is_same<decltype(left1), container_type::left_iterator>::value << endl;
cout << is_same<decltype(left2), container_type::left_iterator>::value << endl;
// 转到右视图迭代器
auto right1 = map.project_right(iter);
auto right2 = map.project_right(left_iter);
cout << is_same<decltype(right1), container_type::right_iterator>::value << endl;
cout << is_same<decltype(right2), container_type::right_iterator>::value << endl;
// 使用场景
map.replace_left(map.project_up(map.right.find("李四")), 2001);
for_each(map.begin(), map.end(), [](const auto& item) { cout << item.left << " " << item.right << endl; });
}
int main()
{
test01();
test02();
return 0;
}
#endif
程序执行结果：
1001 张三
1002 李四
1003 王五
---------
1002 李四
1003 王五
2002 张三
---------
1002 王五-修改
1003 王五
2002 张三
---------
1003 王五
1111 王五-修改
2002 张三
---------
1111 王五-修改
2002 张三
---------
1
1
1
1
1
1
1001 张三
1003 王五
2001 李四
