Тренды

C++: руководство по сортировке строк

31.07.2025

Сортировка строк на C++

Сортировка строк является фундаментальной операцией во многих задачах программирования — от организации пользовательского ввода до обработки больших наборов данных. На C++ строки сортируются несколькими способами, у каждого из них имеются преимущества. Рассмотрим нюансы этих методов, приемов и практическое применение сортировки строк на C++.

Базовая сортировка строк с std::sort

Отсортировать строку на C++ проще всего функцией std::sort из библиотеки <algorithm>. Вот простой пример:

#include <iostream>
#include <string>
#include <algorithm>

int main() {
    std::string str = "zycbwvutsrqponmlkjihgfedcba";
    std::sort(str.begin(), str.end());
    std::cout << "Sorted string: " << str << std::endl;
    return 0;
}

Вывод:

Sorted string: abcdefghijklmnopqrstuvwxyz

Этим методом символы строки сортируются в порядке возрастания их значений ASCII.

Сортировка вектора строк

Что, если нужно отсортировать несколько строк? В этом случае сортируется вектор строк:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

int main() {
    std::vector<std::string> words = {"banana", "apple", "cherry", "date"};
    std::sort(words.begin(), words.end());
    
    std::cout << "Sorted words:" << std::endl;
    for (const auto& word : words) {
        std::cout << word << std::endl;
    }
    return 0;
}

Вывод:

Sorted words:
apple
banana
cherry
date

При этом строки сортируются лексикографически, в словарном порядке.

Пользовательская сортировка: сравнение без учета регистра

А что, если отсортировать строки независимо от регистра? Этим занимается пользовательская функция-компаратор:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cctype>

bool case_insensitive_compare(const std::string& a, const std::string& b) {
    return std::lexicographical_compare(
        a.begin(), a.end(),
        b.begin(), b.end(),
        [](char a, char b) {
            return std::tolower(a) < std::tolower(b);
        }
    );
}

int main() {
    std::vector<std::string> words = {"Banana", "apple", "Cherry", "date"};
    std::sort(words.begin(), words.end(), case_insensitive_compare);
    
    std::cout << "Case-insensitive sorted words:" << std::endl;
    for (const auto& word : words) {
        std::cout << word << std::endl;
    }
    return 0;
}

Вывод:

Case-insensitive sorted words:
apple
Banana
Cherry
date

Этим пользовательским компаратором при сортировке игнорируется регистр, исходная заглавная буква каждого слова сохраняется.

Сортировка строк по длине

А вот как строки сортируются по длине:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

int main() {
    std::vector<std::string> words = {"short", "very long string", "medium"};
    std::sort(words.begin(), words.end(), 
              [](const std::string& a, const std::string& b) {
                  return a.length() < b.length();
              });
    
    std::cout << "Strings sorted by length:" << std::endl;
    for (const auto& word : words) {
        std::cout << word << std::endl;
    }
    return 0;
}

Вывод:

Strings sorted by length:
short
medium
very long string

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

Реальное применение: сортировка имен

Рассмотрим практический пример с сортировкой списка имен, сначала сортируем по фамилии. Затем по имени, если фамилии одинаковые.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <sstream>

struct Name {
    std::string first;
    std::string last;
};

std::vector<Name> parse_names(const std::vector<std::string>& full_names) {
    std::vector<Name> names;
    for (const auto& full_name : full_names) {
        std::istringstream iss(full_name);
        Name name;
        iss >> name.first >> name.last;
        names.push_back(name);
    }
    return names;
}

int main() {
    std::vector<std::string> full_names = {
        "John Doe", "Jane Doe", "Alice Smith", "Bob Johnson"
    };

    auto names = parse_names(full_names);

    std::sort(names.begin(), names.end(),
              [](const Name& a, const Name& b) {
                  if (a.last != b.last) {
                      return a.last < b.last;
                  }
                  return a.first < b.first;
              });

    std::cout << "Sorted names:" << std::endl;
    for (const auto& name : names) {
        std::cout << name.first << " " << name.last << std::endl;
    }

    return 0;
}

Вывод:

Sorted names:
Jane Doe
John Doe
Bob Johnson
Alice Smith

В этом примере показана сортировка по критериям: сначала по фамилии, затем по имени.

Обработка строк «Юникода»

Сортировка строк «Юникода» сложнее. В стандартной библиотеке C++ нет встроенной поддержки кодировки символов «Юникода», воспользуемся внешней библиотекой International Components for Unicode. Вот упрощенный пример ее применения:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <unicode/unistr.h>
#include <unicode/coll.h>

