Как найти пару из множества, используя только второе значение?

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

Код с использованием std::find_if но это занимает линейное время

set<pair<int,int> > s;

s.insert(make_pair(3,1));
s.insert(make_pair(1,0));

auto it = find_if(s.begin(),s.end(),[value](const pair<int,int>& p ){ return p.second == value; });

if(it==s.end()) 
    s.insert(make_pair(1,value));
else {
    int v = it->first;
    s.erase(it);
    s.insert(make_pair(v+1,value));
}

Я хочу использовать функцию set std::find чтобы она занимала логарифмическое время.

Всего 1 ответ


Нет такой структуры данных, которая делает именно то, что вы хотите.

Однако базы данных делают нечто подобное. Они называют это индексным пропуском сканирования . Чтобы реализовать то же самое, не начиная с нуля, вы можете реализовать std::map от первой вещи в паре до std::map второй вещи в паре. И теперь поиск по одной паре является логарифмическим по времени, поиск вещей с заданной первой записью также логарифмичен по времени (хотя итерация по этим вещам может быть медленнее), и поиск вещей со второй записью линейен по количество первых значений у вас, умноженное на логарифмическое число вторых значений, которые у вас есть.

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

Это довольно специфический набор предположений для удовлетворения. Это встречается гораздо чаще для баз данных, чем для программистов на C ++. Вот почему большинство баз данных поддерживают эту операцию, а стандартная библиотека C ++ - нет.


Есть идеи?

10000