Задача простая (на превый взгляд):
как наиболее быстро найти в std::map<int,int> наименьший неиспользованный ключ в диапазоне [A,B )
(B - не включено в диапазон)
Алексей1153,
уточни пожалуйста диапазон может быть любой
т.е.
1: [0, 3, 4, 5, 8, 11 )
или только
2: [3,4,5,6,7,8,9,10 )
?
в map значения отсортированные по ключам.
итератор begin соответсвует меньшему ключу итератор end большему ключу.
очевидны простые ответы
1. если диапазон искомых не входит в диапазон ключей от begin до end ответ А.
2. если имеет пересечение у нижней границы ключей то ответ тоже А
1 и 2 можно обЪединить.
3. если диапазон искомых и ключей имеют пересечение у верхней границы ключей то ответ ключ итератора end +1
4. сымый сложный случай: если интервал искомых входит в интервал ключей полностью - в цикле пока ключ входит в диапазон перебирать ключи вычисляя разность между соседними ключами, если разность больше 1, то искомое значение младший ключ+1.
думаю, примерно так:
берём интервал (первый раз - все элементы мапа). берём первый и последний элементы и сравниваем разницу их ключей с количеством элементов в интервале. если разница+1 равна количеству, то нефиг там искать - там нет свободных ключей. если разница оказалась больше - то делим интервал пополам и рассматриваем по одному первую и вторую половину.
ну и так далее.
но тут надо смотреть, сколько тиков тратится на операции. может, проще тупо перебором...
а ещё можно также делить, но искать с помощью upper_bound и lower_bound.
Алексей1153,
class mapKeyComp2: public std::binary_function<std::pair<int,int>, std::pair<int,int>, bool> {
public:
bool operator()(std::pair<int,int> leftSide, std::pair<int,int> rightSide) const
{
return leftSide.first < rightSide.first;
}
};
.....
std::map<int,int>::iterator it19 = std::lower_bound(map_.begin(), map_.end(),
std::pair<int,int>(19,0), mapKeyComp2() );
Форум Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)