How to use vector and struct?

Question

I need to count letters from the string, sort them by count and cout results. For this purpose I'm trying to use vector and struct. Here is part of my code, but it's not working, because I don't know how to implement something:

#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;
}

At this code I have 2 parts that I don't know how to deal:

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

and

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

Maybe you can see any other mistakes and potential issues at this code.

Answer 1

I find more natural to use a std::map container to store each character occurrences. The character is map's key, its occurrence count is map's value. It's easy to scan the source string and build this map using std::map::operator[], and ++ to increase the occurrence count.

Then, you can build a second map from the above map, with key and value inverted: so this map will be sorted by occurrences, and then you can print this second map. Note that you have to use a std::multimap as this second map, since its keys (i.e. the occurrences) can be repeated.

Sample code follows (I tested it with 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;
}

Output:

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

If you don't want to print the space character occurrences, you can easily filter that out.

Note that using std::map/std::multimap will also scale up better than std::vector for non-ASCII characters, e.g. if you use Unicode UTF-32 (since Unicode characters are much more than just 256).

Answer 2

I would use a std::map to determine the frequency of each letter, then copy that into a multimap while reversing the key and value to get them in order.

#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;
  }
};

Answer 3

When accessing the container with the key (vector is indexed with an integer, which is "the key" in your case), you don't have to store the key in the value field of the container again.

So you don't need your struct since you only need the value field and can can store the number of occurrences directly in the vector.

The idea is to fill the vector with 256 integers in the beginning, all initialized to zero. Then, use the vector index as your "key" (character code) to access the elements (number of occurrences).

This will result in a code similar to this:

// 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]++;  
}   

Once filling of the vector is done, you can find the maximum value (not only the value but also the key where it is stored) using the std::max_element algorithm:

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);

Here is your example with the changes (only printing the most frequent character, here it is the space so you don't see it): http://ideone.com/94GfZz

You can sort this vector, however, you will loose the key of course, since the elements will move and change their indices. There is a nice trick to process statistics like that: Use a reversed (multi)map (key, value reversed):

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));
}

Updated code: http://ideone.com/Ub5rnL

The last thing you should now sort out by yourself is how to access and process the data within this map. The fancy thing about this reversed map is that it is now automatically sorted by occurrence, since maps are sorted by key.

Answer 4

This should do what you need:

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

Yes, it sets the key many times, even though it doesn't need to.