Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Frozen bimap? #145

Open
RazielXYZ opened this issue Nov 21, 2022 · 2 comments
Open

Frozen bimap? #145

RazielXYZ opened this issue Nov 21, 2022 · 2 comments

Comments

@RazielXYZ
Copy link

RazielXYZ commented Nov 21, 2022

In a lot of use cases for frozen, such as enum-to-string mappings, it feels like it would be very useful to have the option for looking up values from either side.
Obviously, one could do this by manually making another map with the keys and values swapped, or, even use a macro or code generator to do so, but those solutions tend to be either annoying to implement and use, or relatively fickle.

That in mind, I've implemented a quick and "simple" bimap on top of frozen::unordered_map, which can handle constexpr elements, and looks something like this:

template <typename T1, typename T2>
struct swappedPair {
    constexpr std::pair<T2, T1> operator()(const std::pair<T1, T2>& inPair) {
        return {inPair.second, inPair.first};
    }
};

template <typename K, typename V, std::size_t N>
struct FrozenBimap {
    const frozen::unordered_map<K, V, N> left;
    const frozen::unordered_map<V, K, N> right;

    constexpr std::array<std::pair<V, K>, N> makeR(std::pair<K, V> const (&items)[N]) {
        return [] <std::size_t... I>(std::pair<K, V> const (&s)[N], std::index_sequence<I...>) -> std::array<std::pair<V, K>, N> {
            return {swappedPair<K, V>{}(s[I]) ...};
        }(std::forward<std::pair<K, V> const[N]>(items), std::make_index_sequence<N>{});
    }

    constexpr FrozenBimap() = delete;

    constexpr FrozenBimap(std::pair<K, V> const (&items)[N]) :
        left(frozen::unordered_map<K, V, N>{items}),
        right(makeR(items)) {
    }

    constexpr FrozenBimap(std::array<std::pair<K, V>, N> const& items) :
        left(frozen::unordered_map<K, V, N>{items}),
        right(makeR(items)) {
    }
};

Would something like this be useful as a part of frozen proper? I could try to further refine it then do a PR. Note that this version only works with C++20, but I'm pretty sure C++14 would be doable, although not quite as clean on the makeR method's implementation.
Also, obviously because the values are keys for the second map, this would likely be limited to both keys and values being immutable.

@muggenhor
Copy link
Contributor

muggenhor commented Jul 27, 2023

I have the same use case but storing quite large objects. So for me it would be preferable to only duplicate the indices (hash table) instead of the data.

I actually have a even more complicated use case: I have 3 members that are all unique and I need the ability to perform lookups for each of them (ISO-3166 country codes, numeric ones, 2 letter ones and 3 letter ones). So instead of a special case for 1 lookup key and another for 2 maybe it's desirable to allow for N indices (with N >= 1 && N <= sizeof...(Elements))?

At that point this would start looking a lot like a constexpr version of a basic SQL table with a bunch of UNIQUE clauses on columns to get an index for each of those columns.

@ddevienne
Copy link

A SQL table or Boost.Multi-Index, BMIs as I call them.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants