Sort set <string> based on length

Question

My question is related to this .

I wanted to do a sort() operation on set using a lambda expression as a predicate.

My code

 #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 could not figure out how to fix them. Can someone tell me what is wrong with this code.

Answer 1

Edit : Please note that Steve Townsend's solution is the one you are looking for since it is included in C ++ 0x Lambda, which I write as C ++ 03 code below.

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

std::set already ordered ...

std::set has its own order, and you should not change it after creating it. 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 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 method, I really handled the case of “the same length, but different content means different lines” because I believe (possibly erroneously) that the behavior in the original program is an error. For the behavior to be encoded in the source program, remove the if block from the code.

And now you are creating a lot:

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

Now the set will use the MyStringLengthCompare functor to arrange its elements, and thus this code will output:

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

But beware of order errors!

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

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

If for any reason your order function does not comply, you will have a broken set in your hands.

Answer 2

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

You need to copy the results to vector or deque (or such) first.

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

Answer 3

You can customize the order of elements in set by providing a custom predicate to determine the order in which elements are added relative to existing members. set defined as

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

where are the traits

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

There is a background where you can use a lambda expression as a template parameter .

In your case, this means:

 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 that will be treated as duplicates that are not what you want, as far as I can understand the desired result.

Answer 4

sort requires random access iterators that set does not provide (this is a bidirectional iterator). If you change the code to use vector , it compiles fine.

Answer 5

You cannot sort a set. It is always ordered by keys (which themselves are elements).

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

Answer 6

Since I wrote the original code that you are using, maybe I can extend 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); } }; 

First, it is compared in length, then in value. Change the set definition:

 set<string, cmp_by_length> results; 

And you will go well:

 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 // ie 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 7

std :: set is most useful to maintain a sorted and mutating list. It is faster and less to use the vector when the set itself does not change significantly after its creation.

 #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 result set unique. I also cleared your code to a bit more C ++ 0x-y.