Помощь - Поиск - Пользователи - Календарь
Полная версия этой страницы: задачка с std::map :)
Форум на CrossPlatform.RU > Курилка > Алгоритмы, задачи по программированию, логические игры
Алексей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.
Алексей1153
Цитата(kwisp @ 15.2.2011, 14:12) *
уточни пожалуйста диапазон может быть любой

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

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

поэтому решил так - простым перебором ищу первый элемент в диапазоне и последний. Затем по ним шагаю и определяю, какой ключ взять, если всё не заполнено под завязку
kwisp
Алексей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 - произвольные.

да это значительно усложняет задачу.
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.
Форум IP.Board © 2001-2022 IPS, Inc.