how to improve natural sort program for decimals ?

Question

Hello,

I have std::strings containing numbers in the leading section that I need to sort. The numbers can be integers or floats.

The vector<std::string> sort was not optimal, I found the following natural sort program which was much better. I still have a small issue with numbers smaller than zero that do not sort just right. Does anyone have a suggestion to improve? We're using Visual Studio 2003.

The complete program follows.

TIA, Bert

#include <list>
#include <string>
#include <iostream>

using namespace std;

class MyData
{
public:
    string m_str;
    MyData(string str) {
     m_str = str;
    }

    long field1() const 
    {
     int second = m_str.find_last_of("-");
     int first = m_str.find_last_of("-", second-1);
     return atol(m_str.substr(first+1, second-first-1).c_str());
    }

    long field2() const 
    {
     return atol(m_str.substr(m_str.find_last_of("-")+1).c_str());
    }

    bool operator < (const MyData& rhs)
    {
     if (field1() < rhs.field1()) {
      return true;
     } else if (field1() > rhs.field1()) {
      return false;
     } else {
      return field2() < rhs.field2();
     }
    }
};

int main()
{
    // Create list
    list<MyData> mylist;
    mylist.push_front(MyData("93.33"));
    mylist.push_front(MyData("0.18"));
    mylist.push_front(MyData("485"));
    mylist.push_front(MyData("7601"));
    mylist.push_front(MyData("1001"));
    mylist.push_front(MyData("0.26"));
    mylist.push_front(MyData("0.26"));


    // Sort the list
    mylist.sort();

    // Dump the list to check the result
    for (list<MyData>::const_iterator elem = mylist.begin(); elem != mylist.end(); ++elem)
    {
     cout << (*elem).m_str << endl;
    }

    return 1;
}

GOT:

0.26
0.26
0.18
93.33
485
1001
7601

EXPECTED:

0.18
0.26
0.26
93.33
485
1001
7601

Answer 1

If it's just float strings, I'd rather suggest to create a table with two columns (first row contains the original string, second row is filled with the string converted to float), sort this by the float column and then output/use the sorted string column.

Answer 2

If the data are all numbers I would create a new class to contain the data.

It can have a string to include the data but then allows you to have better methods to model behaviour - in this case espacially to implement operator <

The implementation could also include use of a library that calculates to exact precion e.g. GNU multiple precision this would do the comparison and canversion from string (or if the numbers do not have that many significant figures you could use doubles)

Answer 3

Use atof() instead of atol() to have the comparison take the fractional part of the number into account. You will also need to change the return types to doubles.

Answer 4

I would compute the values once and store them.
Because they are not actually part of the objects state (they are just calcualted values) mark them as mutable. Then they can also be set during const methods.

Also note that MyClass is a friend of itself and thus can access the private members of another object of the same class. So there is no need for the extranious accessor methods. Remember Accessor methods are to protect other classes from changes in the implementation not the class you are implementing.

The problem with ordering is that atoi() is only reading the integer (ie it stops at the '.' character. Thus all your numbers smaller than 0 have a zero value for comparison and thus they will appear in a random order. To compare against the full value you need to extract them as a floating point value (double).

class MyData
{
private:
    mutable     bool    gotPos;
    mutable     double  f1;
    mutable     double  f2;
public:
    /*
     * Why is this public?
     */
    std::string m_str;

    MyData(std::string str)
        :gotPos(false)
        ,m_str(str)     // Use initializer list
    {
        // If you are always going to build f1,f2 then call BuildPos()
        // here and then you don't need the test in the operator <
    }

    bool operator < (const MyData& rhs)
    {
        if (!gotPos)
        {   buildPos();
        }
        if (!rhs.gotPos)
        {   rhs.buildPos();
        }
        if (f1 < rhs.f1)    return true;
        if (f1 > rhs.f1)    return false;
        return f2 < rhs.f2;
    }
    private:
        void buildPos() const
        {
            int second = m_str.find_last_of("-");
            int first = m_str.find_last_of("-", second-1);

            // Use boost lexical cast as it handles doubles
            // As well as integers.
            f1 = boost::lexical_cast<double>(m_str.substr(first + 1, second-first - 1));
            f2 = boost::lexical_cast<double>(m_str.substr(second + 1));
            gotPos = true;
        }
};