Sort linked list within template - issues with strings

Question

I'm creating a linked list that is sorting on insertion. It's a template class, so type is defined at run-time.

The problem is, I am comparing two values to see which one is greatest, then I put that value in the spot within the linked list it is supposed to be. This works all fine and dandy for any math based type, but it doesn't work well for strings. It doesn't sort alphabetically.

Here's the code I'm trying to get working properly, so I can compare two strings and find out which one comes first alphabetically (but it's a template, so it has to work for other types as well)

The comparison code is here

while ( data  >  iter->_data && iter->_next != 0) {

Here's the full code, and I've included some code from main() below as well

template <typename T>
class LinkedList;

template <class TNode>
class Iterator
{
    friend class LinkedList<typename TNode::value_type>;
    TNode* pNode;

    Iterator(TNode* _pNode) : pNode(_pNode) {}
public:
    void operator++() { pNode = pNode->_next; }
    void operator++(int) { pNode = pNode->_next; }
    bool operator!=(Iterator<TNode> rval) { return !(pNode == rval.pNode); }
    bool operator==(Iterator<TNode> rval) { return (pNode == rval.pNode); }
    typename TNode::value_type operator*() { return pNode->_data; }
    Iterator<TNode> operator+(int _i)
    {
        Iterator<TNode> iter = *this;
        for (int i = 0; i < _i; ++i)
        {
            if (iter.pNode) //If there's something to move onto...
                ++iter;
            else
                break;
        }
        return iter; //Return regardless of whether its valid...
    }
};

template <typename T>
class Node
{
    friend class LinkedList<T>;
    friend class Iterator<Node<T> >;
    Node() : _next(0) {}
    Node(T data) : _data(data), _next(0) {}
    Node(T data, Node<T>* next) : _data(data), _next(next) {}
    Node(Node<T>* next) : _next(next) {}

    T _data;
    Node<T>* _next;
    Node<T>* _prev;
public:
    typedef T value_type;
};

template <typename T>
class LinkedList
{
    Node<T>* first;
    int count = 0;

public:
    typedef Iterator<Node<T> > iterator;
    typedef T         value_type;

    LinkedList() : first(0) {}
    ~LinkedList()
    {
        if (first)
        {
            Node<T> *iter = first;
            while (iter != 0)
            {
                Node<T>* tmp = iter;
                iter = iter->_next;
                delete tmp;
            }
        }
    }
    bool LinkedList<T>::operator < (LinkedList<T> rhs);
    bool LinkedList<T>::operator > (LinkedList<T> rhs);

    void insert(T data)
    {
        if (first)
        {
            Node<T> *iter = first;
            Node<T> *preIter = first;
            while ( data  >  iter->_data && iter->_next != 0) {
                preIter = iter;
                iter = iter->_next;
            }
            if (iter == first) {
                if (data < iter->_data) {
                    Node<T>* holder = first;
                    first = new Node<T>(data);
                    first->_next = holder;
                    holder->_prev = first;
                    first->_prev = 0;
                }
                else if (iter->_next != 0) {
                    Node<T>* newIter = new Node<T>(data);
                    newIter->_next = first->_next;
                    first->_prev = newIter;
                    newIter->_prev = first;
                    first->_next = newIter;
                }
                else {
                    first->_next = new Node<T>(data);
                    first->_next->_prev = first;
                }

            }
            else if(preIter->_next != 0) {
                Node<T>* newIter = new Node<T>(data);
                preIter->_next = newIter;
                newIter->_next = iter;
                iter->_prev = newIter;
                newIter->_prev = preIter;
            }
            else {
                iter->_next = new Node<T>(data);
                iter->_next->_prev = iter->_next;
            }
        }

    };

    iterator begin() { return iterator(first); }
    iterator end() { return iterator(0); }

    bool erase(iterator& _iNode) //True for success, vice versa
    {
        /* This is rather inneffecient. Maybe a better way to do this? */
        /* Even then, it's *still* more effecient than a contiguous container */
        if (_iNode.pNode == first)
        {
            first = first->_next;
            delete _iNode.pNode;
            return true;
        }
        else
        {
            for (Node<T>* iter = first; iter->_next; iter = iter->_next)
            {
                if (iter->_next == _iNode.pNode) //Find our node.
                {
                    iter->_next = _iNode.pNode->_next;
                    delete _iNode.pNode;
                    return true;
                }
            }
        }
        return false;
    }
};

With the below code, the end sorting result does not equal for the test. It works fine for the integer test (also included), but not the string tests. I end up with all upper case characters for at the beginning for the first A...Z string test, and some of the words for the full word test aren't in the correct places for the second string test. In general, it's fairly accurate, but not fully alphabetical.

How can I make this alphabetically sorted?

/** Test fundamental concept by storing and retrieving 0..9 */
BOOST_AUTO_TEST_CASE(ut_concept_0_to_9) {
    vector<long> v{ 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    auto shuffle = v;
    random_shuffle(shuffle.begin(), shuffle.end());

    LinkedList<long> sl;
    for (auto x : shuffle)
        sl.insert(x);

    auto it = sl.begin();
    for (auto x : v) {
        BOOST_CHECK_EQUAL(*it, x);
        ++it;
    }
}

/** Test fundamental concept by storing and retrieving A..Z */
BOOST_AUTO_TEST_CASE(ut_concept_A_to_Z) {
    string s = "Hello, world!";

    LinkedList<string::value_type> sl;
    for (auto ch : s)
        sl.insert(ch);

    sort(s.begin(), s.end());

    auto it = sl.begin();
    for (auto ch : s) {
        BOOST_CHECK_EQUAL(*it, ch);
        ++it;
    }
}

/** Test fundamental concept by storing and retrieving strings */
BOOST_AUTO_TEST_CASE(ut_concept_strings) {
    vector<string> words{ "Sunna", "Mona", "Tiw", "Woden", "Thunor", "Frige", "Saturn" };
    LinkedList<string> sl;
    for (auto ch : words)
        sl.insert(ch);

    sort(words.begin(), words.end());

    auto it = sl.begin();
    for (auto word : words) {
        BOOST_CHECK_EQUAL(*it, word);
        ++it;
    }
}

EDIT: My Unique Solution

I ended up finding out that my issue was not a pure alphabetic sorting issue. It was actually in my code. I was missing a situation where I would place the object I was trying to put in order inbetween the last object, and the second to last object. It should have gone one past the last object. This code will be cleaned up, as there are a bunch of areas that need to be cleaned up, but this should sort properly. I was wrong about needing alphabetical sorting.

else if (iter->_next == NULL) {
    if (iter->_data < data) {
        iter->_next = new Node<T>(data);
            iter->_next->_prev = iter->_next;
        }
        else {
            Node<T>* newIter = new Node<T>(data);
            preIter->_next = newIter;
            newIter->_next = iter;
            iter->_prev = newIter;
            newIter->_prev = preIter;
        }
    }
}

I marked the answer below, as I used this to resolve my issues, and it is also the answer to alphabetical order, which was my original question. So, the original question is answered, but I found another issue that yields this question useless to me for my case, but others may need an answer to this question.

Answer 1

As others noted, std::string has overloaded operator < and > to do the job of doing a lexicographical comparison.

However, if your goal is to do an alphabetic sort, then you need to rewrite your template class. But then things get very messy using the code you have already written, so a different approach can be taken.

If you are allowed to leverage using std::list, then writing a template linked list class that stores items in a custom order can be done using a wrapper class.

First, we need to have the template take not only a type, but a comparison function to tell the linked list the criteria on how to insert an item into the list.

Without explaining too much more, here is the code:

#include <functional>
#include <algorithm>
#include <cctype>
#include <list>
#include <iterator>
#include <iostream>
#include <string>

template <typename T, typename Comparer = std::greater<T>>
class LinkedList
{
    private:
        std::list<T> m_list;

    public:
        void insert(const T& data)
        {
            Comparer comp;
            typename std::list<T>::iterator it = m_list.begin();
            while (it != m_list.end())
            {
                // call the > comparison function
                if (comp(data, *it))
                    ++it;  // keep searching
                else
                {
                    // this is the spot
                    m_list.insert(it,data);
                    return;
                }
            }
            // has to go on the end if not inserted  
            m_list.push_back(data);
        }

        // use this for demonstration purposes only
        void displayMe()
        {
            std::copy(m_list.begin(), m_list.end(), std::ostream_iterator<T>(std::cout, "\n"));
        }
};

struct MyComparerForStrings
{
    // case insensitive comparison
    bool operator()(const std::string& s1, const std::string& s2) 
    { 
        std::string str1Cpy(s1);
        std::string str2Cpy(s2);

        // convert to lower case 
        std::transform(str1Cpy.begin(), str1Cpy.end(), str1Cpy.begin(), ::tolower);
        std::transform(str2Cpy.begin(), str2Cpy.end(), str2Cpy.begin(), ::tolower);

        // returns if first string is > second string 
        return (str1Cpy > str2Cpy);
    }
};

int main()
{
    LinkedList<std::string,  MyComparerForStrings> sList;
    sList.insert("abc");
    sList.insert("zzz");
    sList.insert("joe");
    sList.insert("BOB");
    sList.displayMe();
    cout << "\n";
    LinkedList<int> intList;
    intList.insert(10);
    intList.insert(1);
    intList.insert(3);
    intList.displayMe();
}

So what did we do? We created a template class that takes two parameters, a type and a comparison function.

Note that the comparison defaults to the std::greater for the type T. So for example, if it T is an int, then std::greater<int> will do the comparison of two integers to see if the first item is greater than the second. The example above shows that the template is instantiated the same way using a single parameter if the type's operator > is adequate (which for int, it is).

However, we want for our purposes to sort std::string alphabetically (or case insensitive). To do that, we give as a template argument our custom function that takes two strings and compares them alphabetically (heads up to this SO question: Case insensitive string comparison in C++)

Now, the insert function uses iterators and just searches, using our comparison function, for the spot to insert the item. When found, it just calls the list::insert function, which does all the work.

This is not the best example in the world, by no means. But you should be able to get the idea.

Here is a live example: http://coliru.stacked-crooked.com/a/ecb2e7957eb4fea8