How to use vector and structure?
I need to count letters from a string, sort them by count and cout
. For this I am trying to use vector
and struct
. Here is part of my code, but it doesn't work 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 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;
}
In this code, I have two parts that I don't know how to do:
most_frequent[int_char]++; <-- I want to do something like this, but it not working
and
for (vector<int_pair>::iterator it = most_frequent.begin(); it != most_frequent.end(); ++it) <-- is this call correct?
Perhaps you can see any other errors and possible problems in this code.
source to share
I would use std :: map to figure out the frequency of each letter, and then copy it into a multimap, 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;
}
};
source to share
When accessing a container with a key ( vector
indexed with an integer, which is the "key" in your case), you don't need to store the key in the container's value field again.
This way you don't need yours struct
as you only need a value field and can store the number of occurrences directly in the vector.
The idea is to fill the vector with 256 integers at the beginning, all initialized to zero. Then use the vector pointer as your "key" (character code) to access the elements (number of occurrences).
This will result in 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]++;
}
After filling the vector, you can find the maximum value (not only the value, but also the key in which it is stored) with 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);
Here's your example with changes (only print the most frequent character, here is a space so you don't see it): http://ideone.com/94GfZz
You can sort this vector, however, you will of course lose the key as the elements will move and change their indices. There is a nice trick for handling statistics: use a reverse (multi) map (key, value inverse):
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 need to figure out now is how to access and process the data on this card. The quirky thing about this inverted map is that it is now automatically sorted by occurrence, as maps are sorted by key.
source to share
I find it more natural to use a container to store each character. The symbol is the key of the card, its amount of occurrence is the value of the card. It is easy to scan the original line and build this map with and to increase the number of occurrences. std::map
std::map::operator[]
++
Then you can build a second card from the above card with the key and value inverted: so that this card will be sorted by occurrence and then you can print this second card. Note that you must use std::multimap
both this second card, as its keys (i.e. occurrences) can be repeated.
Below is a sample code (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 value (i.e. char's
// occurrences), which is new map 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 space characters, you can filter that out easily.
Note that using std::map
/ std::multimap
will also scale better than std::vector
for non-ASCII characters, for example. if you are using Unicode UTF-32 (since there are much more Unicode characters than just 256).
source to share