5
\$\begingroup\$

In chapter 3 of Koenig's Accelerated C++, he asks the reader to write a program that performs the task described in the title. At this point, he has only introduced the built-in types, io-types, and vectors, so maps are not allowed. I have written a program that does this, but it is lengthy and requires a number of objects that essentially duplicate existing vectors.

Note: the use of while (cin >> input) will not terminate without an explicit end of line character because of the input type, so a better way to handle the input would be nice to have!

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

using std::cin;
using std::cout;
using std::vector;
using std::string;
using std::endl;

int main ( int argc, char** argv )
{
    string input;
    vector<string> input_arr;

    cout << "Please enter a sentence or list of words, separated by spaces,"
            "and terminated by an EOL character(^d): ";

    while(cin >> input) {
        input_arr.push_back(input);
    }

    sort(input_arr.begin(), input_arr.end());

    vector<string>::size_type len = input_arr.size();

    uint count = 0;
    vector<uint> count_arr;
    string current_string = input_arr[0];
    vector<string> unique_words;
    unique_words.push_back(input_arr[0]);

    for (vector<string>::size_type i = 0; i < len; i++) {

        count_arr.push_back(0);

        if (current_string != input_arr[i]) {
            count +=1;
            current_string = input_arr[i];
            count_arr.push_back(0);
            unique_words.push_back(input_arr[i]);
        }

        count_arr[count] += 1;
    }

    cout << endl;

    for (int j = 0; j <= count; j++) {
        cout << endl << "The word " << unique_words[j] << " occured " << count_arr[j] << " times!";
    }

    cout << endl;

    return 0;
}

In Python, I could achieve this in about 5 lines, for example:

from collections import defaultdict

print("Please enter some text: ")

input_arr = input().split()
d = defaultdict(int)

for k in input_arr:
    d[k] += 1

for key in d.keys():
    print("The word %s occurs %d times!\n" %(key, d[key]))

I am looking for a better way to accomplish this in C++, preferably not using std::maps, since the author probably put this exercise at this stage in the book for a reason. I'm also just learning C++, do I'd appreciate any advice on best practices that I'm violating in this example.

\$\endgroup\$
  • \$\begingroup\$ Python code uses defaultdict... I giess you should not compare the "number of lines" if using std::map in C++ code is not allowed. \$\endgroup\$ – jvb Jun 18 '17 at 9:16
  • \$\begingroup\$ Note the python version is also broken if there is any punctuation in the input then it will affect the word split. \$\endgroup\$ – Martin York Jun 18 '17 at 21:02
4
\$\begingroup\$

Old book:

The age of the book starts to get noticable. May be before 2011 it would be still very effective, but not that much now. May be not in 5 lines, but it is possible write it pretty shortly and neatly in upcoming C++17

#include <iostream>
#include <iterator>
#include <vector>
#include <map>

int main() {
    std::vector<std::string> all_words{std::istream_iterator<std::string>(std::cin),
                                       std::istream_iterator<std::string>()};
    std::map<std::string, std::size_t> unique_words;
    for (const auto& word: all_words)
    {
        ++unique_words[word];
    }

    for (const auto& [word, count]: unique_words)
    {
        std::cout << "word " << word << " occured " << count << " times\n";
    }
}

live demo. Be sure to checkout stdin though, I'm not sure if it is preserved.

Unfortunately there are not many books about recent versions of C++, but knowing the basics should be enough to learn new stuff.

It is also possible to write this without using a map, albeit much more sophisticated:

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

int main()
{
    std::vector<std::string> all_words{std::istream_iterator<std::string>(std::cin),
                                       std::istream_iterator<std::string>()};

    std::sort(all_words.begin(), all_words.end());
    auto first_duplicate_pos = std::unique(all_words.begin(), all_words.end());

    for (auto first = all_words.begin(); first != first_duplicate_pos; ++first)
    {
        auto count = std::count(first_duplicate_pos, all_words.end(), *first);
        ++count; //since occured once in non duplicate part
        std::cout << "word " << *first << " occured " << count << " times\n";
    }
}

The idea here is that after using std::unique<>(), the vector is divided into two ranges: one that has only unique elements, and other has duplicates of unique elements, if any. Now, map is not needed, because in fact the first range is map keys with value equal to 1 (remember that unique counts too). Then we just iterate through the other half searching for one of the keys at a time.

Do note that both versions are invincible to the problem mentioned by @jvb. Thus, it is much better to learn to use standard library first, rather than trying to implement it by hand.

