Метод upper_bound

Метод upper_bound класса map возвращает итератор на первый элемент контейнера, ключ которого строго больше заданного значения. Если такого элемента нет, метод возвращает итератор на позицию end. В первый параметр мы передаем ключ, относительно которого выполняется поиск. Контейнер при этом не изменяется.

Метод работает за логарифмическое время O(log n), так как элементы в map хранятся в отсортированном по ключу порядке.

Синтаксис

it = m.upper_bound(key)

Пример

Давайте создадим словарь с числовыми ключами и найдем первый элемент, ключ которого больше числа 3:

#include <iostream>
#include <map>
using namespace std;

int main()
{
	map<int, string> m = {
		{1, "a"},
		{2, "b"},
		{3, "c"},
		{4, "d"},
		{5, "e"}
	};

	auto it = m.upper_bound(3);
	cout << it->first << " " << it->second << endl;
	return 0;
}

Результат выполнения кода:

"4 d"

Пример

Давайте проверим, что вернет метод, если заданный ключ больше или равен максимальному ключу в контейнере:

#include <iostream>
#include <map>
using namespace std;

int main()
{
	map<int, string> m = {
		{1, "a"},
		{2, "b"},
		{3, "c"}
	};

	auto it = m.upper_bound(3);

	if (it == m.end()) {
		cout << "end" << endl;
	} else {
		cout << it->first << " " << it->second << endl;
	}

	return 0;
}

Результат выполнения кода:

"end"

Пример

Давайте переберем все элементы словаря, ключ которых больше числа 2, используя метод upper_bound:

#include <iostream>
#include <map>
using namespace std;

int main()
{
	map<int, string> m = {
		{1, "a"},
		{2, "b"},
		{3, "c"},
		{4, "d"},
		{5, "e"}
	};

	for (auto it = m.upper_bound(2); it != m.end(); ++it) {
		cout << it->first << " " << it->second << endl;
	}

	return 0;
}

Результат выполнения кода:

"3 c"
"4 d"
"5 e"

Смотрите также

метод lower_bound,
который ищет первый элемент с ключом не меньше заданного
метод find,
который ищет элемент по заданному ключу
метод equal_range,
который возвращает диапазон элементов с заданным ключом
класс map,
который представляет собой словарь с уникальными ключами