Тренды

C++: подробное руководство по cортированным векторам

11.09.2025

В сортированных векторах на C++ сочетаются удобство векторов и эффективность сортированных структур данных.

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

Изучим эффективное использование этих сортированных векторов в проектах на C++.

Сортированные векторы

Сортированный вектор — это не отдельный контейнер на C++, а обычный std::vector, сохраняемый в отсортированном состоянии. Этим подходом сочетаются преимущества непрерывного сохранения в памяти из векторов и возможности быстрого — благодаря сортируемости — поиска.

Вот простой пример создания и сохранения сортированного вектора:

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

int main() {
    std::vector<int> sorted_vec = {1, 3, 5, 7, 9};

    // Добавление нового элемента
    int new_element = 4;
    auto it = std::lower_bound(sorted_vec.begin(), sorted_vec.end(), new_element);
    sorted_vec.insert(it, new_element);

    // Вывод сортированного вектора
    for (int num : sorted_vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

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

Ключевые операции над сортированными векторами

Рассмотрим основные операции, выполняемые с сортированными векторами.

Вставка элементов

Чтобы вставить элемент и сохранить порядок сортировки, при помощи std::lower_bound находится правильная позиция, затем используется vector::insert:

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

void insert_sorted(std::vector<int>& vec, int element) {
    auto it = std::lower_bound(vec.begin(), vec.end(), element);
    vec.insert(it, element);
}

int main() {
    std::vector<int> sorted_vec = {1, 3, 5, 7, 9};
    
    insert_sorted(sorted_vec, 4);
    insert_sorted(sorted_vec, 8);

    for (int num : sorted_vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Этой функцией эффективно вставляются новые элементы при сохранении порядка сортировки.

Поиск элементов

Для быстрого поиска используется std::binary_search:

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

int main() {
    std::vector<int> sorted_vec = {1, 3, 5, 7, 9};

    int search_element = 5;
    bool found = std::binary_search(sorted_vec.begin(), sorted_vec.end(), search_element);

    std::cout << "Element " << search_element << " is " 
              << (found ? "found" : "not found") << " in the vector." << std::endl;

    return 0;
}

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

Удаление элементов

Удаляемый элемент сначала обнаруживается при помощи std::lower_bound, затем удаляется благодаря vector::erase:

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

void remove_element(std::vector<int>& vec, int element) {
    auto it = std::lower_bound(vec.begin(), vec.end(), element);
    if (it != vec.end() && *it == element) {
        vec.erase(it);
    }
}

int main() {
    std::vector<int> sorted_vec = {1, 3, 5, 7, 9};
    
    remove_element(sorted_vec, 5);

    for (int num : sorted_vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Этой функцией элемент эффективно удаляется с сохранением порядка сортировки.

Практические применения сортированных векторов

Рассмотрим реальные сценарии, в которых сортированные векторы приходятся особенно кстати.

Реализация простого словаря

Сортированным вектором эффективно реализуется словарь от малого до среднего размера:

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

struct DictionaryEntry {
    std::string word;
    std::string definition;

    bool operator<(const DictionaryEntry& other) const {
        return word < other.word;
    }
};

class Dictionary {
private:
    std::vector<DictionaryEntry> entries;

public:
    void add_word(const std::string& word, const std::string& definition) {
        DictionaryEntry new_entry{word, definition};
        auto it = std::lower_bound(entries.begin(), entries.end(), new_entry);
        entries.insert(it, new_entry);
    }

    std::string find_definition(const std::string& word) {
        DictionaryEntry search_entry{word, ""};
        auto it = std::lower_bound(entries.begin(), entries.end(), search_entry);
        if (it != entries.end() && it->word == word) {
            return it->definition;
        }
        return "Word not found";
    }
};

int main() {
    Dictionary dict;
    dict.add_word("apple", "A round fruit with red or green skin");
    dict.add_word("banana", "A long curved fruit with a yellow skin");
    dict.add_word("cherry", "A small round fruit with a single hard seed");

    std::cout << "Definition of 'banana': " << dict.find_definition("banana") << std::endl;
    std::cout << "Definition of 'grape': " << dict.find_definition("grape") << std::endl;

    return 0;
}

С такой реализацией выполняется быстрый поиск слов, что для словаря немаловажно.

Управление списком лидеров

Сортированными векторами отлично реализуется список лидеров в играх:

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

struct Player {
    std::string name;
    int score;

    bool operator<(const Player& other) const {
        return score > other.score; // Сортируется в порядке убывания
    }
};

class Leaderboard {
private:
    std::vector<Player> players;
    const size_t max_size;

public:
    Leaderboard(size_t size) : max_size(size) {}

    void add_score(const std::string& name, int score) {
        Player new_player{name, score};
        auto it = std::lower_bound(players.begin(), players.end(), new_player);
        players.insert(it, new_player);

        if (players.size() > max_size) {
            players.pop_back();
        }
    }

    void display() {
        std::cout << std::setw(4) << "Rank" << std::setw(20) << "Name" << std::setw(10) << "Score" << std::endl;
        std::cout << std::string(34, '-') << std::endl;
        for (size_t i = 0; i < players.size(); ++i) {
            std::cout << std::setw(4) << i+1 
                      << std::setw(20) << players[i].name 
                      << std::setw(10) << players[i].score << std::endl;
        }
    }
};

int main() {
    Leaderboard leaderboard(5);  // Сохраняется пять наивысших результатов

    leaderboard.add_score("Alice", 100);
    leaderboard.add_score("Bob", 85);
    leaderboard.add_score("Charlie", 95);
    leaderboard.add_score("David", 110);
    leaderboard.add_score("Eve", 90);
    leaderboard.add_score("Frank", 105);

    leaderboard.display();

    return 0;
}

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

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

Несмотря на преимущества сортированных векторов, важно понимать и нюансы производительности:

Вставки и удаления — это операции O(n), поскольку требуется перемещать элементы.
Поиски же — O(log n) при использовании алгоритмов двоичного поиска.
Сортированные векторы хороши для операций с преобладанием считываний и периодическими записями.
Для очень больших наборов данных с частыми вставками/удалениями используйте другие структуры данных, например std::set или std::map.

Вот простой тест производительности для сравнения поиска сортированного и несортированного векторов:

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

std::vector<int> generate_random_vector(size_t size) {
    std::vector<int> vec(size);
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(1, 1000000);

    for (size_t i = 0; i < size; ++i) {
        vec[i] = dis(gen);
    }
    return vec;
}

int main() {
    const size_t size = 1000000;
    std::vector<int> unsorted_vec = generate_random_vector(size);
    std::vector<int> sorted_vec = unsorted_vec;
    std::sort(sorted_vec.begin(), sorted_vec.end());

    int search_element = unsorted_vec[size / 2];  // Средний элемент

    // Тестируется несортированный вектор
    auto start = std::chrono::high_resolution_clock::now();
    auto it = std::find(unsorted_vec.begin(), unsorted_vec.end(), search_element);
    auto end = std::chrono::high_resolution_clock::now();
    auto unsorted_duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);

    // Тестируется сортированный вектор
    start = std::chrono::high_resolution_clock::now();
    bool found = std::binary_search(sorted_vec.begin(), sorted_vec.end(), search_element);
    end = std::chrono::high_resolution_clock::now();
    auto sorted_duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);

    std::cout << "Unsorted vector search time: " << unsorted_duration.count() << " microseconds" << std::endl;
    std::cout << "Sorted vector search time: " << sorted_duration.count() << " microseconds" << std::endl;

    return 0;
}

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

Заключение

Сортированные векторы на C++ — это практичное решение для управления упорядоченными коллекциями данных. В нем простота векторов сбалансированно сочетается с быстрым поиском сортированных структур данных.

Благодаря эффективной реализации сортированных векторов повышаются производительность и удобство восприятия кода на C++ во многих реальных сценариях.

C++: подробное руководство по cортированным векторам

Сортированные векторы

Ключевые операции над сортированными векторами

Вставка элементов

Поиск элементов

Удаление элементов

Практические применения сортированных векторов

Реализация простого словаря

Управление списком лидеров

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

Заключение

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

Потрясающие функции Next.js 15

Автоматизируем создание отчета о расходах с помощью Python

В чем магия ожидаемых результатов?

Тесты

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

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

Насколько вы знакомы с языком Swift