String Sort . Boost , Boost.Sort , Spreadsort

String Sort

<string_sort>представляет собой гибридный алгоритм на основе радикса / сравнения, который сортирует строки символов (или массивы двоичных данных) в порядке возрастания.

Простейшая версия (без функторов) сортирует строки элементов, которые могут отливать на неподписанный тип данных (например, неподписанный char), иметь оператор <, иметь функцию размера и функцию данных (), которая возвращает указатель на массив символов, таких как std::string. Версия функтора может сортировать любой тип данных, который имеет строгую слабую упорядоченность, с помощью шаблонирования, но требует определений get_char (действует как x [offset] на строке или массиве байтов), get_length (возвращает длину сортируемой строки) и сравнительный функтор. Отдельные символы, возвращаемые get_char, должны поддерживать оператора != и иметь неподписанное значение, определяющее их лексикографический порядок.

Этот алгоритм неэффективен для типов символов размером более 2 байт каждый и оптимизирован для однобайтных строк символов. По этой причинеstd::sortбудет называться вместо этого, если тип персонажа имеет размер >2.

<string_sort>имеет специальную оптимизацию для идентичных подстрок. Это добавляет некоторые накладные расходы на случайные данные, но идентичные подстроки распространены в реальных строках.

reverse_string_sort сортирует строки в обратном (отклоняющемся) порядке, но в остальном идентичен.<string_sort>достаточно гибкий, чтобы сортировать любой тип данных, которыйstd::sortможет, при условии, что пользователь предоставляет соответствующие функторы, которые индексируют в ключ.

Сортировка струн Windows

Сортировка струн OSX

String Sort Examples

См.stringfunctorsample.cppдля примера того, как сортировать структуры с помощью струнного ключа и всех функторов:

struct lessthan {
  inline bool operator()(const DATA_TYPE &x, const DATA_TYPE &y) const {
    return x.a < y.a;
  }
};

struct bracket {
  inline unsigned char operator()(const DATA_TYPE &x, size_t offset) const {
    return x.a[offset];
  }
};

struct getsize {
  inline size_t operator()(const DATA_TYPE &x) const{ return x.a.size(); }
};

И эти функторы используются таким образом:

string_sort(array.begin(), array.end(), bracket(), getsize(), lessthan());

См.generalizedstruct.cppдля рабочего примера обобщенного подхода к сортировке структур последовательностью целых, поплавковых и множественных струнных ключей с использованием string_sort:

struct DATA_TYPE {
  time_t birth;
  float net_worth;
  string first_name;
  string last_name;
};
static const int birth_size = sizeof(time_t);
static const int first_name_offset = birth_size + sizeof(float);
static const boost::uint64_t base_mask = 0xff;
struct lessthan {
  inline bool operator()(const DATA_TYPE &x, const DATA_TYPE &y) const {
    if (x.birth != y.birth) {
      return x.birth < y.birth;
    }
    if (x.net_worth != y.net_worth) {
      return x.net_worth < y.net_worth;
    }
    if (x.first_name != y.first_name) {
      return x.first_name < y.first_name;
    }
    return x.last_name < y.last_name;
  }
};
struct bracket {
  inline unsigned char operator()(const DATA_TYPE &x, size_t offset) const {
    // Sort date as a signed int, returning the appropriate byte.
    if (offset < birth_size) {
      const int bit_shift = 8 * (birth_size - offset - 1);
      unsigned char result = (x.birth & (base_mask << bit_shift)) >> bit_shift;
      // Handling the sign bit.  Unnecessary if the data is always positive.
      if (offset == 0) {
        return result ^ 128;
      }
      return result;
    }
    // Sort a signed float.  This requires reversing the order of negatives
    // because of the way floats are represented in bits.
    if (offset < first_name_offset) {
      const int bit_shift = 8 * (first_name_offset - offset - 1);
      unsigned key = float_mem_cast<float, unsigned>(x.net_worth);
      unsigned char result = (key & (base_mask << bit_shift)) >> bit_shift;
      // Handling the sign.
      if (x.net_worth < 0) {
        return 255 - result;
      }
      // Increasing positives so they are higher than negatives.
      if (offset == birth_size) {
        return 128 + result;
      }
      return result;
    }
    // Sort a string that is before the end.  This approach supports embedded
    // nulls.  If embedded nulls are not required, then just delete the "* 2"
    // and the inside of the following if just becomes:
    // return x.first_name[offset - first_name_offset];
    const unsigned first_name_end_offset =
      first_name_offset + x.first_name.size() * 2;
    if (offset < first_name_end_offset) {
      int char_offset = offset - first_name_offset;
      // This signals that the string continues.
      if (!(char_offset & 1)) {
        return 1;
      }
      return x.first_name[char_offset >> 1];
    }
    // This signals that the string has ended, so that shorter strings come
    // before longer ones.
    if (offset == first_name_end_offset) {
      return 0;
    }
    // The final string needs no special consideration.
    return x.last_name[offset - first_name_end_offset - 1];
  }
};
struct getsize {
  inline size_t operator()(const DATA_TYPE &x) const {
    return first_name_offset + x.first_name.size() * 2 + 1 +
      x.last_name.size();
  }
};

string_sort(array.begin(), array.end(), bracket(), getsize(), lessthan());

Другие примеры:

Сортировка.

Обратная струна.

Широкий набор символов.

Случай нечувствительный струнный сорт.

Сортировать структуры, используя струнный ключ и индексирующие функторы.

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

Статья String Sort раздела Boost.Sort Spreadsort может быть полезна для разработчиков на c++ и boost.

String Sort

Boost , Boost.Sort , Spreadsort

Boost C++ Libraries

String Sort

String Sort Examples