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

I feel your pain. What makes me mad is that set and map are always implemented using the same data-structure under the hood, which is a tree of values parametrized with a key extractor. Unfortunately there is no such thing in the standard.

If boost is OK, use Boost.MultiIndex to achieve what you need. Take a look at Boost.Intrusive too.

Answer 3

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.

Answer 4

... but where the value object itself (and references to it) knows its key

Map:

The object can't know 'its' key, since a pointer to the same object may be added to several maps, using different keys. The key belongs to a map; not to an object.

Set:

What should happen when the value of this member changes? How would you force a reindexing? This is why set enforces constness.

--

You are trying to index items of a given class based on one of its members, but you don't want to copy this member for indexing purposes, and you don't want to make the object const (I assume that you do want to make the member const).

I would have built it on top of a Red-Black or AVL tree.

I'm not familiar enough with Boost.MultiIndex suggested by ybungalobill. I'm not sure whether its instantiated code copies the indexed member, or how it handles values changes for this member.