С ++: нужно установить индексируется

Question

мне нужно индексированный ассоциативный контейнер, который работает следующим образом:

• изначально пустой, размер = 0.

• Когда я добавляю к нему новый элемент, он помещает его в индекс [размер], очень похожий на push_back вектора. Он увеличивает размер и возвращает индекс вновь добавленного элемента.

• Если элемент уже существует, он возвращает индекс, где он встречается.

Set кажется идеальной структуры данных для этого, но я не вижу каких-либо вещь, как получение индекс из операции поиска. Найти в наборе возвращает итератор элементу.

Будет ли иметь значение с set.begin() быть правильной вещью в этой ситуации?

Answer 1

В 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; 
} 

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

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

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

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

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