c++ - 给定字符串中每个字符出现了多少

我需要计算每个字符在给定字符串中出现了多少次。我需要在C或C++上执行此操作，我可以使用任何库。问题是我不是C/C++开发人员，所以我不确定我的代码是否最佳。我想获得最佳性能的算法，这是此问题的主要原因。

我目前正在使用以下代码:

using namespace std;
...

char* text;        // some text, may be very long
int text_length;   // I know this value, if it can help

map<char,int> table;
map<char,int>::iterator it;

for(int i = 0; c = text[i]; i++) {
    it = table.find(c);
    if (it2 == table.end()) {
        table[c] = 1;
    } else {
        table[c]++;
    }
}

我可以使用除std::map以外的任何其他结构，但是我不知道哪种结构更好。

谢谢你的帮助!

最佳答案

您正在使用bucket sort做对了。有限宇宙中的元素(例如字符)的计数方法不可能有更快(非并行)的算法。

如果仅使用ASCII字符，则可以使用简单的int table[256]数组来避免C++容器的开销。

使用Duff's device(如今在某些CPU上实际上更慢):

int table[256];
memset(table, 0, sizeof(table));
int iterations = (text_length+7) / 8;
switch(count % 8){
    case 0:      do {    table[ *(text++) ]++;
    case 7:              table[ *(text++) ]++;
    case 6:              table[ *(text++) ]++;
    case 5:              table[ *(text++) ]++;
    case 4:              table[ *(text++) ]++;
    case 3:              table[ *(text++) ]++;
    case 2:              table[ *(text++) ]++;
    case 1:              table[ *(text++) ]++;
                 } while(--iterations > 0);
}

更新:正如MRAB所述，并行处理文本块可能会提高性能。但是请注意，创建线程非常昂贵，因此您应该测量最少的字符数量，这证明了线程创建时间是合理的。