Chinaunix首页 | 论坛 | 博客
  • 博客访问: 559272
  • 博文数量: 104
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1559
  • 用 户 组: 普通用户
  • 注册时间: 2014-08-21 00:58
个人简介

锻炼精神,首先要锻炼肉体

文章分类

全部博文(104)

文章存档

2018年(1)

2016年(1)

2015年(101)

2014年(1)

我的朋友

分类: C/C++

2015-05-30 19:04:16

这篇文章简单介绍一下 boost 中十分实用的库函数 --- 多重索引 multi_index ,它的底层结构是用来存放 结构体的 map 的数据结构,
但不同于 stl,boost 中普通的map,它可以根据用户的需要来指定索引的类型,即 key 的值可以根据需要的不同而变化的。



比如说,现在我定义了一个 fruit 的结构体,其中包含属性 { fruit_name , fruit_color , fruit_shape }
然后使用 fruit 结构体分别存放三种水果,将其设定为 fruit_table

{apple    |  fruit_name = apple   ,   fruit_color = red    , fruit_shape = cycle  }
{banana |  fruit_name = banana ,  fruit_color = yellow , fruit_shape = line   }
{grape   |  fruit_name = grape   ,   fruit_colo r= purple , fruit_shape = cycle }

对于 multi_index 来说,仅仅为每个fruit /水果 实例提供一份存储空间,但是却可以分别将 fruit_name , fruit_color , fruit_shape 设定为该结构体的索引,
不同的索引对应的结构体中的 fruit 排序方式是不同的。

这里定义的多重索引的功能与含义完全可以等同于数据库中所创建的索引,那么通过访问 映射底层存储数据上的不同类型的索引
所直接获取的并不是存储底层数据实体,而是该存储实体的一个视图,相当于是获取到一个对象实体的指针一样。

不同的视图中元素属性排列的方式是不同的,
如果我们将 fruit_name 设为多重索引之一,那么我们通过 fruit_name 属性访问 fruit_table 将会得到一个按照 fruit_name 属性进行排列的 fruit_table 的视图 "view"
1.{apple| ...} , 2. {banana|...} , 3. {grape|...}
如果按照 fruit_color 我们将会获取到一个按照 fruit_color 进行排序的 fruit_table 的视图 "view"
1.{grape| fruit_color=purple} 2. {apple|fruit_color= red} 3.{banana | fruit_color = yellow }

fruit_shape 属性建立索引也是同理

索引的一点好处就是,可以根据需要来设定,在不修改底层存储列表顺序的基础上,可以将列表中的元素快速的按照属性进行顺序访问。
不然的话,就只能将底层存放的数据一一全部读取到内存中,再根据某一个属性进行升序、降序的排列。
因为将底层数据(存放到计算机硬盘上的文件)通过 I/O 读入到内存中,一是需要耗费大量的时间进行扫描硬盘,而是内存空间可能容纳不下
列表项中全部的信息条目的(实际工作中的信息条目可并不像是 fruit_node 中的属性那样少,有可能一个条目就对应上 GB 的视频文件)
这样读入本身就是问题,在跑个排序算法,后果就可想而知了。

这就是我们为何要使用索引的原因,为何要使用多重索引呢?
1.实际工作中需要频繁的针对数据列表中的多个属性进行排序,这样便有了针对该数据列表创建一个多重索引。
2.用于排序的索引属性并不全都主索引(也就是索引与数据记录/表项 之间是一一映射的关系)不能够确定数据列表的排序顺序,
   就像是 fruit 例子中的仅仅通过 fruit_shape 属性是无法将 grape 和 apple 进行排序的,因为没有其他的索引属性可供参考了。
   这种情况,就需要添加其他的索引{fruit_name ,fruit_color }用作参考,当然这种情况下是优先参考有着 unique 性质的索引
 


现在我们要通过创建一个文件列表的多重索引来介绍使用 boost::multi_index 的规则和如何调用自定义的多重索引来获取视图,通过视图来访问底层存储实体的各类属性

如果运行平台是 windows 直接运行源码即可,不过要根据需要修改一下对应读入的文件路径
如果运行平台是 linux ,
请结合后续的 configure.in 和 Makefile 以及 build.sh 文件来使用 autotools 流程来编译, 参考文档
linux平台上,要配合程序中的设定在 /tmp/路径下面创建名称为 rsa_key.pub,rsa_key{0|1|2|3|4}.txt 的文件,如果不想改源程序的话


