Метод lower_bound

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

Так как элементы в map всегда отсортированы по ключу, метод lower_bound выполняет поиск за логарифмическое время. Контейнер при этом не изменяется.

Синтаксис

m.lower_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.lower_bound(3);
	
	if (it != m.end()) {
		cout << it->first << " " << it->second << endl;
	}
	
	return 0;
}

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

"3 c"

Пример

Давайте найдем позицию для ключа, которого нет в контейнере. Например, для ключа 3 при наличии ключей 1, 2, 4, 5 метод вернет итератор на первый ключ, который больше 3:

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

int main()
{
	map<int, string> m = {
		{1, "a"},
		{2, "b"},
		{4, "d"},
		{5, "e"}
	};
	
	auto it = m.lower_bound(3);
	
	if (it != m.end()) {
		cout << it->first << " " << it->second << endl;
	}
	
	return 0;
}

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

"4 d"

Пример

Если все ключи в контейнере меньше заданного значения, метод возвращает итератор end. Давайте проверим это для ключа 10:

#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.lower_bound(10);
	
	if (it == m.end()) {
		cout << "not found" << endl;
	}
	
	return 0;
}

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

"not found"

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

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