Search code examples
c++boostboost-multi-index

boost::multi_index insertion function for "other" indices


Here is a container of ints with a hashed index and a sequence index:

#include <iostream>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/sequenced_index.hpp>

int main()
{
    boost::multi_index_container<
    int,
    boost::multi_index::indexed_by<
        boost::multi_index::hashed_unique<boost::multi_index::identity<int>>,
        boost::multi_index::sequenced<>
        >
    > c;
    for (int i=99; i>=0; --i) c.get<0>().insert(i);
    for (int j : c.get<0>()) std::cout << " " << j;
    std::cout << std::endl;
    for (int k : c.get<1>()) std::cout << " " << k;
    std::cout << std::endl;
    return 0;
}

When I run this I get:

 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 2 1 0   
 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

The first line shows the elements are "scattered" via the hash index, as expected. The second line shows the elements are in insertion order via the sequenced index. But the elements were inserted via the hash index; what can we expect for the elements of the sequenced index? That is, when insert is called for one index, are the insertion functions used for "other" indices defined?

Specifically: When a multi-index container has a hashed index and a sequenced index, and elements are only inserted via the hashed index, will the elements always be in insertion order via the ordered index?


Solution

  • As for sequenced indices, docs say:

    Elements in a sequenced index are by default sorted according to their order of insertion: this means that new elements inserted through a different index of the multi_index_container are appended to the end of the sequenced index.