使用string.compare()进行反向字母排序

Question

我有一个函数，它将一个单词添加到字母表中适当位置的链表中。它应该按A-Z排序，但由于某种原因，它是相反的。我认为问题是我使用string.compare()错误，但它可能是其他东西。这可能很容易修复，我只是盯着它看了一段时间，我会欣赏一个新的视角!

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

Answer 1

看来你已经交换了compare的参数。想象a.compare(b) < 0等于a < b。然后你会发现你在做:

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

你可能指的是if (theWord < Head)，所以真正的代码应该是:

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

当然，由于您只使用每个compare()的结果一次，因此您可以直接使用operator <:

if(theWord < mpHead->word)
//...
while( theWord > pCurrent->pNextNode->word)

Answer 2

直接使用std::set。

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

with std::list(允许链表+副本):

#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");
// ...

注意:在中也有std::multiset，它也允许重复。