структура данных в c++

> Как заботать следующее: имеется отображение int'ов в другие объекты.
> Нужно по значению int k найти наибольший ключ, не превосходящий k, ну
> и потом найти объект, соответствующий этому ключу. В контейнере map
> такой функциональности почему-то не нашел. Может плохо искал...

std::map::lower_bound(k) вернет итератор на первый элемент, ключ
которого больше либо равен k. Потом через operator-- получаешь итератор
на предыдущий элемент, который и будет нужным тебе.

Да, очевидно, перед тем, как вызывать operator--, неплохо бы сначала
проверить, что итератор не равен m.begin() - что равносильно отсутствию
удовлетворяющих условию элементов.

> s/begin/end/;

Нет, именно begin(). Т.к. после проверки мы вызываем operator--, а не
operator++.

В случае, если контейнер пуст, begin()==end().