Re: C++ solution for K & R(2nd Ed) Ex.6-4 - better solution needed
Barry wrote:
subramanian100in@yahoo.com, India wrote:
First I express my thanks to all of you for replying.
Looks like, some of you have suggested map data structure. This cannot
be used because it sorts the input based on string which is the key.
But the input words should not be sorted. Their order should be
retained as they appear in the input. Later, they should be sorted
based on frequency of their occurrence.
Let me put the logic that I have used, in words.
Instead of going through the code, kindly go through this and give me
your feedback as help.
I create "vector<string> unique_words;" to store each input word as it
arrives(after checking if it is already not found in this vector). I
also create "vector< pair<int, string> > v;" along with the above
vector<string>. Whenever a word arrives, first it is stored in
vector<string> if it is a new word and in this case, make_pair(1,
word) is stored in vector<pair<int,string>>. If the word has been
previously stored, then its count is incremented in
vector<pair<int,string>>. After reading all words, I do
sort(v.begin(), v.end(), cmp_fn);
for_each(v.begin(), v.end(), print);
The disadvantage is the addition of two global functions cmp_fn and
print. There can be other disadvantages also.
I think you can wrap them up,
You can check this out:
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
class AssocVector
{
public:
typedef std::vector<std::pair<int, std::string> > ContainerType;
typedef ContainerType::iterator Iterator;
typedef ContainerType::const_iterator ConstIterator;
public:
void Insert(std::string const& word)
{
bool found = false;
Iterator iter = c.begin();
for (; iter != c.end(); ++iter)
{
if (iter->second == word)
{
++(iter->first);
found = true;
break;
}
}
if (found && iter != c.begin())
{
for (; iter != c.begin(); --iter)
{
Iterator prev = iter;
--prev;
if (prev->first < iter->first)
std::iter_swap(prev, iter);
else
break;
}
}
if (!found)
c.push_back(std::make_pair(1, word));
}
Wow: is that bubble sort on the fly?
Anyway, I don't like the mix of responsibilities that issues from putting
the increment of the frequency count within the search loop. Consider:
void Insert(std::string const& word)
{
Iterator iter = c.begin();
while ( iter != c.end() && iter->second != word ) {
++ iter;
}
if ( iter == c.end() ) {
c.push_back(std::make_pair(1, word));
} else {
++ iter->first;
while ( iter != c.begin() ) {
Iterator next = iter;
--iter;
if (iter->first < next->first) {
std::iter_swap(next, iter);
} else {
return;
}
}
}
}
Iterator begin()
{
return c.begin();
}
Iterator end()
{
return c.end();
}
ConstIterator begin() const
{
return c.begin();
}
ConstIterator end() const
{
return c.end();
}
protected:
ContainerType c;
};
struct Printer
{
void operator() (std::pair<int, std::string> const& p) const
{
std::cout << p.first << ' ' << p.second << std::endl;
}
};
int main()
{
AssocVector assocVec;
std::string word;
while (std::cin >> word)
assocVec.Insert(word);
std::for_each (assocVec.begin(), assocVec.end(), (Printer()));
}
I think this is overkill (and inefficient due to the use of bubble sort :-)
Instead, let me suggest some spagetty code (all goes into main):
#include <iostream>
#include <string>
#include <map>
int main ( void ) {
std::string word;
typedef std::map< std::string, unsigned long >
frequency_table;
frequency_table frequency;
// reading and counting:
while ( std::cin >> word ) {
++ frequency[ word ];
}
// reverting and resorting:
typedef std::multimap< unsigned long, std::string >
inverse_table;
inverse_table inverse;
for ( frequency_table::const_iterator iter
= frequency.begin();
iter != frequency.end(); ++ iter ) {
inverse.insert
( inverse_table::value_type
( iter->second, iter->first ) );
}
// output:
for ( inverse_table::const_reverse_iterator iter
= inverse.rbegin();
iter != inverse.rend(); ++ iter ) {
std::cout << iter->second << " " << iter->first << '\n';
}
}
Best
Kai-Uwe Bux