Непонятное поведение std::next_permutation с std::wstring
Учитывая эту программу для работы с Unicode, я нашел результаты, которые не имеют для меня смысла:
#include <iostream>
#include <algorithm>
#include <cassert>
int main() {
std::locale::global(std::locale(""));
std::wcout.imbue(std::locale());
std::wstring unicodeString = L"⊓⊔⊏"; // FAIL!
// 6 permutations as expected
// std::wstring unicodeString = L"abc"; // OK
size_t permutations_count = 0;
// Print the Unicode string
do {
std::wcout << unicodeString << std::endl;
permutations_count++;
} while (std::next_permutation(unicodeString.begin(),unicodeString.end()));
std::wcout << "sizeof char " << sizeof(char) << std::endl;
std::wcout << "sizeof wchar_t " << sizeof(wchar_t) << std::endl;
std::wcout << "string size: " << unicodeString.size() << std::endl;
std::wcout << "permutations: " << permutations_count << std::endl;
assert(permutations_count == 6);
return 0;
}
Возврат GCC 11.4.0 и Clang 19.0.0git (g++ -std=c++17 -Wall -Wextra, clang++ -std=c++17 -Wall -Wextra):
⊓⊔⊏
⊔⊏⊓
⊔⊓⊏
sizeof char 1
sizeof wchar_t 4
string size: 3
permutations: 3
a.out: /mnt/c/Workspace/test.cc:26: int main(): Assertion `permutations_count == 6' failed.
Aborted
Который по какой-то причине не напечатал все 3! == 6 перестановки "⊓⊔⊏". Однако он работает правильно, когда строка «abc» передается в next_permutation, что указывает на неправильную обработку многобайтовых значений моим кодом.
MSVC CL 19.40.33811 (cl /EHsc /std:c++17) также выводит неясные результаты,
... thousands of lines cut ...
""SSâS?ââ
""SSâSâ?â
""SSâSââ?
""SSS?âââ
""SSSâ?ââ
""SSSââ?â
""SSSâââ?
sizeof char 1
sizeof wchar_t 2
string size: 9
permutations: 6,725
Assertion failed: permutations_count == 6, file test.cc, line 26
Существуют различия в том, что наивно кажется совместимым со стандартами и переносимым программным обеспечением между поставщиками, и ни одно из этих действий не имеет для меня смысла. Другие примечания,
Мой исходный файл закодирован с использованием UTF-8. Я пробовал другие способы написания
unicodeString, напримерstd::string unicodeString = u8"⊓⊔⊏";, но это также дает неожиданные результаты.Я предполагаю, что
wstringпредназначен для работы с «широкими символами» (2 байта сcl, 4 сg++/clang++), а не с байтами, как, по-видимому, интерфейс, используемый универсальными алгоритмами.
Пожалуйста, может кто-нибудь объяснить, что здесь делается неправильно?
Какова локаль системы? ИЛИ в какой локали вы ожидаете такого поведения.
Ответы 2
next_permutation перебирает все перестановки только в том случае, если входные данные были отсортированы, но ⊓⊔⊏ не отсортированы. Вот почему GCC 11.4.0 и Clang 19.0.0 не выдают ожидаемых результатов.
MSVC CL 19.40.33811 — более сложный случай. Единственный способ, по которому я могу предположить, что в итоге получилось 9 символов, заключается в том, что ваш cpp файл имеет кодировку UTF-8, и, таким образом, строка сохраняется как байты 0xe2 0x8a 0x93 0xe2 0x8a 0x94 0xe2 0x8a 0x8f, но затем компилятор интерпретировал файл как какую-то другую кодовую страницу (вероятно, CP-1252 ), поэтому интерпретировал каждый байт как отдельный символ, а затем сохранял их как отдельные символы wchar_t в кодировке UTF-16 wstring. Это распространенная ошибка, называемая Моджибаке. Строка из 9 символов приведет к 362 880 перестановкам... за исключением того, что ваш ввод не отсортирован.
По касательной к этому, когда он записывает байты в терминал, терминал интерпретирует эти байты как некоторую другую кодировку (вероятно, CP-1252) и, таким образом, отображает в терминале неправильные символы.
Сноска: next_permutation четко определена для любого ввода и просто переходит к следующему вводу в отсортированном порядке. Когда следующий ввод будет «меньше», чем текущее состояние, он возвращает false. Следовательно: если вы хотите легко перебирать все перестановки, вам следует начать с отсортированного состояния и повторять до тех пор, пока оно не вернется false. Но next_permutation не ограничивается этим случаем, и его можно использовать и другими интересными способами.
Спасибо за объяснение, я многому научился!
@user26340612 @user26340612 Функции алгоритма гарантированно будут работать, если они вызваны правильно и соблюдены предварительные условия (в этом случае данные должны быть отсортированы). Все, что next_permutation видит, — это набор T и запускает алгоритм. Требование к next_permutation использовать отсортированные данные здесь. Несортированные данные приводят к неопределенному поведению. Посмотрите пункты 1) и 2) по ссылке.
next_permutation only iterates through all permutations if the input was sorted - это плохое утверждение. Вы можете начать итерацию с любой перестановки, и функция вернет false, когда диапазон будет сохранен после next_permutation.
@PaulMcKenzie Это не приводит к неопределенному поведению. Однако next_permutation остановится (вернёт false), когда будет достигнута последняя перестановка в лексикографическом порядке.
@MarekR: Технически то, что я написал, было правильным упрощением. Вы правы, мне следовало уточнить это в ответе и добавить это в качестве сноски.
Этот код имеет несколько проблем.
- Вы неправильно настраиваете локаль. Подробности см. в другом моем ответе — обратите внимание на все 5 пунктов о подводных камнях кодирования. На других платформах/копиляторах везде предполагается UTF-8, поэтому эта проблема возникает не так часто. Чтобы это исправить, добавьте флаг компиляции
/utf-8и в коде должно быть:
int main() {
#if 0
std::locale::global(std::locale{"en_US.UTF-8"}); // replace en_US with your language
#else
// or use system language settings and enforce UTF-8:
std::locale::global(std::locale{std::locale{""}, "en_US.UTF-8", std::locale::ctype});
#endif
std::wcout.imbue(std::locale{""});
После этого печать на MSVC будет работать (при условии, что ваша кодовая страница поддерживает эти символы).
- Другая проблема заключается в том, что символы в исходной строке не отсортированы, поэтому итерация по всем перестановкам начинается с середины. Демо. (это описано в другом ответе).
3. Если вы ожидаете, что локаль повлияет на порядок символов. Затем посмотрите документацию по оператору less: - моя ошибка: оператор < less для std::wstring не используется.
Соответствующее сравнение выполняется на индивидуальном уровне wchar_t, без использования std::basic_stringoperator<. Для std::wstring это не имеет значения, поскольку std::char_traits<wchar_t> функции-члены eq и lt должны вести себя идентично встроенным == и < в wchar_t. Однако, если бы это была какая-то другая std::basic_string специализация, разница могла бы быть, потому что соответствующая char_trait может переупорядочивать символы или считать некоторые из них равными.
Или по-другому: даже при нестандартной std::char_traits специализации std::next_permutation строка все равно не будет локально-зависимой, а вместо этого будет упорядочена по значению единиц кода.
Помимо проблемы с заказом и проблемы с исходной кодировкой: это не относится к вашему конкретному примеру, но имейте в виду, что все функции стандартной библиотеки, включая
next_permutation, будут действовать на отдельные единицы кода, а не на кодовые точки или символы в каком-либо смысле. Итак, если вы попытаетесь, например, переставить😀, вы получите две последовательности в MSVC, потому что😀занимает две кодовые единицы UTF-16, причем вторая последовательность будет недействительной UTF-16. Аналогично, если у вас есть, например.äв качестве последовательности, в зависимости от нормализации, это может быть одна или две кодовые точки (и единицы) с бессмысленной перестановкой.