3
\$\begingroup\$

I recently had the problem that I wanted a hashmap where there would be a variable amount of distinct classes which each could be used to look up each other. I couldn't find any implementation online so I wrote it myself:

// Compile with c++20 because this code uses concepts
#include <concepts>
#include <vector>
#include <utility>
#include <iostream>
#include <sstream>
#include <string>
#include <cstdio>
#include <tuple>

template <typename T> concept Streamable = requires(std::ostream &os, T value) {
    { os << value } -> std::convertible_to<std::ostream &>;
};

template<typename T> concept nMapValidType = std::default_initializable<T> && std::equality_comparable<T> && Streamable<T>;

template<nMapValidType ...T>
class nMap {
    public:
    nMap(std::initializer_list<std::tuple<T...>> iList) : 
        vec(iList) {}

    ~nMap() = default;

    void add(std::tuple<T...> tuple) {
        this->vec.push_back(tuple);
    }

    nMap<T...>& operator=(std::initializer_list<std::tuple<T...>> iList) {
        this->vec = iList;
        return *this;
    }

    template<nMapValidType Gettee, nMapValidType Getter>
    Gettee get(Getter getVal, bool throwError = true) const {
        if constexpr (!std::disjunction_v<std::is_same<Gettee, T>...>) {
            std::perror("Return type for nMap::get not found.");
        } else {}
        if constexpr (!std::disjunction_v<std::is_same<Getter, T>...>) {
            std::perror("Getter type for nMap::get not found.");
        } else {}

        for (const auto& tuple: this->vec) {
            if (std::get<Getter>(tuple) == getVal) {
                return std::get<Gettee>(tuple);
            }
        }

        if (throwError) {
            std::stringstream sstr;
            sstr << "No keys to value `" << getVal << "` found.";
            std::perror(sstr.str().c_str());
        }
        return {};
    }

    template<nMapValidType Type>
    bool contains(Type item) const {
        if constexpr (!std::disjunction_v<std::is_same<Type, T>...>) {
            std::perror("Type passed to nMap::contains not found.");
        } else {}
        for (const auto &tuple: this->vec) {
            if (std::get<Type>(tuple) == item) {
                return true;
            }
        }
        return false;
    }

    private:
    std::vector<std::tuple<T...>> vec;
};

template<nMapValidType A, nMapValidType B, nMapValidType C>
using triMap = nMap<A, B, C>;

template<nMapValidType A, nMapValidType B>
using biMap = nMap<A, B>;


int main() {
    const nMap<int, char, bool> boolMap = {
        { 0, 'f', false},
        { 1, 't', true}
    };
    bool testBool = boolMap.get<bool>('f');
    int testInt = boolMap.get<int, bool>(true);
    return testInt;
}

While functioning quite well, I feel that the lookup for both get and contains could be improved.

Another feature that this implementation is missing, is both the get and contains function. I haven't had a use for non-const nMap's yet, so this is not a dealbreaker but I just don't want to copy-paste those huge chunks of code.

Something that I feel is impossible is the separation of declaration and definition of these functions, as they are included in many files in a larger project I'm working on and compile-times have proven to be quite slow (I don't know if it is because of this class, this just may be a factor).

\$\endgroup\$

1 Answer 1

Reset to default
4
\$\begingroup\$

Don't call this a map

Your nMap is just presenting a convenient API for a std::vector<std::tuple<...>>, however it has almost none of the properties of an STL map. Someone familiar with the STL but now with the implementation details of your class will be confused, and think for example that objects stored in the map can be retrieved in \$O(\log N)\$ time and have stable pointers, when that is not the case.

Try to match the API of STL containers as much as possible

A container becomes much more useful if its API closely matches that of other STL containers. For one, it makes it much easier for programmers: they don't have to remember two different APIs. The other reason is that generic algorithms will be able to work with your container if it has the expected API.

For get(), that might be problematic, as it's a combination of std::tuple's get() and the std::find() algorithm. But add() could be renamed to push_back() at least.

There is also a lot missing that would be useful, like iterators, operator[], clear(), resize() and so on.

What if you have identical types?

What if you want to have a nMap<int, int, int>? You can create one and add elements, but you can't use get() or contains() with it.

Think about references and non-const access

Your get() makes a copy of a value stored in the map. For large types, this can be inefficient. Consider returning a (const) reference to the gettee.

Also think about how you pass parameters: getVal should be a const reference, add() should also take a const reference, and/or an rvalue reference.

throw instead of using perror()

perror() is a C function. In C++, prefer to throw errors: this allows the caller to catch them and do something about it, if so desired.

Also, for compile-time errors, use static_assert(): this will cause the compilation to abort, so the programmer can find problems early. Compiling in a call to perror() might delay discovery of a programming error until the program is run.

Also, don't try to print the value you cannot find if this restricts the types your class can support.

\$\endgroup\$
6
  • \$\begingroup\$ Thank you for the insight! The main gripe with it is the section about errors. There is nothing unexpected about the errors, I find it to be better to actually check if the nMap actually contains the element and only then get it, but that is just my personal opinion. And also I did use static_assert, just not in one place where it was "impossible" because checking if the nMap contains an element can only be done at run-time. \$\endgroup\$ Commented Oct 20, 2022 at 18:50
  • \$\begingroup\$ I don't see any static_assert() in your code. Of course, if it's only something that can be done at runtime, then indeed you cannot use it. Have a look at how the STL handles this in std::map::at(). \$\endgroup\$ Commented Oct 20, 2022 at 19:52
  • \$\begingroup\$ I changed the code in my editor and then forgot to paste the changes over. My mistake. Every error in the original question except for the one in get now uses static_assert. You also mentioned the Big-O of the lookup, which I believe to currently be \$O(N)\$. Do you think this could be improved? \$\endgroup\$ Commented Oct 20, 2022 at 20:01
  • \$\begingroup\$ Sure, you can use multiple std::maps or std::unordered_maps instead of single std::vector to allow for fast lookups. This will complicate the code and increase memory usage of course, but that might be a perfectly fine trade-off if you expect to do a lot of lookups. \$\endgroup\$ Commented Oct 20, 2022 at 20:06
  • \$\begingroup\$ How would that work with the typepack though? \$\endgroup\$ Commented Oct 20, 2022 at 20:07

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.