Куча и куча (серия «114 алгоритмов C++»)

Добро пожаловать в седьмую часть серии «114 алгоритмов C++». Сегодня мы поговорим об алгоритмах, которые предлагают семантику структуры данных max-кучи, и об алгоритмах, которые работают с неинициализированной памятью (не только в куче).

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

Структура данных куча

Стандарт предлагает удобную оболочку для структуры данных max-кучи через std::priority_queue. Однако при использовании std::priority_queue мы теряем доступ к базовым данным, что может быть неудобно.

Для сравнения давайте реализуем простую версию алгоритма topk, который возвращает верхние k элементов из диапазона (аналогично partial_sort_copy):

auto topk_queue(std::input_iterator auto begin, std::sentinel_for<decltype(begin)> auto end, 
                size_t k) {

    using vtype = std::iter_value_t<decltype(begin)>;
    std::priority_queue<vtype, std::vector<vtype>, std::greater<vtype>> pq;

    while (begin != end) {
        pq.push(*begin);
        if (pq.size() > k)
            pq.pop();
        ++begin;
    }

    std::vector<vtype> result(k);
    for (auto &el: result | std::views::reverse) {
        el = std::move(pq.top());
        pq.pop();
    }
    return result;    
}

При использовании приоритетной очереди мы можем использовать простой интерфейс push() и pop() (строки 8 и 10). Однако извлечение всех данных из очереди возможно только повторным применением pop() до тех пор, пока очередь не станет пустой (строка 17).

auto topk(std::input_iterator auto begin, std::sentinel_for<decltype(begin)> auto end, 
          size_t k) {
          
    std::vector<std::iter_value_t<decltype(begin)>> result;
    while (begin != end) {
        result.push_back(*begin);
        std::ranges::push_heap(result, std::greater<>{});
        if (result.size() > k) {
            std::ranges::pop_heap(result, std::greater<>{});
            result.pop_back();
        }
        ++begin;
    }
    
    std::ranges::sort_heap(result, std::greater<>{});
    return result;    
}

При использовании алгоритмов кучи нам необходимо вручную управлять базовой структурой данных (строки 6–7 и 9–10). Однако нам не нужно извлекать данные, и, кроме того, мы можем опустить последнюю sort_heap (строка 15), если первые k элементов не нужны нам в отсортированном порядке.

В нашем примере не используется std::make_heap, поскольку мы начинаем с пустого диапазона, который является действительной кучей.

Эти два тестовых алгоритма проверяют инвариант кучи. max-куча – это двоичное дерево, в котором каждый дочерний элемент равен или меньше родительского элемента. Вариант is_heap возвращает логическое значение, а is_heap_until возвращает итератор, обозначающий начальную часть диапазона, который не удовлетворяет инварианту max-кучи.

std::vector<int> data = {1, 2, 3, 4, 5, 6, 7, 8, 9};

assert(!std::is_heap(data.begin(), data.end()));
assert(std::is_heap_until(data.begin(), data.end()) == std::next(data.begin()));

std::make_heap(data.begin(), data.end());

assert(std::is_heap(data.begin(), data.end()));
assert(std::is_heap_until(data.begin(), data.end()) == data.end());

Перед применением make_heap только первый элемент находится в правильном порядке кучи (родитель 2 равен 1, что нарушает инвариант max-кучи). Следовательно, is_heap возвращает false (строка 3), а is_heap_until возвращает итератор ко второму элементу (строка 4).

После применения make_heap весь диапазон находится в порядке кучи, is_heap возвращает true (строка 8), а is_heap_until возвращает итератор конца диапазона (строка 9).

Примечательно, что is_heap(begin, is_heap_until(begin, end)) всегда будет возвращать значение true.

Работа с неинициализированной памятью

Вторая категория алгоритмов, о которых мы сегодня поговорим, – это алгоритмы, работающие с неинициализированной памятью. Как и с алгоритмами кучи, вы должны предпочесть абстракции более высокого уровня (например, ресурс полиморфной памяти). Однако при работе с неинициализированной памятью использование этих алгоритмов предпочтительнее реализации всего функционала с нуля.

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

В качестве альтернативы мы можем использовать глобальный operator new, поскольку, начиная C++17, он принимает параметр выравнивания и возвращает указатель на void. Затем мы можем привести этот указатель к нужному типу, используя static_cast.

Вот пример выделения (и освобождения) пространства для десяти объектов std::string с использованием глобального operator new:

auto* begin = static_cast<std::string*>(
                  ::operator new[](sizeof(std::string)*10, 
                                   static_cast<std::align_val_t>(alignof(std::string))));

::operator delete[](begin, static_cast<std::align_val_t>(alignof(std::string)));

В этом примере много нюансов, поэтому давайте пройдемся по ним:

• Во-первых, нам нужны sizeof(std::string)*10 байт, что является первым параметром operator new (строка 2).
• Всякий раз, выделяя сырую память, мы должны убедиться, что выполняется требование выравнивания объектов, которые мы собираемся хранить в этой памяти.
• Чтобы предотвратить коллизии разрешения перегрузки, operator new принимает выравнивание как align_val_t вместо size_t, возвращаемого alignof, поэтому нам нужно использовать дополнительный static_cast (строка 3).
• Наконец, мы должны привести указатель void к желаемому типу элемента (строка 1).
• При удалении нам нужно убедиться, что мы используем соответствующую версию (здесь – версию для массива) operator delete и выравнивания, следуя той же логике, что упоминалась ранее.

