С++: нужен индексированный набор

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

std::map<T,size_t> objects;
std::vector<const T *> indexed;

Чтобы добавить элемент:

size_t add_element(const T &v) {
    std::map<T,size_t>::iterator it=objects.find(v);
    if(it==objects.end()) {
        it=objects.insert(std::map<T,size_t>::value_type(v,objects.size())).first;
        indexed.push_back(&it->first);
    }
    return it->second;
}

(Очевидные изменения в соответствии с личным стилем могут состоять в том, чтобы хранить вектор итераторов карты, использовать map::insert каждый раз и проверять логическую часть результата, чтобы увидеть, нуждается ли indexed в обновлении, и т. д.)

И чтобы получить элемент:

const T &get_element(size_t index) {
    return *indexed[index];
}

И это все. Одной из проблем является, конечно, то, что когда объект находится в наборе, его нельзя изменить. Это своего рода утечка из того, как это было реализовано здесь, потому что ключи карты по очевидным причинам являются константами, но на самом деле это то, что нужно в любом случае, я думаю, независимо от реализации. Если вы настаиваете на том, чтобы не было дубликатов, то, как только объект находится в списке, он не должен быть модифицируемым, иначе любые модификации сделают его дубликатом другого объекта.

(Также обратите внимание, что я немного схитрил, используя здесь size_t — я полагаю, что std::vector<const T *>::size_type может быть более точным — это в основном в интересах краткости!)