1

I've got a task that I'm stuck on. I need to create a program that reads an input file, stores each word into a vector along with how many times that word was read (hence the struct). Those values then need to print out in alphabetical order.

I've come up with something that I think is along the right lines:

struct WordInfo {
string text;
int count; 
} uwords, temp;

string word;
int count = 0; //ignore this. For a different part of the task
vector<WordInfo> uwords;

while (cin >> word) {
    bool flag = false;
    count += 1;
    for (int i = 0; i < uwords.size(); i++) {
        if (uwords[i].text == word) {
            flag = true;
            uwords[i].count += 1;
        }
    }
    if (flag == false) {
        if (count == 1) { //stores first word into vector
            uwords.push_back(WordInfo());
            uwords[0].count = 1;
            uwords[0].text = word;
        } else {
            for (int i = 0; i < uwords.size(); i++) {
                if (word < uwords[i].text) {
                    uwords.push_back(WordInfo());
                    WordInfo temp = {word, 1};
                    uwords.insert(uwords.begin() + i, temp);
                }
            }
        }
    }
}

Now the problem I'm having, is that when I run the program it appears to get stuck in an infinite loop and I can't see why. Although I've done enough testing to realise it's probably in that last if statement, but my attempts to fix it were no good. Any help is appreciated. Cheers.

EDIT: I forgot to mention, we must use vector class and we're limited in what we can use, and sort is not an option :(

user2773084
  • 107
  • 2
  • 10

2 Answers2

2
            if (word < uwords[i].text) {
                uwords.push_back(WordInfo());
                WordInfo temp = {word, 1};
                uwords.insert(uwords.begin() + i, temp);
            }

Take a good look at this piece of code:

First, it will actually insert 2 words into your list; one time an "empty" one with push_back, and one time with insert. And it will do that whenever the current word is smaller than the one at the position i.

And as soon as it has inserted, there's 2 new elements to walk over; one actually being at the current position of i, so in the next iteration, we will again compare the same word - so your loop gets stuck because index i increases by 1 each iteration, but the increase of i only steps over the just inserted element!

For a quick solution, you want to (1) search for the position where the word before is "smaller" than the current one, but the next one is bigger. Something like

if (uwords[i-1].text < word && word < uwords[i].text) {

(2) and you want to get rid of the push_back call.

Furthermore, (3) you can break the loop after the if condition was true - you have already inserted then, no need to iterate further. And (4), with a bit of condition tweaking, the count == 1 can actually be merged into the loop. Modified code part (will replace your whole if (code == false) block - warning, not tested yet):

if (!flag) {
    for (int i = 0; i <= uwords.size(); ++i) {
        if ((i == 0 || uwords[i-1].text < word) &&
            (i == uwords.size() || word < uwords[i].text)) {
            WordInfo temp = {word, 1};
            uwords.insert(uwords.begin() + i, temp);
            break;
        }
    }
}
codeling
  • 11,056
  • 4
  • 42
  • 71
  • 1
    That's what I thought at first glance, but I don't think it's infinite because the `if` is not satisfied at every iteration. It's very exponential, however. – paddy Nov 07 '13 at 12:36
  • 1
    @paddy it is, as soon as a word is encountered where word is smaller than any uwords entry. When inserting the new word, and then increasing i, it means that in subsequent loops we are actually comparing the same word over and over – codeling Nov 07 '13 at 12:39
  • Ahh true. There's a sign that I should go to bed instead of browsing SO =) – paddy Nov 07 '13 at 12:42
  • I added push_back in there a bit out of desperation. Unfortunately, just having the insert function still yields the infinite loop. – user2773084 Nov 07 '13 at 12:44
  • did you read my whole answer and do it the way I write? or did you just remove the push_back? – codeling Nov 07 '13 at 12:45
  • Sorry, I only just saw the rest of the answer. I'll give it a shot. – user2773084 Nov 07 '13 at 12:46
  • The good news is that the infinite loop is gone. But now the program is only reading in the first word of the input, and nothing after that. I'll keep tinkering with it. – user2773084 Nov 07 '13 at 13:12
  • how do you figure that it reads nothing after that? what do you give as input, what is the output? maybe create a new question with it – codeling Nov 07 '13 at 13:26
  • @nyarlathotep I had to change a few minor pieces with your code, but nothing major (thanks for the foundation). The other problem which took me a while to figure out was that if the word was greater than the last word of the vector, it wouldn't add the word in because my code was only dealt with words less than. E.g. if the first word is 'in', then only words starting with letter a-h would be added to the vector. The solution was a simple if statement that executes if a word wasn't placed in the vector. – user2773084 Nov 07 '13 at 14:38
  • ah of course ;) - with a bit of condition tweaking, you actually shouldn't need any additional if blocks at all - see my updated answer (even the count == 1 if block should be superfluous) – codeling Nov 07 '13 at 14:47
2

You should not push your words nin vector, but in map

std::map<std::string,int>

Since map has comparable keys iterator over map, automaticaly returns sorted range that can be later pushed in vector if needed.

Luka Rahne
  • 10,336
  • 3
  • 34
  • 56