CODEWITHSUNDEEP
c++stringsortinglinked-listalphabetical
Unsigned
Unsigned

Reputation: 25

Alphabetical Sorting is backwards using string.compare()

I have a function that adds a word to a linked list at the appropriate place in the alphabet. It should be sorted A-Z, but for some reason it's the other way around. I think the issue is I'm using string.compare() wrong, but it could be something else. It's probably an easy fix, I've just been staring at it for a while and would appreciate a new perspective!

void LinkedList::addWord( const string& theWord )
{
    ListNode* toAdd = new ListNode(theWord, NULL);

    if( !mpHead ){
        mpHead = toAdd;
        return;
    }

    if(mpHead->word.compare(theWord) < 0){
        toAdd->pNextNode = mpHead;
        mpHead = toAdd;
        return;
    }

    if(mpHead->pNextNode == NULL){
        mpHead->pNextNode = toAdd;
        return;
    }

    ListNode* pCurrent = mpHead;
    ListNode* pCurrentNext = mpHead->pNextNode;

    while( pCurrent->pNextNode->word.compare(theWord) > 0 )
    {
        pCurrent = pCurrentNext;
        pCurrentNext = pCurrentNext->pNextNode;
    }

    toAdd->pNextNode = pCurrent->pNextNode;
    pCurrent->pNextNode = toAdd;
}

Upvotes: 1

Views: 279

Answers (2)

slow
slow

Reputation: 11

just use std::set.

#include <set>
#include <string>
// ...
std::set<std::string> s;
s.insert("foo");
s.insert("fred");
// ...

with std::list (linked list + duplicates allowed):

#include <list>
#include <algorithm>
// ...
std::list<std::string> l;
l.insert(std::lower_bound(l.begin(), l.end(), "foo"), "foo");
l.insert(std::lower_bound(l.begin(), l.end(), "fred"), "fred");
l.insert(std::lower_bound(l.begin(), l.end(), "foo"), "foo");
// ...

note: there's also std::multiset within <set>, which also allows duplicates.

Upvotes: 1

Angew is no longer proud of SO
Angew is no longer proud of SO

Reputation: 171167

It seems you've swapped the arguments of compare. Think of a.compare(b) < 0 as equivalent to a < b. Then you'll see you're doing:

if (Head < theWord) { insert theWord before Head; }

You probably meant if (theWord < Head) instead, so the real code would be:

if(theWord.compare(mpHead->word) < 0){
    toAdd->pNextNode = mpHead;
    mpHead = toAdd;
    return;
}

// ...

while( theWord.compare(pCurrent->pNextNode->word) > 0 )
{
    pCurrent = pCurrentNext;
    pCurrentNext = pCurrentNext->pNextNode;
}

Of course, since you're only using the result of each compare() once, you could use the operator < directly instead:

if(theWord < mpHead->word)

//...

while( theWord > pCurrent->pNextNode->word)

Upvotes: 1

Related Questions