Вычисление номера элемента в отсорированном массиве в SQL

Столкнулся с такой задачей: нужно для каждой строки результата работы SQL-запроса вывести номер этой строки внутри отсортированного по неким параметрам массива. Чтобы было понятно, о чем речь, приведу пример. Есть таблица с данными:
val
-------
7
3
1
5
9
4

Нужно вывести эти числа, не используя ORDER BY или еще каких SQL-инструкций  и вычилсить их номер в отсортированном массиве. Результат должен быть такой:
val   idx
--------------
7    |   4
3    |   1
1    |   0
5    |   3
9    |   5
4    |   2

Столбец "index" должен быть вычислен. Что есть номер элемента в отсортированном по возрастанию массиве? - это число элементов, которые меньше его. Если таких элементов нет - то значит данный элемент самый маленький и будет стоять первым и иметь индекс 0. Таким образом, получаем первый вариант запроса:

 SELECT
     tbl.value as val
    (SELECT
         count(*)
     FROM
         tbl tbl2
     WHERE
        tbl2.value < val ) as idx
FROM
    tbl

Это будет работать, но возникает проблема, если есть повторяющиеся числа. Тогда некоторые элементы будут иметь одинаковый индекс, а нам это не подходит. Что делать в таком случае? Я использовал значение первичного ключа как дополнительный параметр для сравнения: если два значения равны, то сравниваем их первичные ключи - уж они-то точно будут разными. Улучшенный вариант предыдущего запроса будет выглядеть так:


SELECT
     tbl.id  as myid
     tbl.value as val
    (SELECT
         count(*)
     FROM
         tbl tbl2
     WHERE
        (tbl2.value < val)
        OR
        (tbl2.value = val AND tbl2.id < myid) ) as idx
FROM
    tbl

Последний вариант и был успешно использован.

Фибоначчиева куча: как это работает

Нечасто встретишь такой качественный разбор работы чего-либо. Вот тут очень хорошо все разжевано:

http://cppalgo.blogspot.com/2011/11/fibonacci-heap.html.

http://neerc.ifmo.ru/wiki/index.php?title=Биномиальная Куча

http://habrahabr.ru/post/135232/

Читать много, но интересно. Для большего понимания тут есть рисунок.

Timeout serial on boost

Простой класс для работы с последовательным портом ("COM2" например).

#include <exception>

#include <boost/asio.hpp>

#include <boost/asio/serial_port.hpp>

#include <boost/date_time/posix_time/posix_time.hpp>

#include <boost/bind.hpp>

#include <boost/utility.hpp>

#include <boost/algorithm/string.hpp>

namespace SerialPort  

{

    class SerialException : public std::exception {
    public:
        SerialException(const std::string & msg = "SerialException") : std::exception(), m_what(msg)
        {
        }
        ~SerialException() throw() {}
        const char * what() const throw() { return m_what.c_str(); }
    private:
        const std::string m_what;
    };

    class SerialTimeoutException : public SerialException {
    public:
        SerialTimeoutException(const std::string & msg = "SerialTimeoutException") : SerialException(msg)
        {
        }
    }; 

    namespace ba=boost::asio;

    class TimeoutSerialPortBoost {

    public:

        TimeoutSerialPortBoost() : m_io(), m_port(m_io), m_timer(m_io)

        {

        }

        void open(

                const std::string & devname,

                const size_t baud_rate,

                const size_t timeout_ms,

                const size_t char_size,

                const ba::serial_port_base::parity parity_opt,

                const ba::serial_port_base::stop_bits stop_bits_opt

                )

        {

            //

            m_port.open(devname);

            m_port.set_option(ba::serial_port_base::baud_rate(baud_rate));

            m_timeout = boost::posix_time::milliseconds(timeout_ms);  

            m_port.set_option(ba::serial_port_base::character_size(char_size)); 

            // none, odd, even

            m_port.set_option(parity_opt);

            //none, software, hardware

            m_port.set_option(ba::serial_port_base::flow_control(ba::serial_port_base::flow_control::none));

            //one, onepointfive, two

            m_port.set_option(stop_bits_opt);

        }

        void write(const unsigned char *data, const size_t size)