Code Review:

int main ( int argc, char** argv )

No need to have arguments if code is not using it.

sort(input_arr.begin(), input_arr.end());

It would be better to just use std::unique<>() after this and count every occurrence of the elements in range.

Using std::endl should be avoided. It flushes the stream, which is pretty slow. Even Bjarne Stroustrup (original creator of the language) avoids that himself. Instead just use '\n'. std::endl is not only portable way to print a newline, but it also incurs overhead.

for (int j = 0; j <= count; j++)

This lines seems dangerous. I was not able to comprehend the counting logic, but usually when <= count appears, it means getting out of range, which is undefined behavior if it would be the whole vector. I'm pretty sure it should be < count. Anyway, it should've been possible to just use range loop and not worry about the comparison operator.

using std::cin;
using std::cout;
using std::vector;
using std::string;
using std::endl;

This probably didn't buy anything, but instead increased amount of code needed to write. I recommend just sticking with std::. If the namespace is too long, for example std::experimental::filesystem, I recommend doing

namespace exfs = std::experimental::filesystem;

at function scope!

update:

People in the comments mentioned that std::unique<>() is not a partitioning algorithm and the right side of the sequence has unspecified values. It is true. I present another solution, which is standard compliant (I actually went on searching if std::unique<>() always performs swap, but it seems like it is not the case).

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

int main()
{
    std::vector<std::string> all_words(std::istream_iterator<std::string>(std::cin),
                                       {});
    std::sort(all_words.begin(), all_words.end());

    auto first_occurence = all_words.begin();
    while (first_occurence != all_words.end())
    {
        auto next_word_occurence = std::find_if_not(first_occurence, all_words.end(),
                                                    [&first_occurence](const auto& val)
                                                    {
                                                        return val == *first_occurence;
                                                    }
        );

        std::cout << "word " << *first_occurence << " occured "
                  << std::distance(first_occurence, next_word_occurence)
                  << " times\n";
        first_occurence = next_word_occurence;
    }
}

I didn't use std::adjacent_find<>() because it obfuscates the main goal, in my opinion. Using std::find_if_not<>() and its non not version is arguable, but I just went with not version because I usually read on high speeds and sometimes tend to confuse != and ==. Do note that this version is still immune to the point mentioned by @jvb.

\$\endgroup\$
  • 1
    \$\begingroup\$ std::unique is a removal algorithm, not a partitioning algorithm. Since the array is already sorted, usestd::adjacent_find to find the distinct words and their frequency (std::distance on random-access iterators) in linear-time. \$\endgroup\$ – Snowhawk Jun 19 '17 at 18:23
  • \$\begingroup\$ @Snowhawk04, invoking it in a loop look weird. May be negated version would be better? \$\endgroup\$ – Incomputable Jun 19 '17 at 18:30
  • \$\begingroup\$ I do not think it looks "weird", but it does require a C++ implementation from this decade. Also wanted to note that your python translation for defaultdict should be astd::unordered_map. \$\endgroup\$ – Snowhawk Jun 19 '17 at 18:53
  • \$\begingroup\$ The description of std::unique and the way it is used in this answer is complete nonsense. Snowhawk04 is correct that this is not a partitioning. The elements after the new logical end have unspecified values. \$\endgroup\$ – Blastfurnace Jun 21 '17 at 9:58
  • \$\begingroup\$ @Incomputable I don't know if you're going to fix your second example but here is a simple demo that shows std::unique does not do what you think. demo on ideone.com \$\endgroup\$ – Blastfurnace Jun 21 '17 at 12:49
3
\$\begingroup\$

Possible problem/crash here:

vector<string> input_arr;
// some code to read from std::cin and sort
string current_string = input_arr[0];

Let's assume there are no input words (it's user input, after all). While calling std::sort on an empty std::vector is without risk, addressing [0] is illegal (and will lead to unpredictable behavior). There should be a check like

if (!input_arr.empty()) {
  // some for loops
}
\$\endgroup\$
2
\$\begingroup\$

A small point, but I would suggest renaming the variable count to idx. I was finding it hard to follow your code and the word count threw me.

\$\endgroup\$
  • \$\begingroup\$ My compiler complained of signed, unsigned comparison, so you could change the for loop to use a uint: for (uint j = 0; j <= count; j++) \$\endgroup\$ – Will Jun 18 '17 at 19:04
  • \$\begingroup\$ for (uint j = 0; j <= idx; j++) even :) \$\endgroup\$ – Will Jun 18 '17 at 19:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.