3

我需要计算字符串中的字母，按计数和cout结果对它们进行排序。为此，我正在尝试使用vectorand struct。这是我的代码的一部分，但它不起作用，因为我不知道如何实现某些东西：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

struct int_pair{
     int key;
     int value;
};  

bool sort_by_value(int_pair left, int_pair right){
    return left.value < right.value;
}

int main() {    
    string characters = "aasa asdfs dfh f ukjyhkh k wse f sdf sdfsdf";    
    vector<int_pair> most_frequent;     

    for (string::size_type i = 0; i <= characters.length(); i++) {
        int int_char = (int)characters[i];
        most_frequent[int_char]++; <-- I want to do something like this, but it's not working 
    }

    sort(most_frequent.begin(), most_frequent.end(), sort_by_value);

    for (vector<int_pair>::iterator it = most_frequent.begin(); it != most_frequent.end(); ++it) <-- is this call correct?
        cout << " " << it->key << ":" << it->value << endl;    

    return 0;
}

在这段代码中，我有 2 个部分我不知道如何处理：

most_frequent[int_char]++; <-- I want to do something like this, but it's not working

和

for (vector<int_pair>::iterator it = most_frequent.begin(); it != most_frequent.end(); ++it) <-- is this call correct?

也许您可以在此代码中看到任何其他错误和潜在问题。

4

4 回答 4

4

我会使用 std::map 来确定每个字母的频率，然后将其复制到多重映射中，同时反转键和值以使它们按顺序排列。

#include <iostream>
#include <map>
#include <algorithm>

template<class T, class U>
std::pair<U,T> flip_pair(const std::pair<T,U>& p) {
  return std::make_pair(p.second,p.first);
}

int main(){
  std::string characters = "zxcvopqiuweriuzxchajksdui";
  std::map<char,int> freq;
  std::multimap<int,char> rev_freq;

  // Calculate the frequency of each letter.
  for(char c: characters){
    freq[c]++;
  }

  // Copy the results into a multimap with the key and value flipped 
  std::transform(std::begin(freq), std::end(freq), 
                 std::inserter(rev_freq, rev_freq.begin()), 
                 flip_pair<char,int>);

  // Print out the results in order.
  for(std::pair<int,char> p : rev_freq){
    std::cout << p.first << ": " << p.second << std::endl;
  }
};
于 2013-02-12T19:48:54.347 回答
2

这应该做你需要的：

most_frequent[int_char].key = int_char;
most_frequent[int_char].value++;

是的，它设置了key很多次，即使它不需要。

于 2013-02-12T19:23:05.987 回答
1

使用键访问容器时（vector使用整数索引，在您的情况下为“键”），您不必再次将键存储在容器的值字段中。

所以你不需要你的struct，因为你只需要 value 字段并且可以直接在向量中存储出现的次数。

这个想法是在开始时用 256 个整数填充向量，全部初始化为零。然后，使用向量索引作为“键”（字符代码）来访问元素（出现次数）。

这将产生类似于以下的代码：

// initialize with 256 entries, one for each character:
vector<int> counts(256);

for (string::size_type i = 0; i <= characters.length(); i++) {
    // for each occurrence of a character, increase the value in the vector:
    int int_char = (int)characters[i];
    counts[int_char]++;  
}

向量的填充完成后，您可以使用以下算法找到最大值（不仅是值，还有存储它的键）std::max_element：

vector<int>::iterator most_frequent =
        std::max_element(counts.begin(), counts.end());

// getting the character (index within the container, "key"):
std::cout << (char)(most_frequent - counts.begin());

// the number of occurrences ("value"):
std::cout << (*most_frequent);

这是您的更改示例（仅打印最常见的字符，这里是空格，所以您看不到它）：http: //ideone.com/94GfZz

您可以对该向量进行排序，但是，您当然会丢失密钥，因为元素会移动并更改它们的索引。有一个很好的技巧来处理这样的统计数据：使用反转（多）映射（键，值反转）：

multimap<int,int> keyForOccurrence;
for (vector<int>::iterator i = counts.begin(); i != counts.end(); ++i) {
    int occurrences = *i;
    int character = i - counts.begin();
    keyForOccurrence.insert(std::pair<int,int>(occurrences, character));
}

更新代码：http: //ideone.com/Ub5rnL

您现在应该自己理清的最后一件事是如何访问和处理此地图中的数据。这个反转映射的奇妙之处在于它现在可以按出现次数自动排序，因为映射是按键排序的。

于 2013-02-12T19:21:14.593 回答
1

我发现使用std::map容器来存储每个字符的出现更自然。字符是地图的键，它的出现次数是地图的值。很容易扫描源字符串并使用 构建此映射std::map::operator[]，并++增加出现次数。

然后，您可以从上面的映射构建第二个映射，键和值反转：所以这个映射将按出现次数排序，然后您可以打印第二个映射。请注意，您必须使用 astd::multimap作为第二个映射，因为它的键（即出现次数）可以重复。

示例代码如下（我用 VS2010 SP1/VC10 测试过）：

#include <stddef.h>     // for size_t
#include <algorithm>    // for std::transform
#include <functional>   // for std::greater
#include <iostream>     // for std::cout
#include <iterator>     // for std::inserter
#include <map>          // for std::map, std::multimap
#include <ostream>      // for std::endl
#include <string>       // for std::string
#include <utility>      // for std::pair
using namespace std;

int main() 
{    
    string str = "aasa asdfs dfh f ukjyhkh k wse f sdf sdfsdf";    

    // Build the occurrences map (char -> occurrences)
    map<char, size_t> freq;     
    for (size_t i = 0; i < str.length(); ++i)
        freq[ str[i] ]++;

    // Build a new map from previous map with inverted <key, value> pairs,
    // so this new map will be sorted by old map's value (i.e. char's
    // occurrences), which is new map's key. 
    // Use the std::greater comparator to sort in descending order.
    multimap<size_t, char, greater<size_t>> sorted_freq; 
    transform(
        freq.begin(), freq.end(),                       // source 
        inserter(sorted_freq, sorted_freq.begin()),     // destination
        [](const pair<char, size_t>& p)                 // invert key<->value
        { 
            return pair<size_t, char>(p.second, p.first); 
        }
    );

    // Print results    
    for (auto it = sorted_freq.begin(); it != sorted_freq.end(); ++it)
        cout << it->second << ": " << it->first << endl;
}

输出：

 : 9
s: 7
f: 7
d: 5
a: 4
k: 3
h: 3
u: 1
w: 1
y: 1
j: 1
e: 1

如果您不想打印出现的空格字符，则可以轻松将其过滤掉。

请注意，使用std::map/std::multimap也将比std::vector使用非 ASCII 字符更好地扩展，例如，如果您使用 Unicode UTF-32（因为 Unicode 字符远不止 256 个）。

于 2013-02-12T20:00:19.083 回答