从C++字符串中删除不允许的字符的最优雅和有效的方法？

Question

我正在使用C++ 11,我想知道处理现有C++字符串最优雅的是什么,它只包含下面这些有效字符.效率也是一个问题,但最重要的是寻找优雅.

"0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_-";

谢谢你,维吉尔.

Answer 1

这是我的去处:

void removeDisallowed(std::string& in) {
    static const std::string allowed = "01234...";
    in.erase(
        std::remove_if(in.begin(), in.end(), [&](const char c) {
            return allowed.find(c) == std::string::npos;
        }),
        in.end());
}

如果你想提高效率,可以制作一套:

std::unordered_set<char> allowedSet(allowed.begin(), allowed.end());

并将支票更改为:

return !allowedSet.count(c);

[更新]基于很多好的评论和答案,我建议只写一个:

template <typename F>
void erase_if(std::string& in, F func) {
    in.erase(std::remove_if(in.begin(), in.end(), func));
}

然后实际尝试运行它与所有各种提议的funcs,并看看哪一个最适合您的用例.这对Dietmar的答案不起作用,所以你必须单独尝试一下,但它们可能都值得一试.

Answer 2

似乎最优雅的方法是使用正则表达式(注意括号方括号):

std::regex const filter("[^0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_-]");
str = std::regex_replace(str, filter, "");

在关于性能的评论之后,我编写了一个快速基准测试,在github上进行了检查.它比较了一些建议.以下是使用高优化选项的最新版gcc和clang在MacOS笔记本上运行的结果的摘要.显示的数字是以μs为单位处理冗长文本文档所用的时间:

benchmark                         gcc      clang
regex (build                     186131    552697
regex (prebuild)                 177959    566353
use_remove_if_str_find            44802     40644
use_remove_if_find                88377    123237
use_remove_if_binary_search       54091     64065
use_remove_if_ctype               13818     12901
use_remove_if_hash                81341     58582
use_remove_if_table                9033     10203

前两个基准测试使用上面发布的正则表达式方法,而其他基准测试使用Barrystd::remove_if()使用不同的方法在lambda中实现谓词.为了澄清名称,概述了所做的事情(在lambda内部,erase()根据需要结合使用等):

1. 正则表达式(构建): text = std::regex_replace(text, std::regex("[^" + allowed + "]"), "")
2. 正则表达式(prebuild):( text = std::regex_replace(text, filter, "")构建正则表达式在时间之外)
3. remove_if str find: std::remove_if(... a.find(c))
4. remove_if find: std::remove_if(... std::find(a.begin(), a.end(), c) == a.end())
5. remove_if binary_search: std::remove_if(... std::binary_search(a.begin(), a.end(), c))
6. remove_if ctype: std::remove_if(... isalnum(c) || c == '-' || c == '_')
7. remove_if hash: std::remove_if(... unordered_set.count(c))
8. remove_if表: std::remove_if(... table[c])

有关详细信息,请查看源代码.

Answer 3

这可能是简单的,但我会考虑使用适合几个缓存行的常量时间查找表.

void remove_disallowed(std::string &str)
{
    static const char disallowed[] = {
        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1,
        1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0,
        1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1,
        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
    };
    str.erase(std::remove_if(str.begin(), str.end(), [&](char c) {
        return disallowed[static_cast<unsigned char>(c)];
    }), str.end());
}