[feature request] composite key partial matching for ordered index

[redboltz]

Thank you for developing the great library. rust version of Boost.MultiIndex like container is what I want to have.

Perhaps it has already planned in your roadmap, but I'd like to have the follwoing feature.

Boost.MultiIndex for C++ supports composite key partial matching for ordered index. If this library has similar functionality, it's very useful.

elem_t

elem_t has name, time_stamp, and rank. Let's say inseting the following elements.

NOTE: It doesn't mean internal structure.

name	time_stamp	rank
bbb	10	3000
bbb	30	2000
bbb	20	1000
aaa	10	3000

Let's say there are two composite indexes. The first index (tag_name_ts) contein name and time_stamp in this order. The second index (tag_name_rank) contains name and rank in this order.

When I get elements by the first index (tag_name_ts), and passes only name "bbb" the left most element, then return the list of elem_t their name is "bbb" and their time_stamp is ordered by time_stamp.

name	time_stamp	rank
bbb	10	3000
bbb	20	1000
bbb	30	2000

When I get elements by the second index (tag_name_rank), and passes only name "bbb" the left most element, then return the list of elem_t their name is "bbb" and their time_stamp is ordered by rank.

name	time_stamp	rank
bbb	20	1000
bbb	30	2000
bbb	10	3000

It is similar behavir as RDB index.

Example

Here is a code example that demonstrates my feature request:

godbolt running demo

https://godbolt.org/z/9x8MKh6vW

C++ code (Boost.MultiIndex)

#include <iostream>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/key.hpp>

namespace mi = boost::multi_index;

struct elem_t {
    elem_t(
        std::string name,
        int time_stamp,
        int rank
    ): name{std::move(name)}, time_stamp{time_stamp}, rank{rank}
    {}

    std::string name;
    int time_stamp;
    int rank;
};

inline std::ostream& operator<<(std::ostream& o, elem_t const& v) {
    o << "name:" << v.name << " ts:" << v.time_stamp << " rank:" << v.rank;
    return o;
}

struct tag_name_ts{};
struct tag_name_rank{};

using elems_t = mi::multi_index_container<
    elem_t,
    mi::indexed_by<
        mi::ordered_non_unique<
            mi::tag<tag_name_ts>,
            //       first key,     second key
            mi::key<&elem_t::name, &elem_t::time_stamp>
        >,
        mi::ordered_non_unique<
            mi::tag<tag_name_rank>,
            //       first key,     second key
            mi::key<&elem_t::name, &elem_t::rank>
        >
    >
>;

int main() {
    elems_t es;
    es.emplace("bbb", 10, 3000);
    es.emplace("bbb", 30, 2000);
    es.emplace("bbb", 20, 1000);
    es.emplace("aaa", 10, 3000);

    {
        std::cout << "Use tag_name_ts and give only name" << std::endl;
        auto [b, e] = 
            es.get<tag_name_ts>().equal_range("bbb"); // give only first key
        // result is sorted by the second key 'time_stamp'
        for (;b != e; ++b ) std::cout << *b << std::endl;
    }
    {
        std::cout << "Use tag_name_rank and give only name" << std::endl;
        auto [b, e] = 
            es.get<tag_name_rank>().equal_range("bbb"); // give only first key
        // result is sorted by the second key 'rank'
        for (;b != e; ++b ) std::cout << *b << std::endl;
    }
}

Output

Use tag_name_ts and give only name
name:bbb ts:10 rank:3000
name:bbb ts:20 rank:1000
name:bbb ts:30 rank:2000
Use tag_name_rank and give only name
name:bbb ts:20 rank:1000
name:bbb ts:30 rank:2000
name:bbb ts:10 rank:3000

[huang12zheng]

I think this can be done with the function+macro_attr. The function name corresponds to the field_name, and the return value corresponds to the type.

[redboltz]

@huang12zheng, thank you for the comment. Do you mean it can be done on the current library code https://github.com/lun3x/multi_index_map/commit/a086ff85690d1e69bfc83bb96909f9e3ef3c03d2 ? Coud you post some example code, if you have a time? Anyway, I will investigate a way using function+macro_attr.

[huang12zheng]

@redboltz

• Not in the current repo. example for: https://github.com/huang12zheng/multi_index_map/blob/324baa1047dcbe065aa84728d9e319317e684075/tests/extra_field.rs

Feedback and revisions are welcome. But I'm actually looking forward to seeing if the repo author agrees with this solution.