        {

            ba::write(m_port, ba::buffer(data, size));

        }

        void read(unsigned char * data, const size_t size)

        {

            if(m_timeout != boost::posix_time::seconds(0)) //If timeout is set, start timer

            {

                m_timer.expires_from_now(m_timeout);

                m_timer.async_wait(boost::bind(&TimeoutSerialPortBoost::timeout_expired,

                                               this,

                                               ba::placeholders::error

                                               )

                                   );

            }

            ba::async_read(m_port,

                           ba::buffer(data, size),

                           boost::bind(&TimeoutSerialPortBoost::read_completed,

                                       this,

                                       ba::placeholders::error,

                                       ba::placeholders::bytes_transferred

                                       )

                           );

            m_read_result = resultInProgress;

            m_bytes_transferred = 0;

            while(true)

            {

                m_io.run_one();// 

                switch(m_read_result)

                {

                case resultSuccess:

                    m_timer.cancel();

                    return;

                case resultTimeoutExpired:

                    m_port.cancel();

                    throw SerialTimeoutException("Error in TimeutSerialBoost::read, timeout expired");

                case resultError:

                    m_timer.cancel();

                    m_port.cancel();

                    throw SerialException("Error in TimeutSerialBoost::read, read error");

                default: //if resultInProgress remain in the loop

                    break;

                }

            }

        }

    private:

        void read_completed(const boost::system::error_code& error, const size_t transferred)

        {

            if(error)

            {

                if(error != ba::error::operation_aborted)

                    m_read_result = resultError;

            }

            else

            {

                if(m_read_result != resultInProgress)

                    return;

                m_read_result = resultSuccess;

                this->m_bytes_transferred = transferred;

            }

        }

        void timeout_expired(const boost::system::error_code & error)

        {

            if(m_read_result != resultInProgress)

                return;

            if(error != ba::error::operation_aborted)

                m_read_result = resultTimeoutExpired;

        }

    private:

        enum ReadResult

        {

            resultInProgress = 0,

            resultSuccess = 1,

            resultError = 2,

            resultTimeoutExpired = 3

        };

    private:

        ba::io_service m_io;

        ba::serial_port m_port;

        ba::deadline_timer m_timer;

        boost::posix_time::time_duration m_timeout;

        ReadResult m_read_result;

        size_t m_bytes_transferred;

    };

}

Объяснять тут особо нечего, кроме, разве что функции TimeoutSerialPortBoost::read(), которая хорошо демонстрирует сущность отношений между объектами собственно последовательного порта и т.н. сервиса ввода-вывода. Суть в следующем. Если мы хотим что-то прочитать из последовательного порта, то мы делаем это не напрямую (вызывая функции чтения класса порта), а посредством сервиса ввода-вывода. Зачем? Потому что мы не можем напрямую указать последовательному порту, что "надо прочитать некоторые данные, но ждать не более n миллисекунд". Для этого у нас есть сервис. Он "знает" об обоих объектах (таймер и последовательный порт) и мы будет вызывать его функцию run_one() до тех пор, пока не произойдет какое-то событие - чтение данных или истечет таймаут. Вызов run_one(). Фактически, вызов функции run_one() блокирует выполнение программы до тех пор, пока не произойдет какое-нибудь событие. После каждого вызова проверяется значение переменной состояния. Переменная состояния m_read_result может быть изменена обработчикам чтения или обработчиком таймаута (одно из этих событий обязательно произойдет после первого вызова run_one) и мы всегда будем знать, как у нас дела.
Естественно, мы можем напрямую вызывать функции чтения класса serial_port, но это будет во 1-х, идеологически неправильно, а во 2-х, мы не сможем завершать ожидание байт по истечению таймаута.

Почему все так сложно и громоздко? Почему было не сделать так, как это осуществлено, например, в WinAPI, когда при вызове CreateFile() мы сразу указываем все параметры, в том числе и таймаут? Потому, что так это и есть на самом деле. То есть в внутри WinAPI происходит ровно то же самое, что мы сделали тут. То есть устанавливается таймер и система ждет, какое событие произойдет раньше - истечение таймаута или чтение байтов. Такова идеология создателей boost - они не ограждают программиста от труда понимать как все работает на самом деле и потому над некоторыми вещами действительно придется хорошенько подумать. Хорошо бы примеров побольше давали, потому что данный исходник был сделан после изучения исходников другого программиста (TimeoutSerial.h,  TimeoutSerial.cpp). Было бы очень удобно, если бы такие хорошие примеры находились прямо на boost.org.

