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

Динамический массив и std::vector в C и C++

В этом уроке вы реализуете на C динамический массив, который сам растёт при добавлении элементов, и сравните его с std::vector в C++.

Введение

Динамический массив (dynamic array) - это массив, который при необходимости может расти. В нём различают два понятия: число хранимых элементов (size) и выделенное место (capacity). Когда массив заполнен, программа выделяет область побольше, обычно вдвое, и переносит туда данные.

Главное

Определите условия, которые всегда должны выполняться (инварианты), прежде чем писать операции.
Обрабатывайте случаи пустой и заполненной структуры и ошибки выделения памяти.
Оценивайте вместе сложность и управление памятью для каждой операции.

Как это работает

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

Примеры кода на C и C++

Запустить →

main.c

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    size_t size = 0, capacity = 2;
    int *values = malloc(capacity * sizeof *values);
    if (!values) return 1;
    for (int value = 1; value <= 5; ++value) {
        if (size == capacity) {
            capacity *= 2;
            int *grown = realloc(values, capacity * sizeof *values);
            if (!grown) {
                free(values);
                return 1;
            }
            values = grown;
        }
        values[size++] = value * value;
    }
    printf("size=%zu capacity=%zu last=%d\n",
           size, capacity, values[size - 1]);
    free(values);
}

Результат выполнения

size=5 capacity=8 last=25

C++

Запустить →

main.cpp

#include <iostream>
#include <vector>

int main() {
    std::vector<int> values;
    for (int value = 1; value <= 5; ++value) {
        values.push_back(value * value);
    }
    std::cout << "size=" << values.size()
              << " last=" << values.back() << '\n';
}

Результат выполнения

size=5 last=25

Сравнение C и C++

В версии на C, когда size достигает capacity, программа удваивает capacity и вызывает realloc, чтобы увеличить память. Результат realloc сохраняется во временный указатель grown, чтобы при неудачном выделении старую память ещё можно было освободить. std::vector в C++ инкапсулирует именно эту стратегию роста и, кроме того, сам освобождает память, поддерживает итераторы и безопасен при исключениях.

Данные (struct) и операции разделены, а память выделяется и освобождается вручную.

C++

Классы и контейнеры защищают целостность данных и сами управляют своими ресурсами.

Упражнения для практики

Запустите обе версии, а затем измените код, чтобы увидеть разницу в безопасности, которую даёт каждый язык.

Добавьте тесты для пустого состояния и момента, когда достигнута максимальная ёмкость.
Напишите освобождение памяти и убедитесь, что утечек нет.
Сравните сложность с аналогичным контейнером стандартной библиотеки.

Попрактикуйтесь на задаче

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

Все задачи