sort string vector in c++

Question

I am writing c++ to sort a string vector. The string should be sorted by its length. If the lengths are the same, sorting by its lexicographical order: eg: abc < abd Here is my code:

static bool sort_find(string& a, string& b){
         if(a.size() < b.size()){
             return true;
         }
         else if(a.size() > b.size()){
             return false;
         }
         else{
             for(int i=0;i<a.size();i++){
                if(a[i] ==  b[i] )
                  continue;
                 else if(a[i] < b[i]){
                    return true;
                  }
                 else{
                   return false;
                }
             }
             return true;
         }
     }

int main(){

 string array[13]={"m","mo","moc","moch","mocha","l","la","lat","latt","latte","c","ca","cat"};

 vector<string> svector(array,array+13);
 sort(svector.begin(),svector.end(),sort_find);
 return 0;
}

The output of this code is [c, l, m, ca, la, moch, mo, cat, lat, moc, latt, mocha, latte] The output does not make sense to me.

Everyone's help is welcome!!

Thanks!

Kenny Ostrom · Accepted Answer · 2017-12-17 14:38:12Z

At first, I thought it was fine. It worked for me. But that was pure luck.

If you look up std::sort, and follow the link for the requirements on the comparison function to http://en.cppreference.com/w/cpp/concept/Compare you will find that it must be a strict weak ordering, including the requirement that

For all a, comp(a,a)==false

You return true if both strings are the same. This does not make sense, as you are really defining the less than operator. This leads to unexpected behavior with std algorithms and data structures which expect a strict weak ordering.

In order to fix it, I would recommend that if the lengths are the same, you simply return a<b, as std::string already has lexicographical comparison.

bool compare_length_then_string_lt(const string& a, const string& b) {
    if (a.size() < b.size())
        return true;
    else if (a.size() > b.size())
        return false;
    else
        return a < b;
}

std::sort(svector.begin(), svector.end(), compare_length_then_string_lt);

But I almost forgot. When combining multiple different ways to compare two structs, you can often use std::tuple or std::tie, which already know how to chain the comparisons together correctly. You just tell them what components to compare in what order, and they take care of the rest:

std::sort(svector.begin(), svector.end(),
    // lambda notation
    [](const std::string &lhs, const std::string &rhs) {
        // comparator body
        return std::make_tuple(lhs.size(), lhs) < std::make_tuple(rhs.size(), rhs);
    }
);

Collectives™ on Stack Overflow

sort string vector in c++

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related