char to TCHAR

Очень популярная задача при использовании WinAPI и предлагается куча решений. Но большинство из них почему-то сходятся к выделению массива TCHAR в куче с помощью new либо использованию массива фиксированной длины. Мне больше всего нравится такое решение:

            //исходная строка

            const std::string dev_name = "COM4";

            //создаем вектор нужной длины с учетом терминального нуля в конце
            std::vector<TCHAR> tchar_dev_name(dev_name.size() + 1);

            //важно! используем std::copy(), а не memcpy()

            std::copy(dev_name.begin(), dev_name.end(), tchar_dev_name.begin());

            //нулевой символ в конце обязателен 

            tchar_dev_name[tchar_dev_name.size() - 1] = 0;

            //дальше все как обычно

            m_port = CreateFile(

                    &tchar_dev_name[0],

                    GENERIC_READ | GENERIC_WRITE, 

                    0, 

                    NULL, 

                    OPEN_EXISTING, 

                    0, 

                    NULL 

                    ); 

Не надо выделять память руками и освобождать ее тоже не надо - за нас все делает STL. Уже на пару строчек меньше. И надежнее. Почему используем std::copy() вместо memcpy()? Потому что TCHAR, вообще говоря, это не тип, а макрос, который определяет тип (char или wchar_t) в зависимости от. То есть, в общем случае нельзя утверждать, что sizeof(char)==sizeof(wchar_t), а значит и memcpy() нам тоже не подходит и вместо него мы используем функцию std::copy(), которая копирует символы из одной строки в другую поштучно.

Исключение надо всегда перехватывать по ссылке!

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

#include <exception>

#include <string>

#include <iostream>

class MyException : public std::exception {

public:

    MyException(const std::string & msg)

        : std::exception(), m_msg(msg)

    {

    }

    const char * what() const throw()

    {

        return m_msg.c_str();

    }

    ~MyException() throw()

    {

    }

private:

    std::string m_msg;

};

int main()

{

    try

    {

        throw MyException("MyException");

    }

    catch(std::exception e) //вот тут происходит т.н. "расщепление"

    {

        std::cout << e.what();

    }

    return 0;

}

Этот код выведет "std::exception". Это происходит потому, что в строке с инструкцией catch(std::exception e) происходит преобразование к значению базового типа (т.н. "срезка" или "расщепление"), в котором нет строки-члена  m_msg, который хранит сообщение об ошибке. То есть, до блока обработки долетает совсем не то, что было сгенерировано внутри try. И выводится именно то, что выводится в std::exception::what(), а не MyException::what(). Чтобы получать правильный тип исключения, надо получать значение по ссылке. То есть заменить "catch(std::exception e)" на "catch(std::exception & e)". Тогда не происходит преобразования к значению класса базового типа и корректно работает механизм полиморфизма. Как с указателями. И в результате мы получаем именно тот объект-исключение, который был сгенерирован в блоке try.
На самом деле не вижу ни одной причины, чтобы не использовать перехват исключений по ссылке всегда. Перехват по значению может привести к описанным выше проблемам, а перехват по указателю обычно ведет к необходимости удалять объект исключения после его  обработки. А это лишнее действие, которое можно и забыть сделать. Поэтому проще всего перехватывать исключения по ссылке и не забивать себе голову лишними действиями. Ну а генерировать исключения надо, в таком случае, всегда по значению.

Любоыптное поведение константной ссылки в C++

Очень любопытно поведение константных ссылок в C++. Потому что константная ссылка - это не просто указатель. Если присвоить ей значение временного объекта, то он будет существовать столько же, сколько и константная ссылка. Это, как ни странно, записано в стандарте. О чем я прочитал в блоге алены-цпп. Но это еще не все:

class SomeClass {

public:

    SomeClass(const std::string & name)  

      : obj_name(name)  

    { 

       std::cout << "object \"" << obj_name.c_str() << "\" created" << std::endl; 

    }

