C++ Структуры данных

C++ предоставляет множество структур данных — от базовых, таких как массивы, структуры и классы, до продвинутых контейнеров STL, таких какvector、mapиunordered_mapи т. д.

Ниже подробно описаны часто используемые структуры данных в C++, а также их особенности и применение.

1. Массив

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

Особенности：

  • Фиксированный размер; после объявления размер нельзя изменить.
  • Прямой доступ к элементам с временной сложностью O(1).
  • Подходит для обработки коллекций известного размера с одинаковыми типами элементов.

Пример

int arr[5] = {1, 2, 3, 4, 5};
cout << arr[0]; // Вывод первого элемента

Преимущества и недостатки：

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

2. Структура

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

Особенности：

  • Может содержать переменные-члены разных типов.
  • Обеспечивает базовую инкапсуляцию данных, но с ограниченной функциональностью.

Пример：

Пример

struct Person {
    string name;
    int age;
};
Person p = {"Alice", 25};
cout << p.name << endl; // Вывод Alice

3. Класс

Классы — это основная структура для объектно-ориентированного программирования в C++, позволяющая определять переменные-члены и функции-члены. По сравнению сstructПохожи, но более мощные, поддерживают такие возможности, как наследование, инкапсуляция и полиморфизм.

Особенности：

  • Может включать переменные-члены, функции-члены, конструкторы и деструкторы.
  • Поддерживает объектно-ориентированные возможности, такие как инкапсуляция, наследование и полиморфизм.

Пример

class Person {
private:
    string name;
    int age;
public:
    Person(string n, int a) : name(n), age(a) {}
    void printInfo() {
        cout << "Имя: " << name << ", Возраст: " << age << endl;
    }
};
Person p("Bob", 30);
p.printInfo(); // Вывод: Имя: Bob, Возраст: 30

4. Связный список

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

Особенности：

  • Динамически изменяет размер, нет необходимости заранее задавать вместимость.
  • Операции вставки и удаления эффективны, временная сложность — O(1) (при работе с головой или хвостом списка).
  • Линейный поиск с временной сложностью O(n).

Пример (односвязный список)

struct Node {
    int data;
    Node* next;
};
Node* head = nullptr;
Node* newNode = new Node{10, nullptr};
head = newNode; // Вставить новый узел

Преимущества и недостатки：

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

5. Стек

Стек — это структура данных «последним пришёл — первым вышел» (LIFO), обычно используется в таких сценариях, как рекурсия и поиск в глубину.

Особенности：

  • Разрешает операции вставки и удаления только на вершине стека.
  • Временная сложность — O(1).

Пример

stack<int> s;
s.push(1);
s.push(2);
cout << s.top(); // Вывод 2
s.pop();

Преимущества и недостатки：

  • Преимущество: простые операции, высокая эффективность.
  • Недостатки: операции можно выполнять только на вершине; для доступа к другим элементам требуется извлечь верхний элемент.

6. Очередь

Очередь — это структура данных «первым пришёл — первым вышел» (FIFO), обычно используемая в таких сценариях, как поиск в ширину и планирование задач.

Особенности：

  • Операции вставки выполняются в хвосте очереди, а операции удаления — в голове.
  • Временная сложность — O(1).

Пример

queue<int> q;
q.push(1);
q.push(2);
cout << q.front(); // Вывод 1
q.pop();

Преимущества и недостатки：

  • Преимущества: подходит для сценариев, в которых данные обрабатываются в порядке поступления, например для планирования задач.
  • Недостаток: невозможен произвольный доступ к элементам.

7. Двусторонняя очередь (Deque)

deque позволяет выполнять операции вставки и удаления на обоих концах, объединяя возможности стека и очереди.

Особенности：

  • Позволяет выполнять вставку и удаление на обоих концах.
  • Временная сложность — O(1).

Пример

deque<int> dq;
dq.push_back(1);
dq.push_front(2);
cout << dq.front(); // Вывод 2
dq.pop_front();

Преимущества и недостатки：

  • Преимущество: гибкие двунаправленные операции.
  • Недостатки: большее использование пространства, подходит для сценариев, требующих частых операций на обоих концах.

8. Хеш-таблица

Хеш-таблица — это структура данных, которая хранит данные в виде пар ключ-значение, поддерживая быстрый поиск, вставку и удаление. В C++,unordered_mapРеализация хеш-таблицы.

Особенности：

  • Использует хеш-функцию для быстрого поиска элементов; временная сложность — O(1).
  • Не гарантирует порядок элементов.

Пример

unordered_map<string, int> hashTable;
hashTable["apple"] = 10;
cout << hashTable["apple"]; // Вывод 10

Преимущества и недостатки：

  • Преимущества: высокая эффективность операций поиска, вставки и удаления.
  • Недостатки: не гарантирует порядок элементов, а производительность снижается при возникновении хеш-коллизий.

9. Map

mapЭто упорядоченный контейнер пар ключ-значение, реализованный с помощью красно-чёрного дерева. По сравнению сunordered_mapВ отличие от него, он гарантирует порядок ключей; временная сложность поиска, вставки и удаления — O(log n).

Особенности：

  • Гарантирует, что элементы упорядочены по их ключам.
  • Реализован с помощью двоичного дерева поиска.

Пример

map<string, int> myMap;
myMap["apple"] = 10;
cout << myMap["apple"]; // Вывод 10

Преимущества и недостатки：

  • Преимущества: элементы упорядочены, подходит для сценариев, в которых необходимо обрабатывать данные по порядку.
  • Недостаток: более низкая производительность, чемunordered_mapНемного ниже.

10. Set

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

Особенности：

  • Гарантирует уникальность элементов.
  • Элементы автоматически располагаются в порядке возрастания.
  • Временная сложность — O(log n).

Пример

set<int> s;
s.insert(1);
s.insert(2);
cout << *s.begin(); // Вывод 1

Преимущества и недостатки：

  • Преимущество: автоматическая сортировка и гарантия уникальности.
  • Недостатки: эффективность вставки и удаления ниже, чем у неупорядоченных множеств.

11. Динамический массив (вектор)

vectorЭто реализация динамического массива, предоставляемая стандартной библиотекой C++, которая может динамически расширять вместимость и поддерживает произвольный доступ.

Особенности：

  • Динамическое изменение размера.
  • Поддерживает произвольный доступ с временной сложностью O(1).
  • Когда ёмкости недостаточно, он динамически расширяется, с амортизированной временной сложностью O(1).

Пример

vector<int> v;
v.push_back(1);
v.push_back(2);
cout << v[0]; // Вывод 1

Преимущества и недостатки：

  • Преимущества: поддерживает произвольный доступ и динамическое расширение.
  • Недостатки: низкая эффективность при вставке или удалении элементов в середине.
Другие расширения