Why std::map takes custom comparator only by lvalue reference?

Question

I am wondering why STL classes like map or unordered_map take custom comparator and hasher objects only by const lvalue reference and not by rvalue reference.

unordered_map( size_type bucket_count,
               const Hash& hash,
               const Allocator& alloc )
              : unordered_map(bucket_count, hash, key_equal(), alloc) {}

template< class InputIt >
map( InputIt first, InputIt last,
     const Compare& comp = Compare(),
     const Allocator& alloc = Allocator() );

In most cases it doesn't matter much, because these objects are normally lightweight, but what if they happened to be quite heavy to copy?

#include <iostream>
#include <string>
#include <unordered_map>
#include <map>

struct Key
{
    std::string first, second;
    int third;

    bool operator==(const Key& other) const
    {
        return (first == other.first && second == other.second && third == other.third);
    }
};

struct KeyHasher
{
    KeyHasher(int param) : myparam(param) {}
    KeyHasher(const KeyHasher& other) { std::cout << "copy" << std::endl; }
    KeyHasher(KeyHasher&& other) { std::cout << "move" << std::endl; }
    std::size_t operator()(const Key& k) const
    {
        using std::size_t;
        using std::hash;
        using std::string;

        return ((hash<string>()(k.first) ^ (hash<string>()(k.second) << 1)) >> 1) ^ (hash<int>()(k.third) << 1);
    }

private:
    int myparam = 22;
    // heavy objects...
};


struct KeyComparator 
{
    KeyComparator() = default;
    KeyComparator(const KeyComparator& other) { std::cout << "copy" << std::endl; }
    KeyComparator(KeyComparator&& other) { std::cout << "move" << std::endl; }
    bool operator()(const Key& lhs, const Key& rhs) const 
    {
        return lhs.third < rhs.third; 
    }
    
    // heavy objects...
};

int main()
{
    std::map<Key, std::string, KeyComparator> map1( KeyComparator{} );      // can't move key comparator
    map1.insert({ {"John", "Galt", 12}, "first" });
    map1.insert({ {"Mary", "Sue", 21}, "second" });

    std::unordered_map<Key, std::string, KeyHasher> map2{ 33, KeyHasher(729) };     // can't move key hasher
    map2.insert({ {"Marie", "Curie", 17}, "radium" });
    
    return 0;
}

Was there a rationale not to add overloads like the following:

unordered_map( size_type bucket_count,
               Hash&& hash,
               Allocator&& alloc ) {}

template< class InputIt >
map( InputIt first, InputIt last,
     Compare&& comp = Compare(),
     Allocator&& alloc = Allocator() );

The same question about allocators which are used in every STL container.

lubgr lubgr · Accepted Answer · 2021-03-04T09:18:23

It's a very basic design decision of the standard library to assume that all function objects are small. If they're not, which should be a rare case, responsability is shifted to the client code - you could work with std::reference_wrapper, closures that refer to the heavy state somewhere on the heap (think of [heavyObject = std::make_unique<SomeType>()](...) { /* ... */ } and so on.

As a reference, see Item 38 in Scott Meyers "Effective STL", named "Design functor classes for pass-by-value":

STL function objects are modeled after function pointers, so the convention in the STL is that function objects, too, are passed by value (i.e., copied) when passed to and from functions.

Why std::map takes custom comparator only by lvalue reference?

2 Answers