C ++: нужен индексированный набор - PullRequest
Новая
       21

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

0 голосов
/ 01 апреля 2010

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

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

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

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

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

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

1 Ответ

3 голосов
/ 01 апреля 2010

Для этого в 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 и проверять часть результата bool, чтобы увидеть, нужно ли обновить indexed и т. Д.)

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

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

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

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

...