boost深入之使用技巧第四讲

1、boost深入剖析之使用技巧第四讲：boost容器库主讲人：步磊峰 UIPower 3D界面引擎负责人第一节： 全能容器multi_index2功能最强大，灵活性最高，复杂度最大的容器 stl的容器map,hashmap,list,vector，boost:bimap都是multi_index的特殊形式 无数的组合，没有做不到，只有你想不到 对关系型数据库进行内存建模，具有主键，联合主键，外键，视图，索引等数据库核心概念，你可以将其看成一个 内存表示的具有基本功能的mysql数据库 存储与操作相分离，使用multi_index_container作为数据存储容器，使用任何一个index对 mu

2、til_index_container容器进行modify操作，其他关联index 会进行同步更新 多种类型的index，可以将每一个index（或视图)看成某一种stl容器 第二节： mutli_index概念图3第三节： mutli_index头文件41、 头文件 2、 namespace using namespace boost; using namespace boost:multi_index; 第四节： mutli_index类型5 index(也可以称为视图) 第五节： 关联性索引6ordered_unqiue 和 ordered_non_unqiue index templa

3、te typename KeyFromValue, typename Compare=std:lessstruct (ordered_unique | ordered_non_unique);template typename TagList, typename KeyFromValue, typename Compare=std:lessstruct (ordered_unique | ordered_non_unique); 第五节： 关联性索引7 hashed_unqiue 和hashed_non_unqiue indextemplate typename KeyFromValue, t

4、ypename Hash=boost:hash, typename Pred=std:equal_tostruct (hashed_unique | hashed_non_unique);template typename TagList, typename KeyFromValue, typename Hash=boost:hash, typename Pred=std:equal_tostruct (hashed_unique | hashed_non_unique); 第五节： 关联性索引8 hashed原理图 /number of bucket1） size_type bucket_c

5、ount() const; /An upper bound on the number of buckets2） size_type max_bucket_count() const; /The number of elements in bucket n3） size_type bucket_size(size_type n) const; /Returns the index of the bucket /which would contain k4） size_type buket(key_type const& k) const /Return begin and end it

6、erators for bucket n.5） const_local_iterator begin(size_type n) const; const_local_iterator end(size_type n) const; 第六节： 线性索引9 non-key-based index /相当于stl:list表示 templatetypename TagList=tag struct sequenced; /相当于stl:vector表示 templatetypename TagList=tag struct random_access; 第七节： index各种操作及比较10 1、

7、index iterator 操作 第七节： index各种操作及比较112、 index capacity操作 第七节： index各种操作及比较123、 index access操作 第七节： index各种操作及比较134 、 index modify 操作 (a : 添加/删除操作) 第七节： index各种操作及比较144、 index modify 操作 (a : 添加/删除操作) insert成员函数 std:pair insert(const value_type& x); /sequenced和random_access不具有该函数 iterator insert(i

8、terator position,const value_type& x); Desc: The return value is a pair p. p.second is true if and only if insertion took place. On successful insertion, p.first points to the element inserted; otherwise, p.first points to an element that caused the insertion to be banned. Note that more than on

9、e element can be causing insertion not to be allowed. template void insert(InputIterator first,InputIterator last); Desc: while(first!=last)insert(position,*first+); 第七节： index各种操作及比较154、 index modify 操作 (a : 添加/删除操作) erase成员函数 iterator erase(iterator position); Desc: Deletes the element pointed to

10、by position. Return An iterator pointing to the element immediately following the one that was deleted, or end() if no such element exists. iterator erase(iterator first,iterator last); Desc: Deletes the elements in first,last). Return last iterator size_type erase(const key_type& x); /ordered和h

11、ashed才具有的 Desc: Deletes the elements with key equivalent to x. Return number of elements deleted第七节： index各种操作及比较164、 index modify 操作 (b : 替换/修改/交换) 第七节： index各种操作及比较174、 index modify 操作 (b : 替换/修改/交换) replace成员函数 bool replace(iterator position,const value_type& x); modify成员函数 template bool modi

