Как создать контейнер карты С++, где ключ является частью значения?

Я хочу хранить кучу объектов с ключом, но где сам объект значения (и ссылки на него) знает свой ключ. Я также хочу эффективно искать эти объекты, учитывая только ключ.

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:: pair, так что значение can not получило доступ к ключу. Если значение содержит ключ, его необходимо дублировать.
- На самом деле не гарантирует, что ключ внутри значения не будет каким-либо образом изменен.
станд:: набор
- Похоже на действительно хорошее решение, используя специальный метод сравнения, чтобы обеспечить уникальность по ключевому слову, пока вы не осознаете, что это сделало ваше целое значение const, а не только ключевым полем.
std::vector (или другие решения типа array/list like)
- Может использовать линейный поиск, или если элементы хранятся в сортированном двоичном поиске. Однако я подозреваю, что это не является оптимальным в плане производительности, и необходим дополнительный уровень, необходимый для реального осуществления с ним желаемого поведения.

Ответ 1

С++ 14 std::set::find неключевой поиск

Как уже упоминалось на http://en.cppreference.com/w/cpp/container/set/find, С++ 14 добавил два новых API find:

main.cpp

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

которые позволяют вам сделать:

#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);
}

Протестировано на Ubuntu 16.10, g++ 6.2.0, с:

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

Использование собственного класса вместо less<>

Это делает вещи немного более явными и позволяет писать несколько компараторов для каждого класса:

#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);
}

Смотрите также

Ответ 2

Я чувствую твою боль. Что меня бесит, так это то, что set и map всегда реализуются с использованием одной и той же структуры данных под капотом, которая представляет собой tree значений, параметризованное с помощью экстрактора ключей. К сожалению, в стандарте такого нет.

Если boost в порядке, используйте Boost.MultiIndex, чтобы добиться того, что вам нужно. Взгляните на Boost.Intrusive тоже.

Ответ 3

С++ предоставляет ключевое слово mutable, которое позволит вам использовать второе решение - a set. Объявление вашего значения как mutable в вашем классе элемента позволит его изменить, даже если элемент const. Смотрите также: Имеет ли ключевое слово "изменчивое" какие-либо цели, кроме возможности изменения переменной с помощью функции const?

Или, что еще проще, реализуйте аксессуар для вашего значения, чтобы const_cast удалил константу элемента.

Ответ 4

... но где сам объект значения (и ссылки на него) знает свой ключ

Карта

Объект не может знать "свой" ключ, поскольку указатель на один и тот же объект может быть добавлен на несколько карт с использованием разных ключей. Ключ принадлежит карте; а не к объекту.

Set:

Что произойдет, когда значение этого члена изменится? Как вы могли бы переиндексировать? Вот почему set принудительно устанавливает константу.

-

Вы пытаетесь индексировать элементы данного класса на основе одного из его членов, но вы не хотите копировать этот элемент для целей индексирования, и вы не хотите создавать объект const (я предполагаю, что вы хотите сделать элемент const).

Я бы построил его поверх дерева Red-Black или AVL.

Я недостаточно знаком с Boost.MultiIndex, предложенным ybungalobill. Я не уверен, что его экземплярный код копирует проиндексированный элемент или как он обрабатывает изменения значений для этого члена.