7
\$\begingroup\$

How good is this algorithm? Personally I think it's over-complicated and needs some improvement. Should I be using iterators here (I think it's "harder" this way) or indexing? Should I stick with a vector or try other containers? Is a vector (array) of pointers generally better than one of objects?

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
struct StringOccurrence //stores word and number of occurrences
{
    std::string m_str;
    unsigned int m_count;
    StringOccurrence(const char* str, unsigned int count) : m_str(str), m_count(count) {};
};

int main()
{
    std::string path;
    std::cout << "enter file name: " << std::endl;
    std::cin >> path;
    std::ifstream in(path);
    if (!in) //check if file path is valid
    {
        std::cerr << "failed to load file!" << std::endl;
        return -1;
    }

    std::vector<std::string>vec;
    std::string lineBuff;
    while (std::getline(in, lineBuff)) // write multiline text to vector of strings
    {
        vec.push_back(lineBuff);
    }

    std::vector<StringOccurrence*> strOc;
    std::string stringBuff;

    for (auto it = vec.begin(); it < vec.end(); it++) //itterate through each line
    {
        for (auto it2 = it->begin(); it2 < it->end();it2++) //itterate through each letter
        {
            if (*it2 != ' ') //keep adding letters to buffer until space (word)
            {
                stringBuff += *it2;
            }
            if (*it2 == ' ' || it2 + 1 == it->end()) //(need fix?)
            {
                if (*(it2 - 1) == ' ') //check for reccurring spaces so they are not counted as words
                {
                    continue;
                }
                for (auto it3 = strOc.begin(); it3 < strOc.end(); it3++)
                {
                    if (stringBuff == (*it3)->m_str) //if word was found increase count
                    {
                        (*it3)->m_count++;
                        goto end; //skip next step (need fix?)
                    }
                }
                strOc.push_back(new StringOccurrence(stringBuff.c_str(), 1)); //if word was not found add it
            end:
                stringBuff.clear(); //empty buffer for next word
            }
        }
    }

    std::ofstream out("test2.out"); //write to file
    for (auto it = strOc.begin();it < strOc.end();it++)
    {
        out << (*it)->m_str << ' ' << (*it)->m_count << std::endl;
    }

    return 0;
}
\$\endgroup\$
11
\$\begingroup\$

Excessive Memory Use

The first thing you do is read every line into memory:

while (std::getline(in, lineBuff)) // write multiline text to vector of strings
{
    vec.push_back(lineBuff);
}

Why? Do you need to have every line in memory? No. You're just trying to count the words. What if the file was 100TB worth of "all work and no play makes Jack a dull boy"?

Poor Memory Use

std::vector<StringOccurrence*> strOc;

That should yell antipattern to you. You're not holding pointers to existing objects, this is strOc actually owning that memory. You use new to add to it. I don't see any deletes. So you're leaking memory. Doesn't matter so much in this case, but this is exactly what RAII is for. Prefer:

std::vector<std::unique_ptr<StringOccurrence>> strOc;

Though, regardless, don't use a vector to begin with because...

Data Container Choice

You are holding a vector of StringOccurrences. That means that on each new word, you have to walk through the whole vector doing string comparisons. That is O(N). Everything about this is bad. To start with:

goto end; //skip next step (need fix?)

Yes, this needs a fix. Never use goto. The way to search for things is to use the <algorithm> library, specifically std::find_if:

auto it = std::find_if(strOc.begin(), strOc.end(), [&](StringOccurence* so){
    return so->m_str == stringBuff;
});
if (it != strOc.end()) {
    // success case
}
else {
    // new word case
}

That'll make your code easier to understand by far and drop the goto. But it won't handle the O(N) problem. For that, we just need to use an entirely new data structure. We need to map a word to a number, and we don't care about word ordering. Thus, std::unordered_map. This will have O(1) lookup. And we don't even need to do all that work ourselves!

std::unordered_map<std::string, int> strOc;
// for each word
++strOc[stringBuff]; // this will insert new elements as necessary

Cool.

Read the words directly