点击(此处)折叠或打开

  1. #if !defined(NDEBUG)
  2. #define BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING
  3. #define BOOST_MULTI_INDEX_ENABLE_SAFE_MODE
  4. #endif

  5. #include <cstdio>

  6. #include <boost/multi_index_container.hpp>
  7. #include <boost/multi_index/member.hpp>
  8. #include <boost/multi_index/ordered_index.hpp>
  9. #include <boost/shared_ptr.hpp>

  10. #include <algorithm>
  11. #include <iostream>
  12. #include <iterator>
  13. #include <string>

  14. using boost::multi_index_container ;
  15. using namespace boost::multi_index ;

  16. struct file_node
  17. {
  18.     int id ;                             // ---- 这个是文件的 id 号码
  19.     std::string path_name ;              // ---- 这个是文件的 路径, 在设定索引的时候,我们将其设定为非重复的主索引项
  20.     long length ;                        // ---- 这个是文件的 长度, 在本实验中没有用到
  21.     std::string creator ;                // ---- 这个是文件的 作者, 在设定索引的时候,我们将其设定为可重复的辅助索引项
  22.     

  23.     file_node( int id , std::string path_name , std::string creator ):    // 这个是 文件-节点 结构体的构造函数
  24.         id(id) , path_name(path_name) , length(0), creator(creator)
  25.     {
  26.          
  27.             
  28.     }

  29.     friend std::ostream & operator<<(std::ostream &os , const file_node & f ) ;  // 这里重载了 operator<< 并将其设定为友元方法,
  30.                                                                                 //  为了方便将 file-node 中的属性信息转换为流
  31. } ;

  32. std::ostream &operator<< ( std::ostream &os , const file_node &f )            // 在这里根据文件路径打开文件,并读取文件的内容
  33. {                                                                             // 将文件中的内容进行格式化并转换为 流 对象,并返回
  34.      char file_buffer[1024] ;
  35.      std::string file_content ;
  36.      bool isOpen = false ;

  37.      FILE *fp = fopen(f.path_name.c_str() , "r") ;
  38.         if ( fp != NULL )
  39.              isOpen = true ;

  40.      if ( isOpen )
  41.      {
  42.      int ret = fread((void*)file_buffer , sizeof(char) , sizeof(file_buffer)-1 , fp );
  43.          file_buffer[ret] = '\0' ;
  44.         
  45.          file_content+= file_buffer ;

  46.          fclose (fp) ;
  47.      }


  48.      else
  49.      {
  50.          file_content = "failed open file "+ f.path_name ;
  51.      }
  52.     

  53.     os<<"[file path]     " << f.path_name << std::endl
  54.         << "[file index]     " << f.id << std::endl
  55.         <<"[file creator] " << f.creator << std::endl
  56.         <<"[file contents] " << file_content << std::endl << std::endl ; ;
  57.     return os ;
  58. }

  59. /**
  60.  here we tags for accessing the corresponding indices of file_node_table
  61.  要将 struct file-node 中的某个属性字段设定为 file-node 的索引项的话,需要定义与该
  62.  属性字段同名的空的结构体
  63. */

  64. struct path_name {} ;  
  65. struct creator {} ;

  66. /**
  67.   here we define a multi_index_container of file_node, with
  68.   following indices:
  69.   - a unique index sorted by file_node::path_name
  70.   - a non-unique index sorted by file_node::creator
  71. */

  72. typedef multi_index_container
  73. <
  74.   file_node , // table element , 要将什么作为创建表的元素,传入该结构体名称
  75.   indexed_by <

  76.          ordered_unique   // 唯一索引,主索引,与表项一一映射, tag<传入刚刚定义好的 struct path_name {} 对应的名称 >
  77.          <                // BOOST_MULTI_INDEX_MEMBER( 创建表中的元素结构体名称, 索引的类型, 索引的名称 等于 tag<> 中设定的名称 )
  78.             tag<path_name> , BOOST_MULTI_INDEX_MEMBER(file_node, std::string , path_name)
  79.          > , // this is for file's path_name , like primary-key in database table
  80.         
  81.          ordered_non_unique
  82.          <
  83.             tag<creator> , BOOST_MULTI_INDEX_MEMBER(file_node, std::string , creator)
  84.          > // second index file node's creator
  85.   > // end indexed by
  86. > file_node_table ;

  87. typedef boost::shared_ptr<file_node_table> ftPtr ; // 在这里我们使用 typedef 定义一个用来封装刚刚定义好的多重索引类型的 智能指针 类型


  88. int main ()
  89. {
  90.     // try create obj by shared_ptr
  91.     ftPtr file_table_ptr( new file_node_table ) ;  // shared_ptr 智能指针固有的创建对象的方法

  92.     std::string file_path , author ;
  93.     file_path = "/tmp/rsa_key" ;
  94.     author = "kokia" ;

  95.     // add additional node with creator/author name as 'Aimer'

  96.     file_table_ptr->insert( file_node (1200 , "/tmp/rsa_key.pub" , "Aimer")) ; // 插入 file-node 文件-节点 作为表项

  97.     for ( int i = 0 ; i < 5 ; i++ )
  98.     {
  99.         char no = i+'0' ;    
  100.         file_table_ptr->insert(file_node(i , file_path+no+".txt" , author)) ;
  101.     }

  102.     std::cout << "+++++++++++++++++++++ print files by author ++++++++++++++++++++ "<< std::endl ;
  103.    
  104.     file_node_table::index<creator>::type & index_by_author = file_table_ptr->get<creator>() ; 
  105.     /*
  106.       恭喜你,获得指向以 creator 属性排序的 文件表视图 , 该视图,通过 index_by_author 变量关联
  107.       创建一个视图的迭代器,有了它便可以顺序遍历视图中 以 creator 属性进行排序的各个表项了,
  108.       并访问表项中,也就是每个 file-node 中的各个属性
  109.  
  110.     */                                                                                                        

  111.     file_node_table::index<creator>::type::iterator creator_it = index_by_author.begin() ;    
  112.                                                                                                
  113.     while ( creator_it != index_by_author.end())                                               
  114.     {
  115.         std::cout << *creator_it << std::endl ;
  116.         creator_it++ ;
  117.     }
  118.  

  119.     std::cout << "+++++++++++ print files by path name +++++++++++++++++++++" << std::endl ;
  120. // 这里和上面的原理是一样的,首先是获得 file-table 的按照 path_name 属性进行排序的视图 (注意视图与表的区别,视图仅仅是表的一个映像
  121. // 在系统中并不为视图中的元素提供实际的存储空间,类似于对象实体和指向对象的指针) ,通过该视图创建遍历视图的迭代器,通过迭代器
  122. // 逐个访问以 path_name 属性排序的视图中的各个 file-node 元素,并可以访问各个 file-node 中的属性值
  123.  
  124.     file_node_table::index<path_name>::type & file_table_view_index_by_path_name =
  125.             file_table_ptr->get<path_name>() ;

  126.     // path_it points to the first element in the VIEW which sorted by path_name
  127.     file_node_table::index<path_name>::type::iterator
  128.              path_it = file_table_view_index_by_path_name.begin () ;

  129.     for ( ; path_it != file_table_view_index_by_path_name.end() ; path_it++ )
  130.     {
  131.         // call operator<< method of each object which pointed by iterator of path name
  132.         std::cout << *path_it << std::endl ;
  133.     }

  134.     std::cout << "----------------------- test find method --------------------------------------" << std::endl ;
  135.     //  在下面的演示中,我们首先通过 file_table_ptr->get 获得一个以 creator 属性排序的 file-node-table 的视图
  136.     // 然后创建该 creator-视图调用 find 方法来查找 file-node.creator = "Aimer" 的 file-node
  137.     // 如果找到的话, 迭代器是不会指向 creator-视图 的结尾空元素项的,通过该点即可判断, 因为 itr 类型特殊,不可使用 itr == NULL 判断
  138.     // 
  139.     //在成功找到之后,将找到的对象通过特定类型(creator) 的迭代器指向,然后通过该迭代器即可访问 file-node 中的元素值了

  140.     file_node_table::index<creator>::type::iterator
  141.                  itr(file_table_ptr->get<creator>().find("Aimer")) ;

  142.     if ( itr != file_table_ptr->get<creator>().end() )
  143.     {
  144.         std::cout<< " find file node " << std::endl ;
  145.         std::cout << *itr << std::endl ;
  146.     }

  147.     else
  148.     {
  149.         std::cout << " file node not find" << std::endl ;
  150.     }

  151.     return 0 ;
  152. }