12、fy(iterator position,Modifier mod); template bool modify(iterator position,Modifier mod,Rollback back); 区别: replace在成功时才会修改multi_index_container中的元素以及相关其他index的索引 modify不成功话会删除掉multi_index_container中的元素或相关其他index的索引. 即使modify提供回滚的仿函数，可禁止修改失败后针对修改容器操作第七节： index各种操作及比较184、 index modify 操作 (b : 替换/修改/交

13、换) ordered和hashed才拥有的成员函数 template bool modify_key(iterator position,Modifier mod); template bool modify_key(iterator position,Modifier mod,Rollback back); swap成员函数 void swap(index class name& x); 第七节： index各种操作及比较195、 index lookup操作 第七节： index各种操作及比较205、 index lookup操作 根据key查找value(ordered 和 ha

14、shed才具有) template iterator find(const CompatibleKey& x)const; template iterator find(const CompatibleKey& x,const CompatibleCompare& comp)const; Return: a pointer to an element whose key is equivalent to x, or end() if such an element does not exist Complexity : ordered O(log(n) hashed A

15、verage case O(1) (constant), worst case O(n). 第七节： index各种操作及比较215、 index lookup操作 根据key查找对应value的数量(ordered 和 hashed才具有) template size_type count(const CompatibleKey& x)const; template size_type count(const CompatibleKey& x,const CompatibleCompare& comp)const; Return: the number of elem

16、ents with key equivalent to x Complexity : ordered O(log(n) + count(x,comp). hashed Average case O(count(x,hash,eq), worst case O(n).第七节： index各种操作及比较225、 index lookup操作 根据key查找所有value(ordered 和 hashed才具有，主要用于non_unique关联容器) template std:pair equal_range(const CompatibleKey& x)const; template st

17、d:pair equal_range(const CompatibleKey& x,const CompatibleCompare& comp)const; Return: ordered Equivalent to make_pair(lower_bound(x,comp),upper_bound(x,comp). hashed a range containing all elements with keys equivalent to x (and only those), or (end(),end() if no such elements exist. Comple

18、xity : ordered O(log(n) hashed Average case O(1) (constant), worst case O(n). 返回的是std:pair pair.first 起始迭代器 while(pair.first != pair.second) pair.second 结束迭代器 + pair.first； 第七节： index各种操作及比较235、 index lookup操作 ordered 才具有，主要用于non_unique关联容器三个成员函数 （1） lower_bound template iterator lower_bound(const C

19、ompatibleKey& x)const; template iterator lower_bound(const CompatibleKey& x,const CompatibleCompare& comp)const; Return: an iterator pointing to the first element with key not less than x, or end() if such an element does not exist. Complexity : ordered O(log(n) 第七节： index各种操作及比较245、 ind

20、ex lookup操作 ordered 才具有，主要用于non_unique关联容器三个成员函数 （2） upper_bound template iterator upper_bound(const CompatibleKey& x)const; template iterator upper_bound(const CompatibleKey& x,const CompatibleCompare& comp)const; Return: an iterator pointing to the first element with key greater than x

21、, or end() if such an element does not exist. Complexity : ordered O(log(n) 第七节： index各种操作及比较255、 index lookup操作 ordered 才具有，主要用于non_unique关联容器三个成员函数 （3） range template std:pair range(LowerBounder lower,UpperBounder upper)const; Return: a pair of iterators pointing to the beginning and one past the

22、end of the subsequence of elements satisfying lower and upper simultaneously. If no such elements exist, the iterators both point to the first element satisfying lower, or else are equal to end() if this latter element does not exist Complexity : ordered O(log(n)第 八节： 预定义key Extractors26 预定义 Key Ext

23、ractors 仿函数 /整个base type作为键 identity /一个类的某个成员变量作为键 member /一个类的某个const成员函数的返回值作为键 const_mem_fun /一个类的某个成员函数的返回值作为键 mem_fun /一个全局或静态函数的返回值作为键 global_fun Key Extractors - composite_key 第 九节： multi_index_container类271、类模板 template class multi_index_container; 2、get成员函数(通过idx或tag返回一个索引（视图)引用 template struct nth_index; template stru