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

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

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

//Тип 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 операторы + и < не перегружены. Как быть?

Контейнер list не предназначен для произвольного доступа.

Используй vector или deque.

Используй vector или deque.

vector не подойдёт, т.к. слишком «дорогая» операция удаления элемента. У deque не перегружен оператор + :(

А в качестве бинарного поиска можно использовать std::lower_bound?

А зачем тебе вообще бинарный поиск, да ещё в списке?

Чем тебя не устраивает find?

Если не секрет, что ты такое делаешь, что тебе нужен столь экзотический набор свойств контейнера?

Пишу класс LifeMap, решаю эту задачу.
Есть список живых точек — std::list<coord> map.
Всякий раз при обращении к значению точки(метод getCell(x,y), нужно искать эту точку в map.
Над функцией std::find я уже думал, но она работает за O(n), а это медленно, если количество точек становится большим. Я решил использовать бинарный поиск, он быстрее, т.к. работает за O(log(n)).

Бинарный поиск, говоришь...
А у тебя список отсортирован?
А как у тебя отсортирован список? По X? по Y? или как-то ещё?

Да, и кстати, что значит c1 > c2 для типа coord? Подозреваю, что struct coord { long long x, y; }, ну или около того.

А у тебя список отсортирован?

Да.

А как у тебя отсортирован список? По X? по Y? или как-то ещё?

По Y.

Подозреваю, что

Чуть больше :)

 struct coord
    {
        lsize_t x;
        lsize_t y;
        coord( lsize_t _x = 0, lsize_t _y = 0 ):
            x(_x), y(_y)
        {}
        bool operator ==( const coord &ob ) const  { return x == ob.x && y == ob.y; }
        bool operator >( const coord &ob )  const  { return y > ob.y; }
        bool operator <( const coord &ob )  const  { return !(*this > ob); }
        bool operator !=( const coord &ob ) const  { return !(*this == ob); }

        void binWrite( std::ostream &stream )
        {
            stream.write( reinterpret_cast<char*>( &x ), sizeof( lsize_t ) );
            stream.write( reinterpret_cast<char*>( &y ), sizeof( lsize_t ) );
        }

        void binRead( std::istream &stream )
        {
            stream.read( reinterpret_cast<char*>( &x ), sizeof( lsize_t ) );
            stream.read( reinterpret_cast<char*>( &y ), sizeof( lsize_t ) );
        }

    };

    std::ostream &operator<< ( std::ostream &stream, const coord &ob )
    {
        stream << ob.x << " " << ob.y << std::endl;
        return stream;
    }

    std::istream &operator>> ( std::istream &stream, coord &ob )
    {
        stream >> ob.x >> ob.y;
        return stream;
    }

Если всё так круто, то почему бы не использовать binary_search?

Если ты хочешь активно использовать STL, рекомендую книгу Николай Джосьютис. C++ Стандартная библиотека. Для профессионалов — СП Питер, 2004 ISBN 5-94723-635-4

Издание, правда, достаточно старое. Но актуальность практически не утратило. Есть ли более новое издание — не знаю.

Здесь у тебя неувязочка:

        bool operator >( const coord &ob )  const  { return y > ob.y; }
        bool operator <( const coord &ob )  const  { return !(*this > ob); }

Если истина, что a > b, то из этого не следует, что a < b тоже истина. Они, сволочи, ещё могут быть равны.

Первично лучше определять operator <. Именно он используется в STL для сортировок, сравнений и пр. Следовательно, если он первичен в определении, то хоть немного времени, но сэкономится на вызове лишней подпрограммы.

Если всё так круто, то почему бы не использовать binary_search?

Насколько я понимаю, binary_search только ищет элемент, и возвращает true, если элемент найден и false в противном случае. А мне нужен итератор на найденный элемент.

А std::lower_bound не подходит? Он вроде итератор выдает. Только не помню у него линейная скорость или логарифмическая.

Насколько я понимаю, сложность у него логарифмическая.

Оптимизировать нужно только то, что критично к задаче.
В данном же случае я бы посоветовал тебе реализовать рабочий функционал без лишних заморочек с оптимизацией. Например, через std::vector. А потом смотреть по ситуации, нужна ли эта оптимизация вообще.

Также, ты можешь использовать std::map со ссылкой на элемент списка для быстрого поиска по координатам.