Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум на CrossPlatform.RU _ Алгоритмы, задачи по программированию, логические игры _ задачка с std::map :)

Автор: Алексей1153 15.2.2011, 12:02

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

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

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

Автор: kwisp 15.2.2011, 12:12

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

Автор: kwisp 15.2.2011, 12:51

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

Автор: Iron Bug 15.2.2011, 20:47

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

Автор: Алексей1153 15.2.2011, 22:07

Цитата(kwisp @ 15.2.2011, 14:12) *
уточни пожалуйста диапазон может быть любой

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

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

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

Автор: kwisp 16.2.2011, 10:39

Алексей1153,

Цитата(Алексей1153 @ 15.2.2011, 22:07) *
Но только я не сумел его подружить с мапом, там же 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 обойтись.

Цитата(Алексей1153 @ 15.2.2011, 22:07) *
на входе A и B - произвольные.

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

Форум Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)