Как искать на карте / мультикарте, начиная с определенной позиции

Question

Я хочу искать в карте / мультикарте , но не во всех.Вместо этого я хочу начать с определенной позиции.

В следующем примере я хочу найти два первых числа, которые суммируют b .И вернуть их значение.

multimap<int, int> a;
a.insert(make_pair(2, 0));
a.insert(make_pair(2, 1));
a.insert(make_pair(5, 2));
a.insert(make_pair(8, 3));

int b = 4;

for(auto it = a.begin(); it != a.end(); ++it) {
    auto it2 = a.find(b - it->first); //Is there an equivalent that starts from "it+1"?
    if(it2 != a.end()) {
        cout << it->second << ", " << it2->second << endl;
        break;
    }
}

вывод:

0, 0

желаемый вывод:

0, 1

Можно ли добиться поиска конкретной позиции на карте?

Answer 1

Как искать на карте, начиная с определенной позиции

Вы можете использовать std::find.Но это не идеально, так как он имеет линейную сложность по сравнению с логарифмической сложностью поиска по карте.Интерфейс std::map не поддерживает такую ​​операцию для поиска.

Если вам нужна такая операция, вам нужно использовать другую структуру данных.Это должно быть возможно реализовать путем дополнения (сбалансированного) дерева поиска указателем родительского узла.Недостатком является, конечно, увеличение использования памяти и постоянные накладные расходы на операции, которые изменяют древовидную структуру.

не от начала до конца.

Поиск по карте неначать с «начала» диапазона.Они начинаются с корня дерева.

Answer 2

Если вы используете упорядоченную карту (которая звучит так же, как и вы), то она уже выполняет бинарный поиск с std::find.Эта функция возвращает тип итератора, поэтому предположим, что вы искали значение некоторого ключа x, а затем рассмотрите следующие строки:

std::map<char,int> mymap;
mymap['x'] = 24;
std::map<char,int>::iterator itr = mymap.find('x');
std::cout << "x=" << itr->second << std::endl;

Причина, по которой ваш код не компилировался, была вероятной, потому что вы пытались вернутьпарный итератор, который не печатает точно, чтобы вывести все это хорошо.Вместо этого вызов itr->second позволяет получить значение, связанное с нужным ключом.