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

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 2

You cannot sort a set. It's always ordered on keys (which are elements themselves).

To be more specific, std::sort requires random access iterators. The iterators provided by std::set are not random.

Answer 3

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.

Answer 4

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 5

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 6

std::set is most useful to maintain a sorted and mutating list. It faster and smaller to use a vector when the set itself wont change much once it's been built.

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

  //make it unique
  sort( results.begin(), results.end() );
  auto end_sorted = unique( results.begin(), results.end() );
  results.erase( end_sorted, results.end() );

  //sort by length
  sort (results.begin(),results.end());
          [](string lhs, string rhs)->bool
             { return lhs.length() < rhs.length(); } );

  for ( const auto& result: results ) {
    cout << result << '\n';
  }
}

I used the classic, sort/unique/erase combo to make the results set unique.I also cleaned up your code to be a little bit more c++0x-y.

Answer 7

Since I wrote the original code you're using, perhaps I can expand on it... :)

struct cmp_by_length {
  template<class T>
  bool operator()(T const &a, T const &b) {
    return a.length() < b.length() or (a.length() == b.length() and a < b);
  }
};

This compares by length first, then by value. Modify the set definition:

set<string, cmp_by_length> results;

And you're good to go:

int main() {
  using namespace std;
  string s = "abc";
  typedef set<string, cmp_by_length> Results;  // convenience for below
  Results results;
  do {
    for (int n = 1; n <= s.size(); ++n) {
      results.insert(s.substr(0, n));
    }
  } while (next_permutation(s.begin(), s.end()));

  // would need to add cmp_by_length below, if I hadn't changed to the typedef
  // i.e. set<string, cmp_by_length>::const_iterator
  // but, once you start using nested types on a template, a typedef is smart
  for (Results::const_iterator x = results.begin(); x != results.end(); ++x) {
    cout << *x << '\n';
  }

  // of course, I'd rather write... ;)
  //for (auto const &x : results) {
  //  cout << x << '\n';
  //}

  return 0;
}