Boost 1.34

Вышла новая версия Boost. Не сказал бы "о, какие там новые вкусности!", а скорее "почему этого до сих пор не было???". Это касается таких вещей как optional, unicode пути для filesystem, for each, typeof, вставка auto_ptr в ptr_containers.

Case-insensitive string comparision

Сортировать строки по алфавиту, не при этому учитывая регистр букв, довольно просто:

std::sort(container.begin(), container.end(), std::locale());

Однако использовать подобный предикат для регистро-независимого сравнения строк не получится: std::collate::compare() возвращает ноль для полностью одинаковых строк (что означает их равенство), но вернет не ноль для одинаковых строк, различающихся регистром (например "hello" и "Hello").

Простой тест, чтобы показать несостоятельность std::collate::compare() (или его обертки в виде std::locale::operator()) для использования в ассоциативных контейнерах:

std::set<std::string, std::locale> s;
s.insert("hello");
s.insert("Hello");
std::cout << s.size(); // выведет 2

Предикат std::locale не считает строки "hello" и "Hello" эквивалентными.

Брутальный подход - перевести строки в верхний регистр и уже тогда сравнивать:

template <class CharType>
void ToUpper(std::basic_string<CharType>& String, const std::locale& Locale)
{
    if (!String.empty())
        std::use_facet< std::ctype<CharType> >(Locale).toupper(&*String.begin(), &*String.begin() + String.size());
}

struct LexicographicalLess
{
    LexicographicalLess(const std::locale& Loc = std::locale()) : Locale(Loc) {}
    std::locale Locale;

    template <typename CharType>
    bool operator()(std::basic_string<CharType> lhs, std::basic_string<CharType> rhs) const
    {
        ToUpper(lhs, Locale);
        ToUpper(rhs, Locale);
        return Locale(lhs, rhs);
    }
};

Такой предикат уже пройдет наш мини-тест.

Однако скорость не впечатлит. В процессе сравнения делаются копии строк, что довольно долго. Особенно учитывая то, что std::basic_string хранит более-менее большие строки в динамической памяти.

Кстати, если предикат нужен только для сравнения строк, а не для сортировки (для сортировки у нас есть std::locale в качестве предиката), строку return Locale(lhs, rhs); можно заменить на более быструю return lhs < rhs;, так как для сравнения нам не важно положение буквы в алфавите, сойдет и ее положение в кодовой таблице.

Увеличить производительность LexicographicalLess можно избавившись от копирования строк:

struct LexicographicalLess
{
    LexicographicalLess(const std::locale& Loc = std::locale()) : Locale(Loc) {}
    std::locale Locale;

    template <typename CharType>
    bool operator()(CharType lhs, CharType rhs) const
    {
        return std::toupper(lhs, Locale) < std::toupper(rhs, Locale);
    }

    template <typename CharType>
    bool operator()(const std::basic_string<CharType>& lhs, const std::basic_string<CharType>& rhs) const
    {
        return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end(), LexicographicalLess(Locale));
    }
};

Еще немного дополнительной производительности мне удалось выжать написав свою версию lexicographical_compare.