Sorting a set<string> on the basis of length

Question

My question is related to this.

I wanted to perform a sort() operation over the set with the help of a lambda expression as a predicate.

My code is

#include <set>
#include <string>
#include <iostream>
#include <algorithm>
int main() {
  using namespace std;
  string s = "abc";
  set<string> results;
  do {
    for (int n = 1; n <= s.size(); ++n) {
      results.insert(s.substr(0, n));
    }
  } while (next_permutation(s.begin(), s.end()));

  sort (results.begin(),results.end());[](string a, string b)->bool{

              size_t alength = a.length();
              size_t blength = b.length();
              return (alength < blength);
  });
  for (set<string>::const_iterator x = results.begin(); x != results.end(); ++x) {
    cout << *x << '\n';
  }
  return 0;
}

But the numbers and types of errors were so complex that I couldn't understand how to fix them. Can someone tell me whats wrong with this code.

Answer 1

Edit: Note that Steve Townsend's solution is actually the one you're searching for, as he inlines as a C++0x Lambda what I write as C++03 code below.

Another solution would be to customize the std::set ordering function:

The std::set is already ordered...

The std::set has its own ordering, and you are not supposed to change it once it is constructed. So, the following code:

int main(int argc, char* argv[])
{
    std::set<std::string> aSet ;

    aSet.insert("aaaaa") ;
    aSet.insert("bbbbb") ;
    aSet.insert("ccccccc") ;
    aSet.insert("ddddddd") ;
    aSet.insert("e") ;
    aSet.insert("f") ;

    outputSet(aSet) ;

    return 0 ;
}

will output the following result:

 - aaaaa
 - bbbbb
 - ccccccc
 - ddddddd
 - e
 - f

... But you can customize its ordering function

Now, if you want, you can customize your set by using your own comparison function:

struct MyStringLengthCompare
{
    bool operator () (const std::string & p_lhs, const std::string & p_rhs)
    {
        const size_t lhsLength = p_lhs.length() ;
        const size_t rhsLength = p_rhs.length() ;

        if(lhsLength == rhsLength)
        {
            return (p_lhs < p_rhs) ; // when two strings have the same
                                     // length, defaults to the normal
                                     // string comparison
        }

        return (lhsLength < rhsLength) ; // compares with the length
    }
} ;

In this comparison functor, I did handle the case "same length but different content means different strings", because I believe (perhaps wrongly) that the behaviour in the original program is an error. To have the behaviour coded in the original program, please remove the if block from the code.

And now, you construct the set:

int main(int argc, char* argv[])
{
    std::set<std::string, MyStringLengthCompare> aSet ;

    aSet.insert("aaaaa") ;
    aSet.insert("bbbbb") ;
    aSet.insert("ccccccc") ;
    aSet.insert("ddddddd") ;
    aSet.insert("e") ;
    aSet.insert("f") ;

    outputSet(aSet) ;

    return 0 ;
}

The set will now use the functor MyStringLengthCompare to order its items, and thus, this code will output:

 - e
 - f
 - aaaaa
 - bbbbb
 - ccccccc
 - ddddddd

But beware of the ordering mistake!

When you create your own ordering function, it must follow the following rule:

return true if (lhs < rhs) is true, return false otherwise

If for some reason your ordering function does not respect it, you'll have a broken set on your hands.

Answer 2

std::sort rearranges the elements of the sequence you give it. The arrangement of the sequence in the set is fixed, so the only iterator you can have is a const iterator.

You'll need to copy results into a vector or deque (or such) first.

vector sortable_results( results.begin(), results.end() );

Answer 3

You can customize the ordering of the elements in the set by providing a custom predicate to determine ordering of added elements relative to extant members. set is defined as

template <
    class Key, 
    class Traits=less<Key>, 
    class Allocator=allocator<Key> 
>
class set

where Traits is

The type that provides a function object that can compare two element values as sort keys to determine their relative order in the set. This argument is optional, and the binary predicate less is the default value.

There is background on how to use lambda expression as a template parameter here.

In your case this translates to:

auto comp = [](const string& a, const string& b) -> bool 
    { return a.length() < b.length(); };
auto results = std::set <string, decltype(comp)> (comp);

Note that this will result in set elements with the same string length being treated as duplicates which is not what you want, as far as I can understand the desired outcome.

Answer 4

sort requires random access iterators which set doesn't provide (It is a bidirectional iterator). If you change the code to use vector it compiles fine.