задачка с std::map :) Опции

[Алексей1153]

Задача простая (на превый взгляд):

как наиболее быстро найти в std::map<int,int> наименьший неиспользованный ключ в диапазоне [A,B )

(B - не включено в диапазон)

[kwisp]

Алексей1153,
уточни пожалуйста диапазон может быть любой
т.е.
1: [0, 3, 4, 5, 8, 11 )
или только
2: [3,4,5,6,7,8,9,10 )
?

[kwisp]

в map значения отсортированные по ключам.
итератор begin соответсвует меньшему ключу итератор end большему ключу.
очевидны простые ответы
1. если диапазон искомых не входит в диапазон ключей от begin до end ответ А.
2. если имеет пересечение у нижней границы ключей то ответ тоже А
1 и 2 можно обЪединить.
3. если диапазон искомых и ключей имеют пересечение у верхней границы ключей то ответ ключ итератора end +1
4. сымый сложный случай: если интервал искомых входит в интервал ключей полностью - в цикле пока ключ входит в диапазон перебирать ключи вычисляя разность между соседними ключами, если разность больше 1, то искомое значение младший ключ+1.

[Iron Bug]

думаю, примерно так:
берём интервал (первый раз - все элементы мапа). берём первый и последний элементы и сравниваем разницу их ключей с количеством элементов в интервале. если разница+1 равна количеству, то нефиг там искать - там нет свободных ключей. если разница оказалась больше - то делим интервал пополам и рассматриваем по одному первую и вторую половину.
ну и так далее.
но тут надо смотреть, сколько тиков тратится на операции. может, проще тупо перебором...
а ещё можно также делить, но искать с помощью upper_bound и lower_bound.

Сообщение отредактировал Iron Bug - 15.2.2011, 20:50

[Алексей1153]

уточни пожалуйста диапазон может быть любой

на входе A и B - произвольные.

Iron Bug, lower_bound в основном Но только я не сумел его подружить с мапом, там же value_type составной, третий аргумент никак не могу сообразить

поэтому решил так - простым перебором ищу первый элемент в диапазоне и последний. Затем по ним шагаю и определяю, какой ключ взять, если всё не заполнено под завязку

[kwisp]

Алексей1153,

Но только я не сумел его подружить с мапом, там же value_type составной, третий аргумент никак не могу сообразить

можно так:

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() );

думаю можно и без лишнего создания pair обойтись.

на входе A и B - произвольные.

да это значительно усложняет задачу.