bool compare_unicode(const std::string& a, const std::string& b) {
    UErrorCode status = U_ZERO_ERROR;
    icu::Collator* collator = icu::Collator::createInstance(icu::Locale(""), status);
    
    if (U_FAILURE(status)) {
        std::cerr << "Failed to create collator" << std::endl;
        return false;
    }

    icu::UnicodeString ua = icu::UnicodeString::fromUTF8(a);
    icu::UnicodeString ub = icu::UnicodeString::fromUTF8(b);

    UCollationResult result = collator->compare(ua, ub, status);
    delete collator;

    if (U_FAILURE(status)) {
        std::cerr << "Comparison failed" << std::endl;
        return false;
    }

    return result == UCOL_LESS;
}

int main() {
    std::vector<std::string> words = {"café", "cafe", "résumé", "resume"};
    std::sort(words.begin(), words.end(), compare_unicode);

    std::cout << "Unicode-aware sorted words:" << std::endl;
    for (const auto& word : words) {
        std::cout << word << std::endl;
    }

    return 0;
}

Примечание: в этом примере требуются ссылки на библиотеку International Components for Unicode, может понадобиться дополнительная настройка.

Производительность

Сортировка большого количества строк или очень длинных строк сказывается на производительности. Вот рекомендации:

Чтобы избежать лишнего копирования, для ссылок на строки только для чтения применяйте std::string_view.
Чтобы сохранить относительный порядок эквивалентных элементов, воспользуйтесь стабильным алгоритмом сортировки, например std::stable_sort.
Для очень больших наборов данных применяйте алгоритмы параллельной сортировки, доступные в версии C++17 и новее.

Вот простой тест производительности для сравнения различных методов сортировки:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <chrono>
#include <random>

std::vector<std::string> generate_random_strings(int count, int length) {
    std::vector<std::string> result;
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(97, 122);  // Строчные символы ASCII

    for (int i = 0; i < count; ++i) {
        std::string str;
        for (int j = 0; j < length; ++j) {
            str += static_cast<char>(dis(gen));
        }
        result.push_back(str);
    }

    return result;
}

template<typename Func>
double benchmark(Func f, std::vector<std::string>& data) {
    auto start = std::chrono::high_resolution_clock::now();
    f(data.begin(), data.end());
    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> diff = end - start;
    return diff.count();
}

int main() {
    const int STRING_COUNT = 100000;
    const int STRING_LENGTH = 10;

    auto data = generate_random_strings(STRING_COUNT, STRING_LENGTH);
    auto data_copy = data;  // Для «stable_sort»

    std::cout << "Sorting " << STRING_COUNT << " strings of length " << STRING_LENGTH << std::endl;

    double sort_time = benchmark(std::sort<std::vector<std::string>::iterator>, data);
    std::cout << "std::sort time: " << sort_time << " seconds" << std::endl;

    double stable_sort_time = benchmark(std::stable_sort<std::vector<std::string>::iterator>, data_copy);
    std::cout << "std::stable_sort time: " << stable_sort_time << " seconds" << std::endl;

    return 0;
}

В этом тесте сравниваются std::sort и std::stable_sort. Результаты варьируются в зависимости от системы и характера данных.

Заключение

Сортировка строк на C++ — это универсальная операция со многими сценариями применения. Понимание способов сортировки — от базовой лексикографической до сложной многокритериальной — позволяет эффективно справляться с разнообразными задачами обработки строк.

При выборе метода сортировки всегда учитывайте конкретные требования задачи. Важен ли регистр? Нужно ли корректно работать с «Юникодом»? Проводится ли многокритериальная сортировка?

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

C++: руководство по сортировке строк

Сортировка строк на C++

Базовая сортировка строк с std::sort

Сортировка вектора строк

Пользовательская сортировка: сравнение без учета регистра

Сортировка строк по длине

Реальное применение: сортировка имен

Обработка строк «Юникода»

Производительность

Заключение

Читайте также

7 типичных ошибок в Go-интерфейсах

Встроенная поддержка контейнеров для .NET 7 — контейнеризация приложений .NET без Dockerfile

Хотите стать счастливым и продуктивным программистом? Используйте эти 5 методов из...

Тесты

Насколько хорошо вы разбираетесь в Android?

Являетесь ли вы компьютерным гиком?

Насколько хорошо вы разбираетесь в Go?