Сортировка набора <string>по длине - PullRequest
Новая
       18

Сортировка набора <string>по длине

6 голосов
/ 02 октября 2010

Мой вопрос связан с этим .

Я хотел выполнить sort() операцию над set с помощью лямбда-выражения в качестве предиката.

Мой код 

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

Но количество и типы ошибок были настолько сложными, что я не мог понять, как их исправить. Может кто-нибудь сказать мне, что не так с этим кодом.

Ответы [ 7 ]

8 голосов
/ 02 октября 2010

Редактировать : Обратите внимание, что Решение Стива Таунсенда на самом деле именно то, что вы ищете, поскольку он в качестве 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

Но остерегайтесь ошибки упорядочения!

Когда вы создаете свою собственную функцию упорядочения,оно должно следовать следующему правилу:

вернуть true, если (lhs

Если по какой-то причине ваша функция упорядочения не соблюдает ееу вас будет сломанный набор на руках.

5 голосов
/ 02 октября 2010

std::sort переупорядочивает элементы заданной вами последовательности. Расположение последовательности в set фиксировано, поэтому единственный итератор, который вы можете иметь, - это const итератор.

Сначала вам нужно будет скопировать results в vector или deque (или около того). 

vector sortable_results( results.begin(), results.end() );
3 голосов
/ 02 октября 2010

Вы можете настроить порядок элементов в set, предоставив пользовательский предикат для определения порядка добавленных элементов относительно существующих элементов. set определяется как 

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

где черты

Тип, который предоставляет функцию объект, который может сравнивать два элемента значения в качестве ключей сортировки, чтобы определить их относительный порядок в наборе. это аргумент необязательный, а двоичный предикат меньше по умолчанию значение.

На имеется справочная информация о том, как использовать лямбда-выражение в качестве параметра шаблона здесь .

В вашем случае это означает: 

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

Обратите внимание, что это приведет к тому, что элементы set с одинаковой длиной строки будут считаться дубликатами, а это не то, что вам нужно, насколько я понимаю, желаемый результат.

2 голосов
/ 02 октября 2010

sort требует итераторов произвольного доступа, которые set не предоставляет (это двунаправленный итератор)Если вы измените код для использования vector, он прекрасно скомпилируется.

1 голос
/ 04 октября 2010

Поскольку я написал исходный код, который вы используете, возможно, я смогу расширить его ...:) 

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;
}
1 голос
/ 02 октября 2010

Вы не можете отсортировать набор.Он всегда упорядочен по ключам (которые сами являются элементами).

Чтобы быть более точным, std::sort требует итераторов произвольного доступа.Итераторы, предоставленные std::set, не являются случайными.

0 голосов
/ 02 октября 2010

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-y.

...