57 / 51 / 42
Регистрация: 18.07.2014
Сообщений: 194
1

Бинарный поиск для std::list

10.11.2014, 18:00. Показов 1880. Ответов 3
Метки нет (Все метки)

Здравствуйте.

Хотел написать бинарный поиск для std::list. Пишу:


C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//Тип coord определён выше
 
std::list<coord>::iterator LifeMap::search(coord c)
    {
        std::list<coord>::iterator left, right, middle;
        left = map.begin();
        right = map.end();
        while ( left < right )
        {
            middle = (left + right) / 2;
            if ( *middle == c )
                return middle;
            else if ( *middle > c )
                right = middle;
            else left = middle;
        }
        return map.end();
    }
Но для std::list<coord>::iterator операторы + и < не перегружены. Как быть?

Добавлено через 2 минуты
search - метод класса LifeMap. У класса есть член - std::list<coord> map
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
10.11.2014, 18:00
Ответы с готовыми решениями:

Чтение бинарного файла в поток std::ifstream и вывод в другой бинарный файл std::ofstream (создание копии)
Проверил работу программы на маленькой картинке(744 байт). Все работает. С несколько бОльшими...

Remove_if для std::list
Здравствуйте! Помогите мне разобраться,пожалуйста.Перечитал кучу всего,но так и не понял ,что...

Предикат для сортировки std::list
Помогите правильно составить предикат для сортировки std::list Валит ошибку WinXP, VC6 ...

Std::list для списков с несколькими типами данных
обычно все примеры использования std:list строятся на одном типе переменых типа list&lt;int&gt;...

3
3250 / 2052 / 351
Регистрация: 24.11.2012
Сообщений: 4,902
10.11.2014, 18:19 2
Цитата Сообщение от porshe Посмотреть сообщение
Как быть?
Использовать std::vector. У листа нет и не может быть random-access итератора.

Добавлено через 3 минуты
Ну и чтобы не велосипедить: http://en.cppreference.com/w/c... ower_bound
1
С чаем беда...
Эксперт CЭксперт С++
9283 / 4776 / 1296
Регистрация: 18.10.2014
Сообщений: 10,915
10.11.2014, 18:21 3
Вместо оператора + использовать 'std::advance'. Для итераторов 'std::list' он будет искать соотв. позицию путем банального последовательного прохода по списку. Алгоритм будет работать, но все это будет иметь лишь академическую ценность именно из-за невозможности прямого доступа. В списке нет смысла делать бинарный поиск.
1
57 / 51 / 42
Регистрация: 18.07.2014
Сообщений: 194
10.11.2014, 18:53  [ТС] 4
Цитата Сообщение от 0x10 Посмотреть сообщение
Использовать std::vector
std::vector нельзя, потому что операция удаления элемента слишком медленная
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
10.11.2014, 18:53

Реализация std::list, сложность list::size()
Часто приходилось пользоваться Listом, но сейчас столкнулся с небольшой неоднозначностью. ...

Потокобезопасность std::map::end, std::list::end
Собсна сабж, могу ли я без синхронизаций выполнять подобного рода код if (myIter != map.end()) //...

Бинарный поиск для нахождения нечетных чисел
Подскажите пожалуйста как этот алгоритм линейного поиска обернуть в бинарный поиск for(int i =...

Std:string в бинарный файл и обратно
Извините! Тупонул. Уже сам всё сделал. Не знаю как только тему удалить теперь.


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.