10 апреля 2006

Сортировка строк по алфавиту

Задача:
отсортировать контейнер строк по алфавиту.

Попытка 1:
std::sort( container.begin(), container.end() );


Результат получаем сортированный. Но не по алфавиту. std::sort по умолчанию использует для сортировки предикат less<T>, который в свою очередь использует operator<() для типа T, и если у нас строки типа basic_string<Ch>, то operator<() сравнивает посимвольно две строки, считая их значениями типа Ch, а не символами алфавита.

Единственное, кто может знать про понятие "алфавит", это локаль.

Попытка 2:
struct AlphabeticalCompare
{
template <typename CharType>
bool operator ()(const basic_string<CharType> & lhs, const basic_string<CharType> & rhs) const
{
return std::use_facet< std::collate< CharType > >( std::locale() )
.compare( lhs.data(), lhs.data() + lhs.size(),
rhs.data(), rhs.data() + rhs.size() ) == -1;
}
};

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


Вот теперь сортирует как надо.

Используемый мною тест:

#include <iostream>
#include <string>
#include <locale>
#include <vector>
#include <algorithm>

struct AlphabeticalCompare
{
template <typename CharType>
bool operator ()(const basic_string<CharType> & lhs, const basic_string<CharType> & rhs) const
{
return std::use_facet< std::collate< CharType > >( std::locale() )
.compare( lhs.data(), lhs.data() + lhs.size(),
rhs.data(), rhs.data() + rhs.size() ) == -1;
}
};

int main()
{
std::locale::global(std::locale("Ukrainian_Ukraine.1251"));

std::vector< std::wstring > container;

std::wstring s1; s1 += 0x456; // cyrillic "л"
std::wstring s2; s2 += 0x43b; // cyrillic "і"
// 0x456 is greater than 0x43b, but "і" comes before "л" in Ukrainian

container.push_back(s1);
container.push_back(s2);

std::sort(container.begin(), container.end(), AlphabeticalCompare());
std::cout << (container[0] == s1 ? "passed" : "failed") << std::endl;

return 0;
}

Update: хорошая статья на эту тему - How To Do Case-Insensitive String Comparison

2 комментария:

Григорий Зубанков комментирует...

В качестве тренировки - неплохо.

Вообще у std::locale есть очень удобный operator(), которые позволяет сравнивать две строки, задействуя фацет collate.
В результате предикат AlphabeticalCompare становится излишним:

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

Raider комментирует...

Кстати да! Отличный вариант.

Единственный плюс собственного функтора - можно немного соптимизировать, кэшируя результат вызова use_facet<...>() в конструкторе.