    ~SomeClass()  

    { 

       std::cout << "object \"" << obj_name.c_str() << "\" destroyed" << std::endl;  

    }

private:

    std::string obj_name;

};

SomeClass get_some_class_heap() {

    return *(new SomeClass("HeapObjectFromFunc"));

}

SomeClass get_some_class_val() {

    return SomeClass("ValueObjFromFunc");

}

void test_const_ref_func() {     
    const SomeClass & value_obj_from_func_ref(get_some_class_val()); // 1    

    const SomeClass & heap_obj_from_func_ref(get_some_class_heap()); // 2    

    const SomeClass & heap_obj_ref(*(new SomeClass("HeapObj"))); // 3   
    // 

    std::cout << "end of const_ref_func()" << std::endl;

}

int main(int argc, char *argv[])

{  

    test_const_ref_func();

}

Получаем вот такой вот вывод:

object "HeapObjectFromFunc" created
object "ValueObjFromFunc" created
object "HeapObj" created
end of const_ref_func()
object "ValueObjFromFunc" destroyed
object "HeapObjectFromFunc" destroyed

Первый случай - все понятно: константная ссылка получает временный value-объект и "держит" его, не давая ему умереть, пока сама не выйдет за пределы области видимости функции test_const_ref_func().
Второй случай - то же самое, но возвращается ссылка не на value-объект, а на объект, созданный в куче. Казалось бы - вот они, умные указатели! Но... см.третий случай.
Третий случай - умный указатель получает ссылку на тут же динамически созданный объект. Разумеется, он не удаляет объект после того, как выходит за пределы видимости. Если бы было иначе - отладка программ на C++ была бы еще более непредсказуемой и сложной задачей, чем даже сейчас. И, кстати, поведение компилятора в этом плане во втором случае тоже вызывает много вопросов.

Бьярн страуструп про необходимость сборщика мусора в C++

Прочитал статью на хабре про недавнюю конференцию по C++11 - новому стандарту языка C++. Бьярн Страуструп очень тонко прошелся по всем языкам с автоматическим управлением памятью:

“But I think that Garbage Collection is not as critical for C++ as it is for many of the other languages. We just don’t generate that much garbage”

Что в вольном изложении можно перевести  так: "Мы не так много срем, чтобы нам понадобился сборщик мусора".

Компилирование библиотек boost

У меня есть QtCtreator под Windows и необходимо скомпилировать библиотеки буста. Сначала скачиваем последнюю версию исходников буста. На текущий момент это версия 1.48.
1) Распаковываем архив (я распаковал его на диск C:\ ).
2) Создаем и устанавливаем следующие переменные окружения:
      BOOST_ROOT="C:\boost_1_48_0"
      BOOST_BUILD_PATH="%BOOST_ROOT%\tools\build\v2\engine"
3) Компилируем утилиту bjam.exe, которая потом поможет нам скомпилировать сам буст. Для этого в командной строке меняем текущий каталог на "C:\boost_1_48_0\tools\build\v2\engine", после чего компилируем bjam, вызывая из командной строки скрипт "build.bat" с параметром "mingw":
      >  build.bat  mingw
Варианты параметров запуска командного фала для других компиляторов можно найти в самом командном файле в комментариях: "Toolsets supported by this script are: borland, como, gcc, gcc-nocygwin,  intel-win32, metrowerks, mingw, msvc, vc7, vc8, vc9, vc10".
Итак, теперь в результате у нас есть папка "C:\boost_1_48_0\tools\build\v2\engine\bin.ntx86", а в ней два файла:  "b2.exe" и "bjam.exe". Скопируем их в "C:\Windows\System32". Теперь их можно вызывать из командной строки.
4) Собственно компиляция библиотек boost. Для этого в командной строке переходим в в папку "C:\boost_1_48_0", после чего выполняем команду компиляции библиотек буста:
    >  bjam --toolset=gcc link=static stage

Вот и все.

Ссылки по теме:
Mismatched versions of Boost.Build engine and core
Building Boost for static linking (MinGW)
Сборка библиотеки Boost

Подсчет количества ненулевых бит с помощью "магических чисел"