Вот пример использования буфера char в стеке:

alignas(alignof(std::string)) char buff[sizeof(std::string)*10];
auto *begin = reinterpret_cast<std::string*>(buff);

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

Важно отметить, что всё, что у нас есть в обоих фрагментах кода, – это сырая память. Объекты типа std::string не создаются и не уничтожаются. Также обратите внимание на разницу между static_cast и reinterpret_cast. static_cast предназначен для преобразования между связанными типами (void* относится ко всем типам указателей). reinterpret_cast предназначен для преобразования между несвязанными типами (char* может быть псевдонимом любого другого указателя, но не является связанным типом с std::string*).

construct_at, destroy_at

Алгоритмы construct_at и destroy_at будут создавать/уничтожать один элемент по заданному адресу. Если указаны дополнительные аргументы, construct_at передаст их конструктору объектов.

alignas(alignof(std::string)) char mem[sizeof(std::string)];
auto *ptr = reinterpret_cast<std::string*>(mem);

std::construct_at(ptr, 8, 'X');
// *ptr == "XXXXXXXX", ptr->length() == 8
std::destroy_at(ptr);

В этом примере алгоритм construct_at создает объект std::string, используя аргументы восемь и 'X' (строка 4), в результате чего получается строка, заполненная восемью копиями символа X.

uninitialized_default_construct, uninitialized_value_construct, uninitialized_fill, destroy

Эти три алгоритма охватывают инициализацию по умолчанию, инициализацию значением и инициализацию копированием элементов. destroy обеспечивает уничтожение объектов без освобождения базовой памяти.

Все эти алгоритмы имеют количественные варианты, которые принимают итератор и количество элементов:

alignas(alignof(std::string)) char buffer[sizeof(std::string)*10];
auto *begin = reinterpret_cast<std::string*>(buffer);
auto *it = begin;

std::uninitialized_default_construct_n(it, 3);
it += 3;
std::uninitialized_fill_n(it, 2, "Hello World!");
it += 2;
std::uninitialized_value_construct_n(it, 3);
it += 3;
std::uninitialized_fill_n(it, 2, "Bye World!");

// {"", "", "", "Hello World!", "Hello World!", "", "", "", "Bye World!", "Bye World!"}

std::destroy_n(begin, 10);

Для std::string нет разницы между инициализацией по умолчанию и инициализацией значением. В обоих случаях мы получаем пустую строку.

uninitialized_copy, uninitalized_move

Эти алгоритмы следуют логике алгоритмов копирования и перемещения. Однако, поскольку целевой диапазон представляет собой неинициализированную память, они превращаются в конструкторы копированием и перемещением вместо присваиваний копированием и перемещением.

alignas(alignof(std::string)) char buff1[sizeof(std::string)*5];
alignas(alignof(std::string)) char buff2[sizeof(std::string)*5];
std::vector<std::string> data = {"hello", "world", "and", "everyone", "else"};

auto *bg1 = reinterpret_cast<std::string*>(buff1);
std::uninitialized_copy(data.begin(), data.end(), bg1);
// buff1 == { "hello", "world", "and", "everyone", "else"}
// data == { "hello", "world", "and", "everyone", "else"}
std::destroy_n(bg1, 5);

auto *bg2 = reinterpret_cast<std::string*>(buff2);
std::uninitialized_move(data.begin(), data.end(), bg2); 
// buff2 == { "hello", "world", "and", "everyone", "else"}
// data == { ?, ?, ?, ?, ?}
std::destroy_n(bg2, 5);

Транзакционное поведение

Основное преимущество использования алгоритмов неинициализированной памяти заключается в том, что они правильно обрабатывают поведение транзакций. Транзакционность важна в тех случаях, когда конструктор объекта может бросить исключение. Если один из объектов не удастся создать, эти алгоритмы корректно откатятся, уничтожив уже созданные объекты.

Мы можем понаблюдать за этим поведением, создав тестовый тип, который выбрасывает исключение в конструкторе при третьем вызове:

struct Custom {
  static int cnt;
  Custom() { 
    if (++cnt >= 3)
      throw std::runtime_error("Deliberate failure."); 
    std::cout << "Custom()\n";
  }
  ~Custom() {
    std::cout << "~Custom()\n";
  }
};

int Custom::cnt = 0;

alignas(alignof(Custom)) char buffer[sizeof(Custom)*10];
auto *begin = reinterpret_cast<Custom*>(buffer);

try {
  std::uninitialized_default_construct_n(begin, 10);
  std::destroy_n(begin, 10); // not reached
} catch (std::exception& e) {
  std::cout << e.what() << "\n";
}
/* Вывод:
Custom()
Custom()
~Custom()
~Custom()
Преднамеренный сбой.
*/

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

Спасибо за чтение

В следующей статье будет рассмотрена последняя группа алгоритмов: алгоритмы поиска и алгоритмы min-max.

Теги