这篇文章是检查字符串是否是C++20中回文的置换的后续文章.
那么,有什么新消息?好吧,除了这个程序现在是通用的,并接受了所有string_views的char,char8_t,wchar_t,char16_t和char32_t:
string_utils.h:#ifndef COM_GITHUB_CODERODDE_STRING_UTILS_HPP
#define COM_GITHUB_CODERODDE_STRING_UTILS_HPP
#include <cstddef> // std::size_t
#include <string_view>
#include <unordered_map>
namespace com::github::coderodde::string_utils {
template<typename CharType = char>
bool is_permutation_palindrome(const std::basic_string_view<CharType>& text)
{
std::unordered_map<CharType, std::size_t> counter_map;
for (const auto ch : text)
++counter_map[ch];
std::size_t number_of_odd_chars = 0;
for (const auto& [ch, cnt] : counter_map)
if (cnt % 2 == 1 && ++number_of_odd_chars > 1)
return false;
return true;
}
} // namespace com::github::coderodde::string_utils
#endif // !COM_GITHUB_CODERODDE_STRING_UTILS_HPPmain.cpp:#include "string_utils.h"
#include <iostream>
namespace su = com::github::coderodde::string_utils;
int main() {
std::cout << std::boolalpha;
std::cout << su::is_permutation_palindrome(std::wstring_view(L"")) << "\n";
std::cout << su::is_permutation_palindrome(std::u8string_view(u8"yash")) << "\n";
std::cout << su::is_permutation_palindrome(std::u16string_view(u"vcciv")) << "\n";
std::cout << su::is_permutation_palindrome(std::u32string_view(U"abnnab")) << "\n";
}我想知道如何改进我的解决方案代码。我不太关心表演。
发布于 2021-12-22 16:56:39
没什么可谈的,代码很好。
模板现在不允许直接使用std::string,因为CharType不是自动推导出来的。其他一些可以转换字符串视图的调用现在也被禁止(例如,C字符串)。提供一些使用C字符串和std字符串的重载以方便使用可能是有意义的。
的类型参数
老实说,我不知道是否有人使用它们,但为了完整起见,我将把它留在这里。
我认为直方图计算应与此函数分开。也许拥有一个简单易用的函数是很棒的,但是没有单独的构建块可能会导致问题。
我还没有使用范围,但是如果实际上可以从输入创建另一个视图,即原始的直方图,那么只需应用算法就可以了?这可能解决了@Toby提到的问题,也许忽略的函数可以作为管道的一部分来编写。
这可能使接受任何需要属性的范围类型(预兆概念)变得可行。
发布于 2021-12-22 16:36:42
在英语中,我们通常认为字符串是回文,如果字符串中的字母在两个方向上都是相同的序列:
(例如:“夫人,我是亚当”是一个著名的英文回文。)
这些标准中的第一个相对容易执行。
第二个问题可能会更加困难,因为资本化取决于地区。
第三种方法比较困难,除非我们使用诸如ICU这样的库来分解字符并只保留大写字母。
低级别审查:
count这样的变量。;)&&右侧的副作用很难理解.我可能会选择if ((number_of_odd_chars += cnt % 2) > 1)发布于 2021-12-23 12:50:00
您不太关心性能,但是有一些值得注意的事情,比如对于中长字符串的char,有10种性能的因素。
您仍然使用size_t作为计数器类型。对上一个问题的回答指出,你只需要奇数/偶数,而未签名的环绕则保留了这一点。(真正重要的是,计数中的低位才是最重要的,您不关心从低位执行什么,不管它是否从某种类型的末尾传播出去)。uint_fast8_t,unsigned char,uint8_t,甚至bool都能正常工作。
保持更宽的计数器的一个理由是,如果将直方图部分分解,以便它可以用于其他功能,回文检查将使用它作为助手。
bool将简化检查循环:% 2将通过将增量包装回零来完成。(也可以使用整数类型执行^= 1而不是++。异或加-不带进位。)您甚至可以使用std::count_if来计数非零或奇数元素,或者有保证的0/1元素甚至只对计数进行求和。但一旦你看到第二个奇数就失去了你早早出来的好处。
您还在使用unordered_map,与普通数组(或std::array)相比,对于长度为1024的字符串,char数据要花费性能的10倍。
对于大型输入元素类型,您确实希望使用unordered_map,因此,如果您希望获得窄带类型的性能增益,可以使用模板来选择array<bool, CharType_max + 1>与unordered_map,具体取决于std::numeric_limits<CharType>::digits <= 12或其他方面。(假设bool为1字节,我们最多只能得到一个4kiB的bool数组;但如果CharType实际上是12,则这是一个错误的假设。所以可能只有9或更多。)使用C++11 std::conditional,如下所示
#include <type_traits>
#include <cstdint>
using UCharType = std::make_unsigned<CharType>;
std::conditional<
std::numeric_limits<UCharType>::digits <= 9,
std::array<std::uint_fast8_t, std::numeric_limits<UCharType>::max + 1>,
std::unordered_map<std::uint_fast8_t>
>::type counters;(您可以在返回auto的函数中使用它,返回一个直方图容器,因此仍然可以将直方图从回文检查中分离出来。)
要安全地索引array,索引必须是非负的,因此您也需要使用std::make_unsigned<CharType>。在2's补码系统(就像现在的一切)上,相同宽度的符号和无符号之间的转换是没有操作的,编译器可以自由实现,所以我们总是可以进行转换。
或者,如果使用std::bitset,则可以将2^16位= 2^13字节=8 kiB std::bitset作为本地变量(在堆栈上)。但是,对于短的输入字符串,零位和计数的开销可能比制作一个小unordered_map更糟糕。
对于短字符串,一个小std::bitset实际上值得使用一个短数组,但是字符串长度是一个运行时变量,因此您需要两个版本的函数。
https://codereview.stackexchange.com/questions/272256
复制相似问题