Подсчёт количества ненулевых бит в числе v за log2(v) проходов (на примере 8-битного числа):
    v = (v & 0x55) + ((v >> 1) & 0x55);
    v = (v & 0x33) + ((v >> 2) & 0x33);
    return (v & 0x0f) + ((v >> 4) & 0x0f);

Число разбивается на группы бит одной длины (сперва по одному биту). Затем значения соседних пар одновременно складываются и сохраняются в новых группах в два раза большей длины до тех пор, пока не будут сложены половинки числа.
Поскольку длина суммы двух чисел равна длине большего числа с битом для переноса, поэтому для каждой группы в маске групп достаточно иметь единиц не больше номера шага (то есть 1+log2 от длины группы). Hапример, для подсчёта единичных бит в 32-битном числе (с оптимизацией):


#define g21 0x55555555ul // = 0101_0101_0101_0101_0101_0101_0101_0101
#define g22 0x33333333ul // = 0011_0011_0011_0011_0011_0011_0011_0011
#define g23 0x0f0f0f0ful // = 0000_1111_0000_1111_0000_1111_0000_1111


v = (v & g21) + ((v >> 1) & g21);
v = (v & g22) + ((v >> 2) & g22);
v = (v + (v >> 4)) & g23;
return (v + (v >> 8) + (v >> 16) + (v >> 24)) & 0x3f;


Для сокращения количества шагов можно суммировать тройки и т.д.:

#define g31 0x49249249ul // = 0100_1001_0010_0100_1001_0010_0100_1001
#define g32 0x381c0e07ul // = 0011_1000_0001_1100_0000_1110_0000_0111


v = (v & g31) + ((v >> 1) & g31) + ((v >> 2) & g31);
v = ((v + (v >> 3)) & g32) + ((v >> 6) & g32);
return (v + (v >> 9) + (v >> 18) + (v >> 27)) & 0x3f;

Оригинальный пост (датирован 2003-м годом)  находится здесь. А у себя я его продублировал на тот случай, если вдруг что-то случится с этой веткой форума.

Крайне полезные статьи

Приведу список отличных статей, которые очень сильно помогли мне:

Перевод статьи про d-указатели (aka pimpl, чеширский кот и т.п.). Рассказано, что такое д-указатели, зачем они нужны, как их использование помогает соблюдению бинарной совместимости, как увеличивается производительность при перемещении pimpl-объектов и многое другое. Попутно рассказывается, что такое бинарная совместимость вообще, зачем она нужна и для чего в программах на C++ крайне важно в целях бинарной совместимости все детали реализации писать в cpp-файлах, оставляя в h-файлах только самый необходимый минимум объявлений.

Использование dll в Visual C++. Рассказывается, как подключать dll-библиотеки к программе. Рассматривается три способа использования библиотек: явное подключение, неявное подключение (с использованием lib-файлов) и отложенное подключение библиотек. Описывается, что такое lib-файл и для чего он нужен. Описываются особенности использования библиотечных классов, переменных и функций.

Threading without headache. Описывается, как в Qt писать многопоточные приложения без использования таких базовых примитивов, как, например, мьютексы. Если кто не читал - обязательно прочитать. Я был так впечатлен, что тут же за пару дней переделал свой проект, полностью убрав из него мьютексы. Все вызовы методов интерфейсов заменил механизмом сигналов и слотов. Можно сказать, что я вообще абстрагировался от того факта, что приложение многопоточное- за меня все делает великолепный фреймворк Qt. Описывается, зачем нужна функция moveToThread(). Также советую почитать дополнительно про отправку/прием событий QEvent - иногда вместо механизма сигналов и слотов может быть удобнее использовать сообщения. Еще советую почитать это

Виртуальное наследование. В моей практике еще не попадался случай, когда в этом бы возникла необходимость. Вообще довольно сложно представить такой случай, если честно. Но на собеседованиях этот вопрос почти всегда задают, так что читать в обязательном порядке.

Подсчет количества битов в числе. Тут описан наиболее шаманский способ "магических чисел". Остальные способы (последовательный сдвиг и предварительный подсчет) слишком тривиальны, чтобы давать по ним ссылки.

Статья про boost::bind. Большая и полезная для понимания внутреннего устройства буста статья.