Поиск мультикарты в обратном порядке

Question

Существует ли метод поиска мультикарты (C / C ++ STL) в обратном порядке по логарифмической сложности?

Answer 1

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

В качестве альтернативы, если вы хотите пересечь multimap в обратном порядке, вы можете использовать rbegin() и rend() для получения обратных итераторов.

Answer 2

Я почти уверен, что, поскольку multimap является в основном древовидным представлением, единственный механизм поиска - это обход дерева - здесь нет «вперед» и «назад».первый соответствующий элемент с lower_bound, один после последнего соответствия с upper_bound или полный диапазон, соответствующий ключу с equal_range.РЕДАКТИРОВАТЬ: Все эти методы работают в логарифмической сложности.

Не могли бы вы более подробно о том, что вам нужно?

Answer 3

Я предполагаю, что вы ищете алгоритм поиска, чтобы найти ключ в std::multimap, который

1. гарантирует O(log n), чтобы найти любой ключ в multimapиз n ключей

2. гарантирует O(1) найти ключ, который является наибольшим ключом, удерживаемым multimap

Существуетнет такой вещи встроенной.Большинство (все?) Мультикарты реализованы в виде сбалансированных деревьев, и вызов multimap::find() сначала проверяет середину карты, поскольку именно там находится корень дерева.Вы сами можете убедиться, что вы реализуете шум operator<.

Будет ли просто проверка ключа, на который указывает rbegin() перед вызовом multimap::find(), удовлетворить ваши требования?

Если от "lastвставлено: «Вы действительно имели в виду элемент, который был добавлен на карту самым последним, тогда его вообще невозможно найти, multimap и другие ассоциативные контейнеры не сохраняют информацию о порядке вставки.

Answer 4

Вы можете просто использовать upper_bound и lower_bound как обычно, но поменять местами код итерации.

Последний соответствующий элемент найден с помощью:

ub = m.upper_bound(1);
lb = m.lower_bound(1);
if (ub != lb) {
  --ub;
  return ub->second;
}

Или только с одним поиском:

ub = m.upper_bound(1);
if (ub != m.begin()) {
  --ub;
  if (ub->first == 1) {
    return ub->second;
  }
}