How to make a C++ map container where the key is part of the value?

Question

I want to store a bunch of key-value objects, but where the value object itself (and references to it) knows its key. I also want to efficiently lookup these objects given only the key.

class SomeObject
{
private:
    //String or integer. int seem cheap enough to duplicate with std::map, but
    //strings seem pretty expensive when there may be thousands of objects in existence.
    //Reference/Pointer to key is fine
    const SomeOtherObject key;
    ...other stuff...
public:
    ...methods, some of which use the key in some way...
};

• std::map
  • Seems to require that the storage is an std::pair, such that the value cant access the key. If the value contains the key, it needs to be duplicated.
  • Does not actually enforce that the key inside the value does not get changed in some way
• std::set
  • Looks like a really good solution, using a custom compare method to provide uniqueness by key, until you realise it made your entire value const, not just the key field.
• std::vector (or other array/list like solutions)
  • Can use linear search, or if the items are kept sorted binary search. However I suspect this not not optimal in performance terms, and an extra layer of some kind is needed to really implement the desired behaviour with it.

Answer 1

C++14 std::set::find non-key searches

As mentioned at http://en.cppreference.com/w/cpp/container/set/find C++14 has added two new find APIs:

main.cpp

template< class K > iterator find( const K& x );
template< class K > const_iterator find( const K& x ) const;

which allow you to do:

main.cpp

#include <cassert>
#include <set>

class Point {
    public:
        // Note that there is _no_ conversion constructor,
        // everything is done at the template level without
        // intermediate object creation.
        //Point(int x) : x(x) {}
        Point(int x, int y) : x(x), y(y) {}
        int x;
        int y;
};
bool operator<(const Point& c, int x) { return c.x < x; }
bool operator<(int x, const Point& c) { return x < c.x; }
bool operator<(const Point& c, const Point& d) {
    return c.x < d;
}

int main() {
    // std::less<> because of:
    // https://stackoverflow.com/questions/20317413/what-are-transparent-comparators
    std::set<Point, std::less<>> s;
    s.insert(Point(1, -1));
    s.insert(Point(2, -2));
    s.insert(Point(0,  0));
    s.insert(Point(3, -3));
    assert(s.find(0)->y ==  0);
    assert(s.find(1)->y == -1);
    assert(s.find(2)->y == -2);
    assert(s.find(3)->y == -3);
    // Ignore 1234, find 1.
    assert(s.find(Point(1, 1234))->y == -1);
}

Tested on Ubuntu 16.10, g++ 6.2.0, with:

g++ -std=c++14 -Wall -Wextra -pedantic -o main.out main.cpp
./main.out

Using a custom class instead of less<>

This makes things a bit more explicit and allows you to write multiple comparators per class:

#include <cassert>
#include <set>

class Point {
    public:
        Point(int x, int y) : x(x), y(y) {}
        int x;
        int y;
};

struct PointCmpY {
    // https://stackoverflow.com/questions/20317413/what-are-transparent-comparators
    typedef std::true_type is_transparent;
    bool operator()(const Point& lhs, int rhs) const {
        return lhs.y < rhs;
    }
    bool operator()(int lhs, const Point& rhs) const {
        return lhs < rhs.y;
    }
    bool operator()(const Point& lhs, const Point& rhs) const {
        return lhs.y < rhs.y;
    }
};

int main() {
    std::set<Point, PointCmpY> s;
    s.insert(Point(1, -1));
    s.insert(Point(2, -2));
    s.insert(Point(0,  0));
    s.insert(Point(3, -3));
    assert(s.find(0)->x == 0);
    assert(s.find(-1)->x == 1);
    assert(s.find(-2)->x == 2);
    assert(s.find(-3)->x == 3);
    assert(s.find(Point(1234, -1))->x == 1);
}

See also

• Is it possible to use elements of a different type than contained in a std::set to perform search and deletion?
• Raw pointer lookup for sets of unique_ptrs
• index objects by multiple keys: How to index and query STL map containers by multiple keys?
• implement a bimap efficiently: Is there a more efficient implementation for a bidirectional map?

Answer 2

C++ provides the mutable keyword that would allow you using the second solution -- a set. Declaring your value as mutable in your item class will allow modifying it even if the item is const. See also: Does the 'mutable' keyword have any purpose other than allowing the variable to be modified by a const function?

Or, even simpler, implement an accessor for your value that const_casts away the constant-ness of the item.