CODEWITHSUNDEEP
c++vectorstruct
user2773084
user2773084

Reputation: 107

C++ Sorting a struct vector alphabetically

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 :(

Upvotes: 1

Views: 1105

Answers (2)

codeling
codeling

Reputation: 11379

            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;
        }
    }
}

Upvotes: 2

Luka Rahne
Luka Rahne

Reputation: 10447

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.

Upvotes: 2

Related Questions