还在苦苦敲代码开发APP?你out啦! 试试积木搭建APP吧~

c++ boost::multi_index composite keys efficiency

来源:清泛原创     2016-06-07 10:52:04    人气:     我有话说( 0 人参与)

Long time reader first time poster! I'm playing around with the boost::multi_index container stuff and have a...

Long time reader first time poster! I'm playing around with the boost::multi_index container stuff and have a rather in-depth question that hopefully a boost or C++ container expert might know (my knowledge in C++ containers is pretty basic). For reference, the boost documentation on composite keys can be found here: boost::multi_index composite keys.

When using a composite key, the documentation states that "Composite keys are sorted by lexicographical order, i.e. sorting is performed by the first key, then the second key if the first one is equal, etc". Does this mean that the structure is stored such that a lookup for a specific 2-part composite key will take O(n=1) time, i.e. is the container sorted such that there is a pointer directly to each item, or does the boost container retrieve a list that matches the first part of the composite key and then need to perform a search for items matching the second part of the key and thus is slower?

For example, if I was to maintain two containers manually using two different indices and wanted to find items that matched a specific 2-part query I would probably filter the first container for all items matching the 1st part of the query, and then filter the result for items that match the 2nd part of the query. So this manual method would effectively involve two searches. Does boost effectively do this or does it improve on efficiency somehow via the use of composite keys?

Hopefully I've explained myself here but please ask questions and I will try my best to clarify exactly what I mean!


From:http://stackoverflow.com/questio ... ite-keys-efficiency

c++ boost multi_index

注:本文为本站或本站会员原创优质内容,版权属于原作者及清泛网所有,
欢迎转载,转载时须注明版权并添加来源链接,谢谢合作! (编辑:admin)
分享到: