How to Use Std::Maps With User-Defined Types as Key

Using a user-defined type as map value in c++

Is it possible to instantiate an object like this

Yes, it is.

or do i have to use the new operator in some way?

No, you don't.

How can i make this work?

That already works, assuming you define the variables and types that were missing from the example:

#include <map>
#include <utility>
using std::map;
using std::make_pair;

struct Type {
    Type(int,int,int){}
    Type(){}
    void useMemberFunction(){}
};

int main() {
    int keyVal = 0, intVal = 0;
    map<int,Type> myMap;
    myMap.insert(make_pair(keyVal,Type(intVal,intVal,intVal))); //Type takes 3 int-values for construction.
    myMap[intVal].useMemberFunction();
}

One note though: As per documentation, std::map::operator[] requires that the value type is default constructible. If the type is not default constructible, then you cannot use the subscript operator. You can use std::map::at or std::map::find instead.

C++ std::map with user defined data type

Because in the statement

forest[i]=Set(i);

the forest[i] will try create a Set object using the default constructor and placed in that location. Then another will be created using Set(i) and will be assigned to the ith position using assignment operator. hence you have to provide a default constructor.

To avoid it use std::map::insert method.

forest.insert( {i, Set(i)} );

What requirements must std::map key classes meet to be valid keys?

All that is required of the key is that it be copiable and assignable.
The ordering within the map is defined by the third argument to the
template (and the argument to the constructor, if used). This
defaults to std::less<KeyType>, which defaults to the < operator,
but there's no requirement to use the defaults. Just write a comparison
operator (preferably as a functional object):

struct CmpMyType
{
    bool operator()( MyType const& lhs, MyType const& rhs ) const
    {
        //  ...
    }
};

Note that it must define a strict ordering, i.e. if CmpMyType()( a, b
) returns true, then CmpMyType()( b, a ) must return false, and if
both return false, the elements are considered equal (members of the
same equivalence class).

Can we use a user defined class for the key in a STL map?

Any type can be used as a key as long as it is

• Copyable
• Assignable
• Comparable, since the map is sorted by key

If your class is just a simple structure, then it's already copyable and assignable. For a class to be comparable, you must either implement operator<, or create the map with a custom comparison function to use instead.

The only impact on time efficiency comes from larger objects taking longer to copy and compare. If the objects need to be that size, then there's nothing you can do about that, so don't worry about it.

Overload std::map with different key type

What you need is called heterogeneous lookup and supported by std::map since C++14. For that you can define your own comparator structure and provide type is_transparent in it to enable this functionality. Details on how to enable heterogeneous lookup can be found here How can I search an std::map using a key of a different type

Also note, while std::map::find() does support it std::map::operator[] does not, so you have to replace your code:

if (index.find("test") != index.end())
{
   index["test"].push_back(0);
}

to something like:

 auto it = index.find("test");
 if( it != index.end()) 
     it->second.push_back(0);

and you should do that anyway, as you would do two lookups instead of one otherwise and that is significantly expensive operation on map.

So for your case comparator should be something like:

struct CompareType
{
    using is_transparent = std::true_type;

    // standard comparison (between two instances of Type)
    bool operator()(const Type& lhs, const Type& rhs) const { return lhs.key < rhs.key; }
    // comparisons btw Type and std::string
    bool operator()( const Type& lhs, const std::string &rhs) const { return lhs.key < rhs; }
    bool operator()(const std::string &lhs, const Type& rhs) const { return lhs < rhs.key; }
};

then you create your map by:

std::map<Type, std::vector<int>,CompareType> index;

and you do not need comparison methods in Type itself anymore

Another way is to submit std::less<> as third parameter to std::map, but in that case you are missing the comparison operator, that takes std::string as left operand and Type as right and as that comparison operator cannot be member of Type I think it is cleaner to do it through a separate comparator (code there is consistent).

Using find in map with user defined class as key

std::map is using the relational operator < for ordering and checking key uniqueness. Since your implementations of operator< use the a member only for comparing it will ignore b when evaluating key equality. operator== is not used from the map interface - it is replaced by !(a < b || b < a). You need something like

bool Entry::operator<(const Entry& e){
    return a < e.a || a == e.a && b < e.b;
}

You could remove operator> and operator== or keep them if you need them for other purposes.

---

Related Topics