确定字符是否属于一组已知字符的最快方法C++

Question

给定任何字符,我最快的方法是确定该字符是否属于已知字符的集合(不是容器类型).

换句话说,实现条件的最快捷方式是什么:
char c = 'a';
if(c == ch1 || c == ch2 || c == ch3 ...) // Do something...

是否有一个STL容器(我认为它可能是unordered_set？)我可以将该字符作为键传递给它,如果该键存在,它将返回true？

任何具有O(1)查找时间的东西都适合我.

Answer 1

我进一步编写了两个版本,一个基于查找数组,另一个使用底层哈希.

class CharLookup {
public:
  CharLookup(const std::string & set) : lookup(*std::max_element(set.begin(), set.end()) + 1) {
    for ( auto c : set) lookup[c] = true;
  }
  inline bool has(const unsigned char c) const {
    return c > lookup.size() ? false : lookup[c];
  }
private:
  std::vector<bool> lookup;
};

class CharSet {
public:
  CharSet(const std::string & cset) {
    for ( auto c : cset) set.insert(c);
  }
  inline bool has(const unsigned char c) const {
    return set.contains(c);
  }
private:
  QSet<unsigned char> set;
};

然后写了一个小基准,为了比较添加了几个容器.越低越好,数据点是"字符集大小/文本大小":

看起来像短字符集和文本,std::string::find_first_of比使用查找数组更快,甚至更快,但随着测试大小的增加而迅速减少.std::vector<bool>看起来像是"中庸之道",QBitArray可能有一点不同的实现,因为它随着测试大小的增加而提前,最大的测试QVector<bool>是最快的,可能是因为它没有位访问的开销.两个哈希集是接近的,交易地点,最后和最少有std::set.

在i7-3770k Win7 x64盒子上测试,使用MinGW 4.9.1 x32和-O3.

Answer 2

您可以创建一个布尔数组,并true为所需集中的每个字符分配值.例如,如果您想要的集合包括'a', 'd', 'e':

bool array[256] = {false};
array['a'] = true;
array['d'] = true;
array['e'] = true;

然后你可以检查一个角色c:

if (array[c]) ... 

我们也可以为此目的使用bitset:

std::bitset<256> b;
b.set('a');
b.set('d');
b.set('e');

并检查为:

if (b.test(c)) ...