You are walking through a line character by character. That is error-prone at best, hard to follow at worst. But there's already support for this in C++. Use a std::stringstream. You could have just done:

while (std::getline(in, lineBuff)) {
    std::string word;
    std::istringstream iss(lineBuff);
    while (iss >> word) {
        ...
    }
}

Then again, operator>> is defined on any istream, not just istringstream. So we can use that on the ifstream directly:

std::string word;
while (in >> word) {
    ...
}

Use the right loops

Don't use auto with iterators - just use a range-based for-expression. It'll save on the typing and add to clarity.

Improved solution

std::unordered_map<std::string, int> wordCounts;
std::string word;
while (in >> word) {
    ++wordCounts[word];
}

std::ofstream out("test2.out");
for (auto const& wc : wordCounts) {
    out << wc.first << ' ' << wc.second << '\n';
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ This inserts full lines, not words. You need some way of splitting based on spaces. \$\endgroup\$ – Yuushi Sep 14 '15 at 14:16
  • 2
    \$\begingroup\$ No need to read a line then serialize the line. Just serialize the in into strings. \$\endgroup\$ – Martin York Sep 14 '15 at 17:52
  • \$\begingroup\$ To add to @LokiAstari's comment, the first loop would be much better as std::string word; while (in >> word) { ++wordCounts[word]; } There's no reason to read lines. \$\endgroup\$ – David Hammen Sep 14 '15 at 18:16
4
\$\begingroup\$

Yes this can be simplified to:

int main()
{
     std::ifstream   inputFile("Bob");
     std::unordered_map<std::string, int>  count;

     std::for_each(std::istream_iterator<std::string>(inputFile),
                   std::istream_iterator<std::string>(),
                   [&count](std::string const& word){++count[word];});
}

Why this works:

operator>>

When you read a string from a stream with operator>> it read a space separated word. Try it.

 int main()
 {
     std::string  line;
     std::cin >> line;
     std::cout << line << "\n"; 
 }

If you run that and type a line of text. It will only print out the first space separated word.

std::istream_iterator

The standard provides an iterator for streams. std::istream_iterator<X> will read an object of type X from the stream using operator>>.

This allows you to use streams just like you would any other container when using standard algorithms. The standard algorithms take two iterators to represent a container (begin and end or potentially any two points in the container).

So by using std::istream_iterator<std::string> you can treat a stream like a container of space separated words and use it in an algorithm.

 int main()
 {
     std::string  line;
     std::istream_iterator<std::string> iterator(std::cin);

     line = *iterator;   // de-reference the iterator.
                         // Which reads the stream with operator >>
     std::cout << line << "\n"; 
 }

std::for_each

I use std::for_each above because it is trivial to use. But with a tiny bit of work you can use the range based for loop introduced in C++11 (as this just calls std::begin, std::end on the object to get the bounds of the loop.

But lets look at std::for_each first.

std::for_each(begin, end, action);

Basically it loops from begin to end and performs action on the result of de-referencing the iterator.

 // In my case action was a lambda
 [&count](std::string const& word){++count[word];}

It captures count from the current context to be used in the funtion. And de-referencing the std::istream_iterator<std::string> returns a reference to a std::string object. So we can not use that to increment the count for each word.

Note: count is std::unordered_map so be looking up a value it will automatically insert it if it does not already exist (using default value (for int that is zero). Then increment that value in the map.

Range based for

A quick search to use range based for with std::istream_iterator gives me this:

template <typename T>
struct irange
{
    irange(std::istream& in): d_in(in) {}
    std::istream& d_in;
};
template <typename T>
std::istream_iterator<T> begin(irange<T> r) {
    return std::istream_iterator<T>(r.d_in);
}
template <typename T>
std::istream_iterator<T> end(irange<T>) {
    return std::istream_iterator<T>();
}

int main()
{
     std::ifstream   inputFile("Bob");
     std::unordered_map<std::string, int>  count;

     std::for(auto const& word : irange<std::string>(inputFle)) {
         ++count[word];
     }
}

Issues with this technique.

We use space to separate words. So any punctuation is going to screw things up. Not to worry. C++ allows you to define what is a space in any given context. So we just need to tell the stream what is a space.

https://stackoverflow.com/a/6154217/14065

Review of code

Sure.

struct StringOccurrence //stores word and number of occurrences
{
    std::string m_str;
    unsigned int m_count;
    StringOccurrence(const char* str, unsigned int count) : m_str(str), m_count(count) {};
};

But you can do this with a number of standard types.

typedef std::pair<std::string, unsigned int> StringOccurrence;

You are doing this to store the value in a vector. But a better way to store this is in a map. Because maps are ordered in some way internally lookup is a lot faster. std::map gives access in O(ln(n)) or std::unordered_map gives access in O(1).

I hate bad comments. Bad comments are worse than no comments because they need to be maintained and the compiler will not help you maintain them.

    if (!in) //check if file path is valid

Not quite, but close enough I suppose. But I don't really need the comment to tell me that. The code seems pretty self explanatory.

Note sure if -1 is a good value. It will really depend on the OS you are running on. 0 is the only valid value. Anything else is considered an error. At your OS level this will probably be truncated to 255 on most systems (but not all).

        return -1;

If you run this:

> cat xrt.cpp

int main()
{
    return -1;
}
> g++ xrt.cpp
> ./a.out
> echo $?         # Echos the error code of the last command.
255

I don't think you need to copy the whole thing into memory.

    std::vector<std::string>vec;
    std::string lineBuff;
    while (std::getline(in, lineBuff)) // write multiline text to vector of strings
    {
        vec.push_back(lineBuff);
    }

Just read a line at a time and processes that.

Don't use pointers in C++

    std::vector<StringOccurrence*> strOc;

C++ has much better ways to handle dynamic memory allocation and pointers is never the way to go.

When you iterate from begin -> end of something. You can use the new range based for instead.

    for (auto it = vec.begin(); it < vec.end(); it++)

    // easier to write and read:

   for(auto const& val : vec)

Going to comment on your comments again.

    for (auto it = vec.begin(); it < vec.end(); it++) //itterate through each line

Not very useful. I can see that you are iterating over every line. From the code. You should restrict your comments to WHY you are doing something.

Space ' ' is not the only white space character! What about tab or carrige return \r or vertical tab \v. You should test for space using standard library routines.

std::is_space(c)

I have use goto probably twice in the last ten years. One of those times was probably wrong.

                        goto end; //skip next step (need fix?)

Loops and conditions will always be better and easier to read.

We have a leak her:

                strOc.push_back(new StringOccurrence(stringBuff.c_str(), 1));

I see a new (but no delete). See above about using pointers. There is no need to use a pointer here. Just use a normal object it will be moved into the vector.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Indeed, your algorithm looks quite complicated as is. This can be simplified dramatically with some algorithm usage and a more suitable data structure.

Whenever you have a value that you want to store some data for (such as an associated count), you should be thinking of std::map (or std::unordered_map).

using counter_type = std::unordered_map<std::string, unsigned>;

Instead of looping over each character one by by, it's easier to process it word-by-word, splitting on spaces. The standard library unfortunately doesn't have a (nice) way of doing this, but the boost string algorithms library does:

std::vector<std::string> no_spaces;
boost::split(no_spaces, vec, boost::any_of(' \t\n'),
             boost::token_compress_on);

From here, you already have all the words you need, split up. The last thing to do is to add them to the map:

counter_type occurrence_counter;
for(const auto& word : no_spaces) {
    ++occurrence_counter[word];
}

Writing the map out to a file is similar to what you already have.

As an aside, there is no reason to store a pointer in your vector here. This will actually leak memory, as it is never deleted (for a short program like this, the OS will clean it all up very quickly anyway, but it's a bad habit to get into).

A final note: this solution is still incomplete, as it doesn't deal with punctuation of any kind. You may need to do thing such as strip all characters not in [a-zA-Z0-9] (in regex terms).

| improve this answer | |
\$\endgroup\$

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.