* added memory relocatability test
* added missing #includes
* avoided C++14 std::make_unique
* added hashed index local iterators to the test
* made all iterators store allocator-provided pointers to the nodes
* updated docs
* added gcc-15, gcc-16
* explicitly constructed bfm_header everywhere
* reverted, silenced uninitialized warning
* moved silencing pragma inside header body
* made silencing pragma enclose entire multi_index_container definition
* abandoned pragma, deinlined header()
* tried an even more convoluted workaround
* type-erased member in header_holder
* s/static_cast/reinterpret_cast
* reverted, passed allocator and header explicitly in construction
* used passed header in construction rather than header()
* investigated if hit by https://gcc.gnu.org/bugzilla/show_bug.cgi?id=119321
* documented GCC 16.1 flag
* avoided VS warning
* omitted test_mpl_ops for now
* made IndexSpecifierList a Mp11 sequence
* made nested *_type_list's and tag Mp11 sequences
* leftover MPL->Mp11 change
* removed Clang 5.0 -std=c++1z as not supported by Mp11
* replaced boost::mpl::na with void as default index specifier arg
* removed Clang 5.0 -std=c++1z as not supported by Mp11 (Drone)
* replaced elementary MPL TMP with Mp11/std
* replaced elementary MPL TMP with Mp11/std (tests)
* leftover MPL #include
* suppressed potential narrowing conversion warnings
* enabled macro to support old interface, plus restored and augmented test_mpl_ops
* removed secondary dependency to MPL thru Iterator
* optimized Jamfile.v2
* added conditional support for old definition of tag
* updated MPL support macro in tests
* updated docs
* stylistic
* updated "cxxstd" in libraries.json
* disabled test_serialization for Clang 3.5-3.6 due to lack of support from Boost.SmartPtr
* fixed previous
* removed no longer necessary workaround
* removed redundant dependencies
* updated test description
* refactor: use type_traits/declval over utility/declval
The later is just an include for the former.
* refactor: use container_hash/hash* over functional/hash*
The later just include the former.
The later is deprecated:
```cpp
// The header file at this path is deprecated;
// use boost/core/enable_if.hpp instead.
include <boost/core/enable_if.hpp>
```
* 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
joaquintides