crossplatform.ru

Здравствуйте, гость ( Вход | Регистрация )

 
Ответить в данную темуНачать новую тему
> задачка с std::map :)
Алексей1153
  опции профиля:
сообщение 15.2.2011, 12:02
Сообщение #1


фрилансер
******

Группа: Участник
Сообщений: 2886
Регистрация: 19.6.2010
Из: Обливион
Пользователь №: 1822

Спасибо сказали: 215 раз(а)




Репутация:   34  


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

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

(B - не включено в диапазон)
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
kwisp
  опции профиля:
сообщение 15.2.2011, 12:12
Сообщение #2


астарожна ынтжинэр
*****

Группа: Участник
Сообщений: 1404
Регистрация: 26.11.2008
Из: ТаганрогРодинаЧехова
Пользователь №: 435

Спасибо сказали: 113 раз(а)




Репутация:   23  


Алексей1153,
уточни пожалуйста диапазон может быть любой
т.е.
1: [0, 3, 4, 5, 8, 11 )
или только
2: [3,4,5,6,7,8,9,10 )
?
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
kwisp
  опции профиля:
сообщение 15.2.2011, 12:51
Сообщение #3


астарожна ынтжинэр
*****

Группа: Участник
Сообщений: 1404
Регистрация: 26.11.2008
Из: ТаганрогРодинаЧехова
Пользователь №: 435

Спасибо сказали: 113 раз(а)




Репутация:   23  


в map значения отсортированные по ключам.
итератор begin соответсвует меньшему ключу итератор end большему ключу.
очевидны простые ответы
1. если диапазон искомых не входит в диапазон ключей от begin до end ответ А.
2. если имеет пересечение у нижней границы ключей то ответ тоже А
1 и 2 можно обЪединить.
3. если диапазон искомых и ключей имеют пересечение у верхней границы ключей то ответ ключ итератора end +1
4. сымый сложный случай: если интервал искомых входит в интервал ключей полностью - в цикле пока ключ входит в диапазон перебирать ключи вычисляя разность между соседними ключами, если разность больше 1, то искомое значение младший ключ+1.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Iron Bug
  опции профиля:
сообщение 15.2.2011, 20:47
Сообщение #4


Профессионал
*****

Группа: Модератор
Сообщений: 1587
Регистрация: 6.2.2009
Из: Yekaterinburg
Пользователь №: 533

Спасибо сказали: 218 раз(а)




Репутация:   12  


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

Сообщение отредактировал Iron Bug - 15.2.2011, 20:50
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Алексей1153
  опции профиля:
сообщение 15.2.2011, 22:07
Сообщение #5


фрилансер
******

Группа: Участник
Сообщений: 2886
Регистрация: 19.6.2010
Из: Обливион
Пользователь №: 1822

Спасибо сказали: 215 раз(а)




Репутация:   34  


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

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

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

поэтому решил так - простым перебором ищу первый элемент в диапазоне и последний. Затем по ним шагаю и определяю, какой ключ взять, если всё не заполнено под завязку
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
kwisp
  опции профиля:
сообщение 16.2.2011, 10:39
Сообщение #6


астарожна ынтжинэр
*****

Группа: Участник
Сообщений: 1404
Регистрация: 26.11.2008
Из: ТаганрогРодинаЧехова
Пользователь №: 435

Спасибо сказали: 113 раз(а)




Репутация:   23  


Алексей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 - произвольные.

да это значительно усложняет задачу.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение

Ответить в данную темуНачать новую тему
Теги
Нет тегов для показа


1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0




RSS Текстовая версия Сейчас: 15.10.2019, 2:13