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

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