//================== compile scripts for linux =============================
// build.sh , do not forget chmod 755

点击(此处)折叠或打开

  1. #!/bin/sh

  2. autoscan
  3. aclocal
  4. autoconf
  5. autoheader
  6. automake --add-missing
  7. ./configure CXXFLAGS= CFLAGS=
  8. make

// configure.in

点击(此处)折叠或打开

  1. # -*- Autoconf -*-
  2. # Process this file with autoconf to produce a configure script.

  3. AC_INIT(multi_index_demo)

  4. AC_USE_SYSTEM_EXTENSIONS

  5. AM_INIT_AUTOMAKE( multi_index_demo, 1.0 )

  6. AC_CONFIG_SRCDIR([multi_index_demo.cpp])
  7. AC_CONFIG_HEADERS([config.h])

  8. # Checks for programs.
  9. AC_PROG_CXX
  10. AC_PROG_CC

  11. # Checks for libraries.

  12. # Checks for header files.

  13. # Checks for typedefs, structures, and compiler characteristics.
  14. AC_HEADER_STDBOOL

  15. # Checks for library functions.

  16. AC_OUTPUT(Makefile)
// Makefile.am

点击(此处)折叠或打开

  1. AUTOMAKE_OPTIONS=foreign
  2. bin_PROGRAMS=multi_index_demo
  3. BOOST_LIB_PATH=/unixC/Boost/boost_1_58_0

  4. #what source files multi_index_demo need ?

  5. multi_index_demo_SOURCES=\
  6. multi_index_demo.cpp

  7. multi_index_demo_CXXFLAGS=\
  8. -I$(BOOST_LIB_PATH) -D_FILE_OFFSET_BITS=64 \
  9. -ggdb -Wall -O0

  10. multi_index_demo_LDADD=\
  11. -lpthread -lm -lboost_system -lboost_thread \
  12. -lboost_program_options -lrt

  13. multi_index_demo_LDFLAGS=\
  14. -fPIC -rdynamic -L$(BOOST_LIB_PATH)/stage/lib -pthre
运行结果


没错,我读入的文件是前几篇文章中的程序生成的 rsa_key.pub,并不是实际使用中的 rsa-public-key ,在这里读入的文件可以根据用户喜好而定

end
阅读(6190) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~