根据长度对set<string>进行排序

Question

我的问题与这个有关。

我想使用lambda表达式作为谓词，在set上执行sort()操作。

我的代码是：

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

但是错误的数量和类型非常复杂，我无法理解如何修复它们。有人能告诉我这段代码哪里出错了吗。

- Tester

---

其他人已经指出，您无法对std::set进行std::sort。此外，我认为在lambda表达式之前的);应该是一个逗号。 - Blastfurnace

Answer 1

编辑：请注意，Steve Townsend 的解决方案实际上是你要寻找的解决方案，因为他使用了 C++0x Lambda 内联了我下面写的 C++03 代码。

另一个解决方案是自定义 std::set 的排序函数：

std::set 已经被排序了...

std::set 自带排序功能，一旦构建完成后就不应该再修改它。 因此，以下代码：

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

将输出以下结果：

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

...但是您可以自定义其排序函数

现在，如果您希望，您可以通过使用自己的比较函数来自定义您的集合：

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

在这个比较函数中，我处理了"长度相同但内容不同意味着不同的字符串"这种情况，因为我认为（也许是错误的）在原始程序中的行为是一个错误。要编写原始程序中的行为，请从代码中删除if块。

现在，您可以构建集合：

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

现在集合将使用函子MyStringLengthCompare来排序其项目，因此，此代码将输出：

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

但要小心排序错误！

当您创建自己的排序函数时，它必须遵循以下规则：

如果 (lhs < rhs) 为真，则返回 true，否则返回 false

如果由于某种原因您的排序函数不遵守此规则，则会出现错误的集合。

- paercebal

---

这改变了程序的行为。现在集合只能包含一个给定长度的字符串，而不是任意给定值。你的输出有错误；要得到那个结果需要使用multiset。 - Potatoswatter

@Potatoswatter：问题作者的程序将忽略内容不同但长度相同的字符串。但作者没有描述程序的意图，只是说它有 bug。我猜原始程序的行为是错误的。这就是为什么我的比较函数处理“长度相同，内容不同”的情况。我会在我的答案中澄清这一点，其有趣的价值不在于比较函数的精确代码，而在于它的使用及其陷阱。 - paercebal

@Potatoswatter：现在，如果你跟随链接，你会看到作者想要能够拥有相同长度的字符串的排列，比如“abc”，“bca”等等。在这种情况下，“仅长度”比较函数是无法帮助他的。这让我相信我提供的“先比较长度再比较内容”的方法是正确的。 - paercebal

@Potatoswatter：最后，我想知道你的评论是否意味着我的代码和/或其输出是错误的。因此，为了澄清一切，我的代码在发布之前已经经过测试，其输出是真实的。因此，我的“输出没有错误”。 - paercebal

啊，现在我明白了“默认正常比较”的情况。+1。http://ideone.com/Hywlu - Potatoswatter

Answer 2

std::sort可以重新排列你提供的序列中的元素。由于set中的序列排列是固定的，因此你只能使用const迭代器。

你需要先将results复制到vector或deque（或类似的容器）中。

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

- Potatoswatter

---

我想问他为什么首先要将它们插入到一个集合中。 - Yakov Galka

@ybung：我想是为了去重。 - Potatoswatter

Answer 3

您可以通过提供自定义谓词来确定添加的元素相对于现有成员的顺序，以自定义 set 中元素的排序。 set 的定义如下：

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

其中Traits是提供一个函数对象的类型，该函数对象可以将两个元素值作为排序键进行比较，以确定它们在集合中的相对顺序。此参数是可选的，默认值为二元谓词less。

有关如何将lambda表达式用作模板参数的背景信息，请参见此处。

在您的情况下，这转化为：

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

请注意，这将导致具有相同字符串长度的set元素被视为重复项，而这不是您所希望的结果，就我所理解的而言。

- Steve Townsend

---

@Roger - 你的评论因为包含代码而变得混乱，我认为 - 我的回答已经表明它会导致具有相同长度的字符串重复 - 然而，问题确实要求如何基于字符串长度对std::set进行排序... - Steve Townsend

你忘记在 a.length() 上加括号，但你仍然想要：return a.length() < b.length() or (a.length() == b.length() and a < b); - Roger Pate

Answer 4

sort需要随机访问迭代器，而set不提供（它是一个双向迭代器）。如果你将代码更改为使用vector，它就可以编译了。

- Naveen

Answer 5

既然你正在使用我编写的原始代码，也许我可以对其进行扩展... :)

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

这首先按长度比较，然后按值比较。修改集合定义：

set<string, cmp_by_length> results;

然后你就可以开始了：

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

- Roger Pate

Answer 6

你不能对一个集合进行排序。它总是按照键（也就是元素本身）的顺序排列。

更具体地说，std::sort 需要随机访问迭代器。而 std::set 提供的迭代器不是随机的。

- Pavel Minaev

Answer 7

std::set最有用的是维护一个排序和可变列表。如果集合本身在构建后不会发生太多变化，使用向量会更快、更小。

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

我使用了经典的sort/unique/erase组合来使结果集唯一化。我还将您的代码整理得更加符合C++0x的风格。

- deft_code