• 13.4. Boost.MultiIndex

    13.4. Boost.MultiIndex

    Boost.MultiIndex 比我们之前介绍的任何库都要复杂。 不像 Boost.Array 和 Boost.Unordered 为我们提供了可以直接使用的容器， Boost.MultiIndex 让我们可以自定义新的容器。 跟 C++ 标准中的容器不同的是： 一个用户自定义的容器可以对其中的数据提供多组访问接口。 举例来说， 你可以定义一个类似于 std::map 的容器， 但它可以通过 value 值来查询。 如果不用 Boost.MultiIndex， 你就需要自己整合两个 std::map 类型的容器， 还要自己处理一些同步操作来确保数据的完整性。

    下面这个例子就用 Boost.MultiIndex 定义了一个新容器来存储每个人的 name 和 age， 不像 std::map， 这个容器可以分别通过 name 和 age 来查询（std::map 只能用一个值）。

    1. #include <boost/multi_index_container.hpp> 
    2. #include <boost/multi_index/hashed_index.hpp> 
    3. #include <boost/multi_index/member.hpp> 
    4. #include <iostream> 
    5. #include <string> 
    6.  
    7. struct person 
    8. { 
    9.   std::string name; 
    10.   int age; 
    11.  
    12.   person(const std::string &n, int a) 
    13.     : name(n), age(a) 
    14.   { 
    15.   } 
    16. }; 
    17.  
    18. typedef boost::multi_index::multi_index_container< 
    19.   person, 
    20.   boost::multi_index::indexed_by< 
    21.     boost::multi_index::hashed_non_unique< 
    22.       boost::multi_index::member< 
    23.         person, std::string, &person::name 
    24.       > 
    25.     >, 
    26.     boost::multi_index::hashed_non_unique< 
    27.       boost::multi_index::member< 
    28.         person, int, &person::age 
    29.       > 
    30.     > 
    31.   > 
    32. > person_multi; 
    33.  
    34. int main() 
    35. { 
    36.   person_multi persons; 
    37.  
    38.   persons.insert(person("Boris", 31)); 
    39.   persons.insert(person("Anton", 35)); 
    40.   persons.insert(person("Caesar", 25)); 
    41.  
    42.   std::cout << persons.count("Boris") << std::endl; 
    43.  
    44.   const person_multi::nth_index<1>::type &age_index = persons.get<1>(); 
    45.   std::cout << age_index.count(25) << std::endl; 
    46. }
    • 下载源代码

    就像上面提到的， Boost.MultiIndex 并没有提供任何特定的容器而是一些类来方便我们定义新的容器。 典型的做法是： 你需要用到 typedef 来为你的新容器提供对 Boost.MultiIndex 中类的方便的访问。

    每个容器定义都需要的类 boost::multi_index::multi_index_container 被定义在了 boost/multi_index_container.hpp 里。 因为他是一个模板类， 你需要为它传递两个模板参数。 第一个参数是容器中储存的元素类型， 在例子中是 person； 而第二个参数指明了容器所提供的所有索引类型。

    基于 Boost.MultiIndex 的容器最大的优势在于： 他对一组同样的数据提供了多组访问接口。 访问接口的具体细节都可以在定义容器时被指定。 因为例子中的 person 为 age 和 name 都提供了查询功能， 我们必须要定义两组接口。

    接口的定义必须借由模板类 boost::multi_index::indexed_by 来实现。 每一个接口都作为参数传递给它。 例子中定义了两个 boost::multi_index::hashed_non_unique 类型的接口，（定义在头文件 boost/multi_index/hashed_index.hpp 中） 如果你希望容器像 Boost.Unordered 一样存储一些可以计算 Hash 值的元素， 你就可以使用这个接口。

    boost::multi_index::hashed_non_unique 是一个模板类， 他需要一个可计算 Hash 值的类型作为它的参数。 因为接口需要访问 person 中的 name 和 age， 所以 name 和 age 都要是可计算 Hash 值的。

    Boost.MultiIndex 提供了一个辅助模板类： boost::multi_index::member （定义在 boost/multi_index/member.hpp 中） 来访问类中的属性。 就像我们在例子中所看到的， 我们指定了好几个参数来让 boost::multi_index::member 明白可以访问 person 中的哪些属性以及这些属性的类型。

    不得不说 person_multi 的定义第一眼看起来相当复杂， 但这个类本身跟 Boost.Unordered 中的 boost::unordered_map 并没有什么不同， 他也可以分别通过其中的两个属性 name 和 age 来查询容器。

    为了访问 MultiIndex 容器， 你必须要定义至少一个接口。 如果用 insert() 或者 count() 来直接访问 persons 对象， 第一个接口会被隐式的调用 —— 在例子中是 name 属性的 Hash 容器。 如果你想用其他接口， 你必须要显示的指定它。

    接口都是用从0开始的索引值来编号的。 想要访问第二个接口， 你需要调用 get() 函数并且传入想要访问的接口的索引值。

    函数 get() 的返回值看起来也有点复杂： 他是一个用来访问 MultiIndex 容器的类 nth_index ， 同样的， 你也需要指定需要访问的接口的索引值。 当然， 这个值肯定跟 get() 函数指定的模板参数是一样的。 最后一步： 用 :: 来得到 nth_index 的 type， 也就是接口的真正的type。

    虽然我们并不知道细节就用 nthindex 和 type 得到了接口， 我们还是需要明白这到底是什么接口。 通过传给 get() 和 nth_index 的索引值， 我们就可以很容易得知所使用的哪一个接口了。 例子中的 _age_index 就是一个通过 age 来访问的 Hash 容器。

    既然 MultiIndex 容器中的 name 和 key 作为了接口访问的键值， 他们都不能再被更改了。 比如一个 person 的 age 在通过 name 搜索以后被改变了， 使用 age 作为键值的接口却意识不到这种更改， 因此， 你需要重新计算 Hash 值才行。

    就像 std::map 一样， MultiIndex 容器中的值也不允许被修改。 严格的说， 所有存储在 MultiIndex 中的元素都该是常量。 为了避免删除或修改其中元素真正的值， Boost.MultiIndex 提供了一些常用函数来操作其中的元素。 使用这些函数来操作 MultiIndex 容器中的值并不会引起那些元素所指向的真正的对象改变， 所以更新动作是安全的。 而且所有接口都会被通知这种改变， 然后去重新计算新的 Hash 值等。

    1. #include <boost/multi_index_container.hpp> 
    2. #include <boost/multi_index/hashed_index.hpp> 
    3. #include <boost/multi_index/member.hpp> 
    4. #include <iostream> 
    5. #include <string> 
    6.  
    7. struct person 
    8. { 
    9.   std::string name; 
    10.   int age; 
    11.  
    12.   person(const std::string &n, int a) 
    13.     : name(n), age(a) 
    14.   { 
    15.   } 
    16. }; 
    17.  
    18. typedef boost::multi_index::multi_index_container< 
    19.   person, 
    20.   boost::multi_index::indexed_by< 
    21.     boost::multi_index::hashed_non_unique< 
    22.       boost::multi_index::member< 
    23.         person, std::string, &person::name 
    24.       > 
    25.     >, 
    26.     boost::multi_index::hashed_non_unique< 
    27.       boost::multi_index::member< 
    28.         person, int, &person::age 
    29.       > 
    30.     > 
    31.   > 
    32. > person_multi; 
    33.  
    34. void set_age(person &p) 
    35. { 
    36.   p.age = 32; 
    37. } 
    38.  
    39. int main() 
    40. { 
    41.   person_multi persons; 
    42.  
    43.   persons.insert(person("Boris", 31)); 
    44.   persons.insert(person("Anton", 35)); 
    45.   persons.insert(person("Caesar", 25)); 
    46.  
    47.   person_multi::iterator it = persons.find("Boris"); 
    48.   persons.modify(it, set_age); 
    49.  
    50.   const person_multi::nth_index<1>::type &age_index = persons.get<1>(); 
    51.   std::cout << age_index.count(32) << std::endl; 
    52. }
    • 下载源代码

    每个 Boost.MultiIndex 中的接口都支持 modify() 函数来提供直接对容器本身的操作。 它的第一个参数是一个需要更改对象的迭代器； 第二参数则是一个对该对象进行操作的函数。 在例子中， 对应的两个参数则是： person 和 set_age() 。

    至此， 我们都还只介绍了一个接口： boost::multi_index::hashed_non_unique ， 他会计算其中元素的 Hash 值， 但并不要求是唯一的。 为了确保容器中存储的值是唯一的， 你可以使用 boost::multi_index::hashed_unique 接口。 请注意： 所有要被存入容器中的值都必须满足它的接口的限定。 只要一个接口限定了容器中的值必须是唯一的， 那其他接口都不会对该限定造成影响。

    1. #include <boost/multi_index_container.hpp> 
    2. #include <boost/multi_index/hashed_index.hpp> 
    3. #include <boost/multi_index/member.hpp> 
    4. #include <iostream> 
    5. #include <string> 
    6.  
    7. struct person 
    8. { 
    9.   std::string name; 
    10.   int age; 
    11.  
    12.   person(const std::string &n, int a) 
    13.     : name(n), age(a) 
    14.   { 
    15.   } 
    16. }; 
    17.  
    18. typedef boost::multi_index::multi_index_container< 
    19.   person, 
    20.   boost::multi_index::indexed_by< 
    21.     boost::multi_index::hashed_non_unique< 
    22.       boost::multi_index::member< 
    23.         person, std::string, &person::name 
    24.       > 
    25.     >, 
    26.     boost::multi_index::hashed_unique< 
    27.       boost::multi_index::member< 
    28.         person, int, &person::age 
    29.       > 
    30.     > 
    31.   > 
    32. > person_multi; 
    33.  
    34. int main() 
    35. { 
    36.   person_multi persons; 
    37.  
    38.   persons.insert(person("Boris", 31)); 
    39.   persons.insert(person("Anton", 31)); 
    40.   persons.insert(person("Caesar", 25)); 
    41.  
    42.   const person_multi::nth_index<1>::type &age_index = persons.get<1>(); 
    43.   std::cout << age_index.count(31) << std::endl; 
    44. }
    • 下载源代码

    上例中的容器现在使用了 boost::multi_index::hashed_unique 来作为他的第二个接口， 因此他不允许其中有两个同 age 的 person 存在。

    上面的代码尝试存储一个与 Boris 同 age 的 Anton， 因为这个动作违反了容器第二个接口的限定， 它（Anton）将不会被存入到容器中。 因此， 程序将会输出： 1 而不是2。

    接下来的例子向我们展示了 Boost.MultiIndex 中剩下的三个接口： boost::multi_index::sequenced， boost::multi_index::ordered_non_unique 和 boost::multi_index::random_access。

    1. #include <boost/multi_index_container.hpp> 
    2. #include <boost/multi_index/sequenced_index.hpp> 
    3. #include <boost/multi_index/ordered_index.hpp> 
    4. #include <boost/multi_index/random_access_index.hpp> 
    5. #include <boost/multi_index/member.hpp> 
    6. #include <iostream> 
    7. #include <string> 
    8.  
    9. struct person 
    10. { 
    11.   std::string name; 
    12.   int age; 
    13.  
    14.   person(const std::string &n, int a) 
    15.     : name(n), age(a) 
    16.   { 
    17.   } 
    18. }; 
    19.  
    20. typedef boost::multi_index::multi_index_container< 
    21.   person, 
    22.   boost::multi_index::indexed_by< 
    23.     boost::multi_index::sequenced<>, 
    24.     boost::multi_index::ordered_non_unique< 
    25.       boost::multi_index::member< 
    26.         person, int, &person::age 
    27.       > 
    28.     >, 
    29.     boost::multi_index::random_access<> 
    30.   > 
    31. > person_multi; 
    32.  
    33. int main() 
    34. { 
    35.   person_multi persons; 
    36.  
    37.   persons.push_back(person("Boris", 31)); 
    38.   persons.push_back(person("Anton", 31)); 
    39.   persons.push_back(person("Caesar", 25)); 
    40.  
    41.   const person_multi::nth_index<1>::type &ordered_index = persons.get<1>(); 
    42.   person_multi::nth_index<1>::type::iterator lower = ordered_index.lower_bound(30); 
    43.   person_multi::nth_index<1>::type::iterator upper = ordered_index.upper_bound(40); 
    44.   for (; lower != upper; ++lower) 
    45.     std::cout << lower->name << std::endl; 
    46.  
    47.   const person_multi::nth_index<2>::type &random_access_index = persons.get<2>(); 
    48.   std::cout << random_access_index[2].name << std::endl; 
    49. }
    • 下载源代码

    boost::multi_index::sequenced 接口让我们可以像使用 std::list 一样的使用 MultiIndex。 这个接口定义起来十分容易： 你不用为它传递任何模板参数。 person 类型的对象在容器中就是像 list 一样按照加入的顺序来排列的。

    而通过使用 boost::multi_index::ordered_non_unique 接口， 容器中的对象会自动的排序。 你在定义容器时就必须指定接口的排序规则。 示例中的对象 person 就是以 age 来排序的， 它借助了辅助类 boost::multi_index::member 来实现这一功能。

    boost::multi_index::ordered_non_unique 为我们提供了一些特别的函数来查找特定范围的数据。 通过使用 lower_bound() 和 upper_bound()， 示例实现了对所有 30 岁至 40 岁的 person 的查询。 要注意因为容器中的数据是有序的， 所以才提供了这些函数， 其他接口中并不提供这些函数。

    最后一个接口是： boost::multi_index::random_access， 他让我们可以像使用 std::vector 一样使用 MultiIndex 容器。 你又可以使用你熟悉的 operator 和 at() 操作了。

    请注意 boost::multi_index::random_access 已经被完整的包含在了 boost::multi_index::sequenced 接口中。 所以当你使用 boost::multi_index::random_access 的时候， 你也可以使用 boost::multi_index::sequenced 接口中的所有函数。

    在介绍完 Boost.MultiIndex 剩下的4个接口后， 本章剩下的部分将向你介绍所谓的“键值提取器”（key extractors）。 目前为止， 我们已经见过一个在 boost/multi_index/member.hpp 定义的键值提取器了—— boost::multi_index::member 。 这个辅助函数的得名源自它可以显示的声明类中的哪些属性会作为接口中的键值使用。

    接下来的例子介绍了另外两个键值提取器。

    1. #include <boost/multi_index_container.hpp> 
    2. #include <boost/multi_index/ordered_index.hpp> 
    3. #include <boost/multi_index/hashed_index.hpp> 
    4. #include <boost/multi_index/identity.hpp> 
    5. #include <boost/multi_index/mem_fun.hpp> 
    6. #include <iostream> 
    7. #include <string> 
    8.  
    9. class person 
    10. { 
    11. public: 
    12.   person(const std::string &n, int a) 
    13.     : name(n), age(a) 
    14.   { 
    15.   } 
    16.  
    17.   bool operator<(const person &p) const 
    18.   { 
    19.     return age < p.age; 
    20.   } 
    21.  
    22.   std::string get_name() const 
    23.   { 
    24.     return name; 
    25.   } 
    26.  
    27. private: 
    28.   std::string name; 
    29.   int age; 
    30. }; 
    31.  
    32. typedef boost::multi_index::multi_index_container< 
    33.   person, 
    34.   boost::multi_index::indexed_by< 
    35.     boost::multi_index::ordered_unique< 
    36.       boost::multi_index::identity<person> 
    37.     >, 
    38.     boost::multi_index::hashed_unique< 
    39.       boost::multi_index::const_mem_fun< 
    40.         person, std::string, &person::get_name 
    41.       > 
    42.     > 
    43.   > 
    44. > person_multi; 
    45.  
    46. int main() 
    47. { 
    48.   person_multi persons; 
    49.  
    50.   persons.insert(person("Boris", 31)); 
    51.   persons.insert(person("Anton", 31)); 
    52.   persons.insert(person("Caesar", 25)); 
    53.  
    54.   std::cout << persons.begin()->get_name() << std::endl; 
    55.  
    56.   const person_multi::nth_index<1>::type &hashed_index = persons.get<1>(); 
    57.   std::cout << hashed_index.count("Boris") << std::endl; 
    58. }
    • 下载源代码

    键值提取器boost::multi_index::identity（定义在 boost/multi_index/identity.hpp 中） 可以使用容器中的数据类型作为键值。 示例中， 就需要 person 类是可排序的， 因为它已经作为了接口 boost::multi_index::ordered_unique 的键值。 在示例里， 它是通过重载 operator<() 操作符来实现的。

    头文件 boost/multi_index/mem_fun.hpp 定义了两个可以把函数返回值作为键值的键值提取器： boost::multi_index::const_mem_fun 和 boost::multi_index::mem_fun 。 在示例程序中， 就是用到了 get_name() 的返回值作为键值。 显而易见的， boost::multi_index::const_mem_fun 适用于返回常量的函数， 而 boost::multi_index::mem_fun 适用于返回非常量的函数。

    Boost.MultiIndex 还提供了两个键值提取器： boost::multi_index::global_fun 和 boost::multi_index::composite_key。 前一个适用于独立的函数或者静态函数， 后一个允许你将几个键值提取器组合成一个新的的键值提取器。