* count for ranked_index uses rank
Normally, count is calculated as the distance between iterators,
which takes linear time when count(x,comp) is comparable with n,
but for ranked indices we can subtract the values or rank,
reducing the complexity from log(n)+count(x,comp) to log(n).
* Added test for new count(x) and count(x,comp) in ranked_index
Both, the existing implementation of count from ordered_index and
the new implementation for ranked_index are compared with the
common sense. Positive results of this test show in particular that
the numbers produced by the new implementation are consistent with
those from the existing implementation and hence correct.
* Benchmark of count(): ordered_index vs ranked_index
A benchmark is added as count_benchmark.cpp in the 'example'
directory.
When the values of an index are unique, both implementations are
comparable (ranked_index is 10-15% faster).
However, for highly non-unique indices (like the age of people),
the new implementation in ranked_index outperforms ordered_index.
For 1 000 people of age in 0..99 ranked_index is ~2x faster,
for 10 000 people it is 12-13x faster, and
for 100 000 people it is 95-100x times faster.
For even more non-unique indices (like sex or the age of pupils)
or coarse comparison predicates (grouping people in age groups
like 0..9, 10..19 etc.) the gap in performance grows further.
For a comparison predicate comparing 'age/10' for age in 0..99,
similar gaps in performance occur already for 10x smaller
containers:
for 100 people count in ranked_index is 2x faster,
for 1 000 people it is ~9x faster,
for 10 000 people it is 95-100x faster,
for 100 000 people it is almost 1000x faster.
* Documentation updated with new complexity of count in ranked_index
* simplified Damian's contribution
* reorganized code
* covered ranked_index::count
* updated docs
Co-authored-by: DamianSawicki <86234282+DamianSawicki@users.noreply.github.com>
* initial draft
* modified appveyor.yml for this branch
* dropped BOOST_RV_REF
as it doesn't handle lvalue refs
* befriended index_base from all indices
so as to be grant access to final_extract_for_merge_ from an external container
* added rvalue ref merge
(test expected to fail in C++03)
* added explicit boost::move on rvalue ref
for the benefit of C++03 compilers
* fixed previous workaround
* refactored merge algorithm into multi_index_container
* added hashed_index::merge
* reimplemented sequenced_index::splice(position,x)
* added missing this->'s
* refactored SFINAEing code
* made sequenced_index::splice(position,x) exception robust
* reimplemented random_access_index::splice(position,x)
* micro-optimized legacy code in random_access_index::splice(position,x)
* added missing #include
* reimplemented sequenced_index::splice(position,x,i)
* reimplemented random_access_index::splice(position,x,i)
* reimplemented sequenced_index::splice(position,x,first,last)
* reimplemented random_access_index::splice(position,x,first,last)
* re-engineered sequenced_index::splice(position,x,i)
so that it works when source and destination belong to the same container
* stylistic
* re-engineered random_access_index::splice(position,x,i)
so that it works when source and destination belong to the same container
* re-engineered sequenced_index::splice(position,x,first,last)
so that it works when source and destination belong to the same container
* stylistic
* fixed bug in rvalue ref overload of sequenced_index::splice(position,x,first,last)
* fixed internal sequenced_index::splice(position,x,first,last) across different indices
* re-engineered random_access_index::splice(position,x,first,last)
the same way as done with sequenced_index
* replaced multi_index_container::merge_ with transfer_range_
so as to refactor some code in non-key-based indices
* fixed safe mode check for different-type containers
* hardened merge/splice tests
* s/BOOST_RV_REF/BOOST_FWD_REF
* called the right merge_different overload
* fixed problem with Boost.Move C++03 perfect fwd emulation
* updated (C) year
* allowed intra-container full splice
* required position==end() in intra-container full splice
* made pointwise splice return a pair<iterator,bool>
* added partial merge functionality to key-based indices
plus fixed a compile-time error with legacy splice code when applied to different-type indices
* suppressed unused variable
* fixed wrong signature in splice memfun
* made safe-mode iterators SCARY
* refactored any_container_view
* implemented safe iterator transfer in merge/splice
* reorganized internal deps
* stylistic
* automatically checked iterator invalidation upon merge/splice
* removed commented-out code
* checked allocator equality
* reimplemented random_access_index internal, cross-index splice in linear time
* updated docs
* reverted appveyor.yml
