Sorting a set 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 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 2

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;
}

Answer 3

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 4

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 5

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 6

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.