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

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

2 голосов
/ 23 марта 2020

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

Код, использующий 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));
}

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

1 Ответ

0 голосов
/ 23 марта 2020

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

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

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

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

...