Контейнер C ++ для составного индекса, который позволяет игнорировать субиндекс при поиске - PullRequest
Новая
       24

Контейнер C ++ для составного индекса, который позволяет игнорировать субиндекс при поиске

0 голосов
/ 22 февраля 2012

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

Fe с учетом индекса 

struct index_t
{
    index_t(unsigned key_, unsigned subkey_)
        :   key(key_)
        ,   subkey(subkey_)
    {}
    unsigned key;
    unsigned subkey;
};

и вставкой 

index_t(1,11)
index_t(2,21)
index_t(2,22)
index_t(2,23)
index_t(3,31)

всех элементов с fe key == 2 и игнорируя subkey, нужно искать.

Также возможен поиск с указанными key и subkey.Поэтому использование мультимножества / карты с key в качестве ключа единственного контейнера не является решением.

1 Ответ

0 голосов
/ 22 февраля 2012

Вы можете сделать 

std::set<index_t>  mySet;

И для поиска всех элементов с данным ключом и любым подразделом выполните 

std::pair<std::set<index_t>::iterator, std::set<index_t>::iterator> range;
range.first = mySet.lower_bound(index_t(key, 0));
range.second = mySet.upper_bound(index_t(key, UINT_MAX));

Это сохранит 2 * log n производительности.

...