Buffer c что это

What is buffer concept in C++?

When we write it actually unties cout and cin . We have to flush cout manually or when buffer is full.

I cannot get buffer concept here.

2 Answers 2

What Does it Mean to Buffer in C++?

Buffer is a generic term that refers to a block of memory that serves as a temporary placeholder. You might encounter the term in your computer, which uses RAM as a buffer, or in video streaming where a section of the movie you are streaming downloads to your device to stay ahead of your viewing. Computer programmers use buffers as well.

Data Buffers in Programming

In computer programming, data can be placed in a software buffer before it is processed. Because writing data to a buffer is much faster than a direct operation, using a buffer while programming in C and C++ makes a lot of sense and speeds up the calculation process. Buffers come in handy when a difference exists between the rate data is received and the rate it is processed.

Buffer vs. Cache

A buffer is temporary storage of data that is on its way to other media or storage of data that can be modified non-sequentially before it is read sequentially. It attempts to reduce the difference between input speed and output speed. A cache also acts as a buffer, but it stores data that is expected to be read several times to reduce the need to access slower storage.

How to Create a Buffer in C++

Usually, when you open a file a buffer is created. When you close the file, the buffer is flushed. When working in C++, you can create a buffer by allocating memory in this manner:

When you want to free up the memory allocated to a buffer, you do so like this:

Note: If your system is low on memory, the benefits of buffering suffer. At this point, you have to find a balance between the size of a buffer and the available memory of your computer.

Что такое кольцевой буфер?

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

Теоретические основы буфера

Пользователю легче сделать выбор эффективной структуры массивов после понимания основополагающей теории. Циклический буфер — структура данных, где массив обрабатывается и визуализируется в виде циклов, то есть индексы возвращаются к 0 после достижения длины массива. Это делается с помощью двух указателей на массив: «head» и «tail». Когда данные добавляются в буфер, указатель заголовка перемещается вверх. Точно так же, когда они удаляются, то хвост тоже перемещается вверх. Определение головы, хвоста, направления их движения, места записи и чтения зависят от реализации схемы.

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

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

Еще один вопрос, который возникает в отношении циклического буфера. Нужно ли сбрасывать новые данные или перезаписывать существующие, когда он заполнен? Специалисты утверждают, что нет явного преимущества одного над другим, а его реализация зависит от конкретной ситуации. Если последние имеют больше значимости для приложения, используют метод перезаписи. С другой стороны, если они обрабатываются в режиме «первым пришел — первым обслужен», то отбрасывают новые, когда кольцевой буфер заполнен.

Реализация цикличной очереди

Приступая к реализации, определяют типы данных, а затем методы: core, push и pop. В процедурах «push» и «pop» вычисляют «следующие» точки смещения для местоположения, в котором будет происходить текущая запись и чтение. Если следующее местоположение указывает на хвост, значит, буфер заполнен и данные больше не записываются. Точно так же, когда «head» равен «tail», он пуст и из него ничего не читается.

Стандартный вариант использования

Вспомогательная процедура вызывается процессом приложения для извлечения данных из кольцевого буфера Java. Она должен быть включена в критические разделы, если считывают контейнер более одного потока. Хвост перемещается к следующему смещению до того, как информация будет прочитана, поскольку каждый блок составляет один байт и резервируется аналогичное количество в буфере, когда объем полностью загружен. Но в более продвинутых реализациях циклического накопителя единичные разделы необязательно должны быть одинакового размера. В таких случаях стараются сохранить даже последний байт, добавив больше проверок и границ.

В таких схемах, если хвост передвигается перед чтением, информация, которая должна быть прочитана, потенциально может быть перезаписана вновь выдвинутыми данными. В общем случае рекомендуется сначала читать, а затем перемещать хвостовой указатель. Вначале определяют длину буфера, а затем создают экземпляр «circ_bbuf_t» и назначают указатель «maxlen». При этом контейнер должен быть глобальным или находиться в стеке. Так, например, если нужен кольцевой буфер длиной 32 байта, выполняют в приложении следующее (см. рисунок ниже).

Спецификация функциональных требований

Тип данных «ring_t» будет типом данных, который содержит указатель на буфер, размер его, индекс заголовка и хвоста, счетчик данных.

Функция инициализации «ring_init ()» инициализирует буфер на основе получения указателя на структуру контейнера, созданного вызывающей функцией, имеющей предопределенный размер.

Функция добавления звонка «ring_add ()» добавит байт в следующий доступный пробел в буфере.

Функция удаления кольца «ring_remove ()» удалит байт из самого старого допустимого места в контейнере.

Ring peek в функции «ring_peek ()» будет считывать число байтов «uint8_t ‘count’» из кольцевого буфера в новый, предоставленный в качестве параметра, без удаления каких-либо значений, считанных из контейнера. Он вернет количество фактически прочитанных байтов.

Функция очистки кольца «ring_clear ()» установит «Tail» равным «Head» и загрузит «0» во все позиции буфера.

Создание буфера в C/C ++

Из-за ограниченности ресурсов встроенных систем структуры данных с циклическим буфером можно найти в большинстве проектов фиксированного размера, которые работают так, как если бы память по своей природе была непрерывной и циклической. Данные не нужно переставлять, поскольку память генерируется и используется, а корректируются указатели головы/хвоста. Во время создания циклической буферной библиотеки нужно, чтобы пользователи работали с библиотечными API, а не изменяли структуру напрямую. Поэтому используют инкапсуляцию кольцевого буфера на «Си». Таким образом разработчик сохранит библиотечную реализацию, изменяя ее по мере необходимости, не требуя, чтобы конечные пользователи также обновляли ее.

Пользователи не могут работать с «circular_but_t» указателем, создается тип дескриптора, который можно использовать вместо него. Это избавит от необходимости приводить указатель в реализации функции «.typedefcbuf_handle_t». Разработчикам нужно собрать API для библиотеки. Они взаимодействуют с библиотекой кольцевого буфера «C», используя непрозрачный тип дескриптора, который создается во время инициализации. Обычно выбирают «uint8_t» в качестве базового типа данных. Но можно использовать любой конкретный тип, проявляя осторожность, чтобы правильно обрабатывать базовый буфер и количество байтов. Пользователи взаимодействуют с контейнером, выполняя обязательные процедуры:

1. Инициализировать контейнер и его размер.
2. Сбросить круговой контейнер.
3. Добавлять данные в кольцевой буфер на «Си».
4. Получать следующее значение из контейнера.
5. Затребовать информацию о текущем количестве элементов и максимальной емкости.

И «полный», и «пустой» случаи выглядят одинаково: «head» и «tail», указатели равны. Существует два подхода, различающие полный и пустой:

1. Полное состояние tail + 1 == head.
2. Пустое состояние head == tail.

Реализация библиотечных функций

Для создания кругового контейнера используют его структуру для управления состоянием. Чтобы сохранить инкапсуляцию, структура определяется внутри библиотечного «.c» файла, а не в заголовке. При установке нужно будет отслеживать:

1. Базовый буфер данных.
2. Максимальный размер.
3. Текущую позицию головы, увеличивающуюся при добавлении.
4. Текущий хвост, увеличивающийся при удалении.
5. Флаг, указывающий, заполнен ли контейнер или нет.

Теперь, когда контейнер спроектирован, реализуют библиотечные функции. Каждый из API требует инициализированного дескриптора буфера. Вместо того чтобы засорять код условными утверждениями, применяют утверждения для обеспечения выполнения требований API в стиле.

Реализация не будет являться поточно-ориентированной, если в базовую библиотеку циклических хранилищ не были добавлены блокировки. Для инициализации контейнера у API есть клиенты, которые предоставляют базовый размер буфера, поэтому создают его на стороне библиотеки, например, для простоты «malloc». Системы, которые не могут использовать динамическую память, должны изменить «init» функцию, чтобы использовать другой метод, например, такой как выделение из статического пула контейнеров.

Другой подход заключается в нарушении инкапсуляции, что позволяет пользователям статически объявлять структуры контейнеров. В этом случае «circular_buf_init» необходимо обновить, чтобы взять указатель или «init», создать структуру стека и вернуть ее. Однако, поскольку инкапсуляция нарушена, пользователи смогут изменять ее без библиотечных процедур. После того как создан контейнер, заполняют значения и вызывают «reset». Прежде чем вернуться из «init», система гарантирует, что контейнер создан в пустом состоянии.

Добавление и удаление данных

Добавление и удаление данных из буфера требует манипуляций с «head»- и «tail»-указателями. При добавлении в контейнер вставляют новое значение в текущем «head»-месте и продвигают его. Когда удаляют, получают значение текущего «tail»-указателя и продвигают «tail». Если нужно продвинуть «tail»-указатель, а также «head», необходимо проверить, вызывает ли вставка значения «full». Когда буфер уже заполнен, продвигают «tail» на шаг впереди «head».

После того как указатель был продвинут, заполняют «full»-флаг, проверяя равенство «head == tail». Модульное использование оператора приведет к тому, что «head» и «tail» сбросят значения в «0», когда будет достигнут максимальный размер. Это гарантирует, что «head» и «tail» всегда будут действительными индексами базового контейнера данных: «static void advance_pointer (cbuf_handle_t cbuf)». Можно создать аналогичную вспомогательную функцию, которая вызывается при удалении значения из буфера.

Интерфейс шаблонного класса

Для того чтобы реализация C ++ поддерживала любые типы данных, выполняют шаблон:

1. Сброс буфера для очистки.
2. Добавление и удаление данных.
3. Проверка полного/пустого состояния.
4. Проверка текущего количества элементов.
5. Проверка общей емкости контейнера.
6. Чтобы не оставить никаких данных после уничтожения буфера, используют интеллектуальные указатели C ++, чтобы гарантировать, что пользователи могут управлять данными.

В этом примере буфер C ++ имитирует большую часть логики реализации C, но в результате получается гораздо более чистый и многократно используемый дизайн. Кроме того, контейнер C ++ использует «std::mutex» для обеспечения поточно-ориентированной реализации. При создании класса выделяют данные для основного буфера и устанавливают его размер. Это устраняет накладные расходы, требуемые с реализацией C. В отличие от нее, конструктор C ++ не вызывает «reset», поскольку указывают начальные значения для переменных-членов, круговой контейнер запускается в правильном состоянии. Поведение сброса возвращает буфер в пустое состояние. В реализации циклического контейнера C ++ «size» и «capacity» сообщает количество элементов в очереди, а не размер в байтах.

Драйвер UART STM32

После запуска буфера, он должен быть интегрирован в драйвер UART. Сначала как глобальный элемент в файле, поэтому необходимо объявить:

• «descriptor_rbd» и буферную память «_rbmem: static rbd_t _rbd»;
• «static char _rbmem [8]».

Поскольку это драйвер UART, где каждый символ должен быть 8-разрядным, создание массива символов допустимо. Если используется 9- или 10-битный режим, то каждый элемент должен быть «uint16_t». Контейнер рассчитывается таким образом, чтобы избежать потери данных.

Часто модули очередей содержат статистическую информацию, позволяющую отслеживать максимальное использование. В функции инициализации «uart_init» буфер должен быть инициализирован путем вызова «ring_buffer_init» и передачи структуры атрибутов с каждым членом, которому назначены обсуждаемые значения. Если он успешно инициализируется, модуль UART выводится из сброса, прерывание приема разрешено в IFG2.

Вторая функция, которая должна быть изменена, — это «uart_getchar». Считывание полученного символа из периферийного устройства UART заменяется чтением из очереди. Если очередь пуста, функция должна вернуть -1. Далее нужно внедрить UART для получения ISR. Открывают файл заголовка «msp430g2553.h», прокручивают вниз до секции векторов прерываний, где находят вектор с именем USCIAB0RX. Именование подразумевает, что это оно используется модулями USCI A0 и B0. Статус прерывания приема USCI A0 можно прочитать из IFG2. Если он установлен, флаг должен быть очищен, а данные в приемном отсеке помещены в буфер с помощью «ring_buffer_put».

Репозиторий данных UART

Этот репозиторий дает информацию о том, как считывать данные по UART с использованием DMA, когда количество байтов для приема заранее неизвестно. В семействе микроконтроллеров кольцевой буфер STM32 может работать в разных режимах:

1. Режим опроса (без DMA, без IRQ)- приложение должно опрашивать биты состояния, чтобы проверить, был ли принят новый символ, и прочитать его достаточно быстро, чтобы получить все байты. Очень простая реализация, но никто не использует ее в реальной жизни. Минусы — легко пропустить полученные символы в пакетах данных, работает только для низких скоростей передачи.
2. Режим прерывания (без DMA) — кольцевой буфер UART запускает прерывание, и ЦПУ переходит к служебной программе для обработки приема данных. Наиболее распространенный подход во всех приложениях сегодня, хорошо работает в диапазоне средних скоростей. Минусы — процедура обработки прерывания выполняется для каждого полученного символа, может останавливать другие задачи в высокопроизводительных микроконтроллерах с большим количеством прерываний и одновременно операционную систему при получении пакета данных.
3. Режим DMA используется для передачи данных из регистра USART RX в пользовательскую память на аппаратном уровне. На этом этапе взаимодействие с приложением не требуется, за исключением необходимости обработки полученных приложением данных. Может очень легко работать с операционными системами. Оптимизирован для высоких скоростей передачи данных > 1Mbps и маломощных приложений, в случае больших пакетов данных увеличение размера буфера может улучшить функциональность.

Реализация в ARDUINO

Кольцевой буфер Arduino относится как к проектированию плат, так и к среде программирования, которая используется для работы. Ядром Arduino является микроконтроллер серии Atmel AVR. Именно AVR выполняет большую часть работы, и во многих отношениях плата Arduino вокруг AVR представляет функциональность — легко подключаемые контакты, USB-последовательный интерфейс для программирования и связи.

Многие из обычных плат Arduino в настоящее время используют кольцевой буфер c ATmega 328, более старые платы использовали ATmega168 и ATmega8. Платы вроде Mega выбирают более сложные варианты, такие как 1280 и аналогичные. Чем быстрее Due и Zero, тем лучше используйте ARM. Существует около десятка различных плат Arduino с именами. Они могут иметь разное количество флеш-памяти, ОЗУ и порты ввода-вывода с кольцевым буфером AVR.

Переменную «roundBufferIndex» используют для хранения текущей позиции, а при добавлении в буфер произойдет ограничение массива.

Это результаты выполнения кода. Числа хранятся в буфере, и, когда они заполнены, они начинают перезаписываться. Таким образом можно получить последние N чисел.

В предыдущем примере использован индекс для доступа к текущей позиции буфера, потому что он достаточен для объяснения операции. Но в общем, нормальным является то, что используется указатель. Это модифицированный код для использования указателя вместо индекса. По сути, операция такая же, как и предыдущая, а полученные результаты аналогичны.

Высокопроизводительные операции CAS

Disruptor — это высокопроизводительная библиотека для передачи сообщений между потоками, разработанная и открытая несколько лет назад компанией LMAX Exchange. Они создали это программное обеспечение для обработки огромного трафика (более 6 миллионов TPS) в своей розничной финансовой торговой платформе. В 2010 году они удивили всех тем, насколько быстрой может быть их система, выполнив всю бизнес-логику в одном потоке. Хотя один поток был важной концепцией в их решении, Disruptor работает в многопоточной среде и основан на кольцевом буфере — поток, в котором устаревшие данные больше не нужны, потому что поступают более свежие и более актуальные.

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

Кольцевой буфер «qtserialport» (последовательный порт) наследуется от QIODevice, может быть использован для получения различных последовательной информации и включает в себя все из доступных последовательных устройств. Последовательный порт всегда открыт в монопольном доступе, это означает, что другие процессы или потоки не могут получить доступ к открытому последовательному порту.

Кольцевые буферы очень полезны в программировании на «Си», например, можно оценить поток байтов, поступающих через UART.

Неклассические контейнеры в C++

Устройство одного из контейнеров, описанного в статье

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

В стандартную библиотеку C++ входит несколько контейнеров. Кроме этого, в Open Source есть несколько контейнеров, которые покрывают больше юзкейсов. Я опишу устройство интересных контейнеров вне STL 1 и их отличия от классических контейнеров.

Условно контейнеры можно разделить на две группы — последовательные (sequence) и ассоциативные (associative). Это деление я использую из-за того, что они слишком сильно отличаются между собой. В этой статье я рассматриваю только последовательные контейнеры. Но, возможно, когда-то в будущем напишу про ассоциативные контейнеры.

Управление памятью

Чтобы объект мог существовать, ему нужно выделить память, где будут находиться значения его полей. В стандартных приложениях память берется из стека (stack) или из кучи (heap). В общем, это совершенно прописные понятия, но их хорошо бы представлять себе для понимания этой публикации.

Выделение памяти на стеке (stack allocation) это увеличение указателя стека на захардкоженное значение. Выделение памяти на куче (heap allocation) это может быть системный вызов, могут использоваться кастомные аллокаторы со сложной логикой (как tcmalloc, jemalloc), memory pools — много чего происходит «под капотом».

Разница в скорости между двумя видами аллокации отличается на порядки, можно посмотреть на инфографике:

stack allocation займет единицы CPU-операций, heap allocation может занять тысячи, но это зависит от аллокатора — heap allocation можно сделать крайне быстрым. Про самодельные аллокаторы можно почитать на Хабре 2 .

Реализация STL и неклассических контейнеров

Стандарт C++ описывает только интерфейс контейнеров и требования на какие-то вещи (скорость операций, какие-нибудь гарантии и т.д.)

У STL есть несколько реализаций. Одни и те же контейнеры в разных реализациях обычно не очень сильно отличаются друг от друга. Сейчас есть три популярные реализации STL от команд Clang, GCC и Microsoft.

Читать реализации сложно, потому что один и тот же код должен уметь компилироваться под все стандарты, поэтому там есть мешанина из #ifdef -ов и жуткого кода

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

std::array

std::array<T, N> 3 это простейший контейнер. Его семантика ничем не отличается от обычного массива T[N] . Эти объекты лежат на стеке. Ни добавлять, ни удалять объекты нельзя, их ровно N .

Особенность std::array (а точнее, массива T[N] ) в том, что все объекты, которые в нем находятся, инициализируются немедленно и сразу готовы к употреблению.

std::array<T, 8>

Контейнеры разделяют две стадии «получить память для объекта» и «проинициализировать объект в этой памяти»; вторая стадия может произойти значительно позже первой. Но в std::array все N объектов инициализируются сразу.

По правилам C++ в массиве инициализация объектов происходит «слева направо», уничтожение «справа налево» 4 .

Небольшое отступление: может быть такое, что конструктор/деструктор объекта не делает совсем ничего (не меняет память, не вызывает другие делающие что-нибудь методы. ). Такой конструктор/деструктор называют тривиальным. Если у T тривиальные конструктор и деструктор, то кроме выделения памяти для std::array<T, N> ничего не происходит 5 .

std::vector

std::vector<T> 6 аллоцирует память для объектов в куче. На стеке лежат три указателя: на первый объект ( begin ), на следующий за последним объектом ( end ), и на следующий за последним доступным участком памяти ( end_cap ).

std::vector<T>, size = 5, capacity = 8

Объект в заранее аллоцированной памяти создается с помощью конструкции placement new 7 . А начиная с C++11 с вводом perfect forwarding 8 новый объект для вектора можно создавать in-place (с помощью метода emplace / emplace_back 9 ) без лишних вызовов copy/move-конструкторов.

После добавления объекта; size = 6, capacity = 8; изменяется end

У вектора есть метод .size() , это количество реальных объектов; и .capacity() , это количество объектов, под которые зарезервирована память.

Пустой вектор ничего не аллоцирует ( begin = end = end_cap = nullptr ), то есть имеет size и capacity равные .

При добавлении нового объекта, если он «не влезает», то сначала запрашивается память под max(1, 2 * capacity) объектов и старые объекты перемещаются в новую память. Размер вектора растет в последовательности .

size = capacity = 8, перед добавлением объекта нужна реаллокация capacity растет с 8 до 16

Объекты из старой памяти нужно переместить в новую память, и потом освободить старую память. Перемещать объекты можно разными способами — чуть позже я опишу, каким образом можно выбрать наиболее оптимальный. Сейчас можно презентовать кастомную реализацию вектора.

folly::fbvector — улучшенный аналог std::vector

Folly это опенсорсная C++-библиотека всяких полезных штук. Там есть реализация своего вектора — folly::fbvector с документацией 10 .

Основное отличие от std::vector — capacity увеличивается не в раза, а в раза. В документации приводится подробное объяснение, почему это намного лучше — такой коэффициент более cache-friendly.

Также контейнер умеет подстраиваться под аллокатор jemalloc (если он включен) и более оптимально аллоцировать память специально под него.

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

Вот пример не—relocatable объекта, потому что одно поле указывает на другое поле:

По умолчанию Folly считает, что объекты пользовательских классов не-relocatable. Чтобы указать, что пользовательский класс Widget является relocatable, нужно написать это:

Раньше я обещал показать, как выбирается способ переноса объектов; вот так это выглядит для folly::fbvector :

Если тип IsRelocatable : делается memcpy памяти, занимаемой объектами.

Если у типа есть move-конструктор, являющийся noexcept: делается move каждого объекта.

Если у типа нет copy-конструктора: делается move каждого объекта.

По умолчанию: делается copy каждого объекта.

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

Про второй пункт: зачем нужно требование на noexcept у move-конструктора? Это нужно для того, чтобы выполнялись «strong exception guarantee». Посмотрим на такой код:

«Strong exception guarantee» заключается в том, что если при попытке добавить объект в вектор произошло исключение, то сам вектор должен остаться в консистентном состоянии — то есть таким же, как был до попытки добавления объекта.

Если move-конструктор может бросить исключение, то мы можем безнадежно сломать исходный вектор. Пусть мы делаем переаллокацию и во время переноса произошло исключение:

Брошено исключение во время move пятого объекта

В общем случае объекты после move использовать нельзя. Так как часть объектов перемещена в новую память, то надо их переместить назад в старую память. Если во время этого «восстановления» выбросится новое исключение, то выполнение программы окончательно сломано.

А у noexcept move-конструкторов таких проблем нет. В C++ есть правила, по которым у классов могут создаваться неявные конструкторы 11 , и если это возможно, то на них навешивается noexcept.

Многие стайлгайды C++ запрещают использование исключений в принципе (например Google C++ Style Guide 12 ), и такой класс проблем отсутствует.

Про третий пункт: если у класса нет copy-конструктора (таким классом является, например, std::unique_ptr 13 ), то вызывается move-конструктор независимо от наличия noexcept-спецификатора. Это может сломать консистентность (гарантии нет), но таких классов довольно мало и это событие маловероятно.

Про четвертый пункт: если все прошлые пункты не выполняются, то используется обычное копирование объекта.

Для реализации такой логики используются уникальные функции из стандарта, например std::move_if_noexcept 14 .

У классического std::vector такой же выбор логики для перемещения объектов как для folly::fbvector , за исключением первого пункта. Стандартная реализация считает, что объект класса Widget relocatable, если std::is_trivially_move_constructible<Widget>::value == true 15 , и это поменять нельзя.

std::deque

std::deque 16 (double-ended queue) это контейнер с быстрым добавлением объектов в начало и в конец. Если std::vector это сплошной кусок памяти, то в std::deque вся память разбивается на несколько кусков памяти (чанков) одинаковой величины.

std::deque<T>, на картинке start = 3, size = 15

Указатели на чанки «живут» в контейнере, похожем на вектор (с мелкими отличиями).

Получение ссылки на объект проводится через 2 разыменования (вместо 1 у std::vector ).

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

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

Минус контейнера в оверхеде по памяти, который более ощутим если объектов мало. std::deque<T> с одним объектом аллоцирует чанк немаленького размера (в реализации STL от Clang чанк занимает минимум 4096 байт).

Итераторы, указатели, и их инвалидация

До сего времени я не писал ничего подробного про итераторы и про их инвалидацию (как и про инвалидацию указателей).

Хотя эта тема знакома опытным C++-программистам, надо рассказать про них в контексте неклассических контейнеров.

Итератор у container<T> — это «легкий» объект, который должен быть похож на указатель T* . У каждого контейнера он свой. Задача итератора в основном в том, чтобы после вызова iter++ он начал как бы «указывать» на следующий объект контейнера, а вызов *iter вернул бы ссылку на как бы «указываемый» объект. Итераторы нужны много где, например для range-for 17 .

Самый простой итератор у std::array<T> , это и есть сам указатель T* .

Более сложный итератор у std::deque<T> , это объект из двух указателей: указатель на текущий чанк и указатель на текущий объект чанка. По iter++ эти указатели аккуратно обновляются и по *iter возвращается текущий объект чанка. Таким образом итератор обеспечивает «бесшовный» проход по всем объектам контейнера.

Итераторы/указатели могут инвалидироваться, то есть перестать указывать на объект. Обычно для описания условий, когда это происходит, создают всякие большие таблицы, где разбирают corner case-ы и т.д.

Лучше, конечно, не зубрить таблицы, а прочитать исходник класса итератора и класса контейнера. Тогда понимание этого вопроса придет само. Например, если не знать внутреннее устройство std::vector и std::deque , то сложно понимать, почему после вызова push_back ссылка на объект в первом контейнере может «протухнуть», а во втором — нет.

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

std::forward_list

std::forward_list 18 это однонаправленный список — самая простая реализация списка. Список состоит из вершин. Вершина списка это сам объект и указатель на следующую вершину (указатель принимает значение nullptr , если объект последний в списке). Для каждой вершины память аллоцируется отдельно, размером sizeof(T) + sizeof(void*) байт.

std::forward_list<T> из трех объектов, корневая вершина на стеке

Контейнер поддерживает быструю вставку и удаление объектов в любом месте, потому что для этого понадобится только правка next_ptr у вершины слева. Впрочем, «быстрая вставка» относится исключительно к «алгоритмической сложности». Аллокация памяти для новой вершины может быть небыстрой.

Добавление нового объекта в середину списка

Быстро получить N-й объект нельзя, для этого нужно пройтись от корневой вершины по next_ptr N раз. Размер списка тоже можно узнать только пройдя по всем next_ptr , пока не увидим nullptr . У контейнера даже нет метода .size() .

Вне STL есть реализации однонаправленного списка, где метод .size() реализован за , за оверхед в виде хранения переменной size на стеке.

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

std::list

std::list 19 это более сложная организация списка. Она имеет все те же свойства, как у std::forward_list , но вершины дополнительно могут ссылаться на предыдущие вершины, и есть быстрое добавление в конец списка.

std::list<T>, size = 3

Интересный факт: начиная с C++11, вызов .size() должен работать за константное время 20 . Для этого поддерживается переменная, куда записывается размер списка. До C++11 реализации STL могли выполнять .size() за линейное время, проходя по всем вершинам.

Контейнеры-адаптеры

Некоторые контейнеры не имеют хитрого внутреннего устройства, и их функционал базируется на функционале какого-нибудь другого контейнера. В STL таких контейнеров три: std::stack , std::queue , std::priority_queue , в каждом можно выбрать «реальный» контейнер.

В большинстве случаев интерфейс контейнера-адаптера просто перенаправляет вызов методов, например у std::stack :

Битовые контейнеры — std::bitset, std::vector<bool>, boost::dynamic_bitset

Битовые контейнеры нужны для управления последовательностью из N битов. То есть это контейнеры для всего лишь одного типа — битов.

Объект не может «весить» меньше чем 1 байт, но в один байт вмещается целых CHAR_BIT 21 битов (обычно CHAR_BIT = 8 ). Поэтому специальный контейнер для битов в 8 раз эффективнее по памяти.

Физически такие контейнеры содержат несколько чисел, обычно типа size_t (их размер 64 бита на 64-битной машине).

Как и в «стандартных» контейнерах, данные могут лежать либо на стеке, либо в куче.

std::bitset<512> на 64-битной машине (хватает 8 чисел size_t)

В std::bitset<N> 22 , который лежит на стеке, количество битов нужно знать «заранее». Изначально все биты заполняются нулями. В контейнере есть несколько разнообразных методов для управления битами (всеми битами или конкретным битом).

Групповые операции, например .count() 23 работают намного быстрее, чем если бы они совершались в обычном цикле for. Процессоры умеют производить все битовые операции над числом в одну инструкцию, что как минимум в 64 раза быстрее, чем если бы это делалось в цикле.

Интересным образом поддержана работа с битами через оператор [] :

operator[](size_t pos) переопределен так, чтобы на его вызов возвращался «легкий» объект std::bitset::reference , в котором находится указатель на число и «маска» бита. И в свою очередь у этого объекта переопределен operator=(bool x) , который производит запись в нужный бит.

Как вы уже могли заметить, в C++ много где используются подобные фокусы с подставлением «легких» объектов (итераторы, bit reference), чтобы пользователям было удобно с ними работать.

Аналогичный класс с данными в куче (где количество битов можно задавать в run-time), сделан в виде std::vector<bool> . Этот класс многим программистам не нравится и есть мнение, что это неудачное решение в C++ 24 . Люди, которые пытаются использовать его как полноценный контейнер, а не как » std::bitset на куче», натыкаются, например, на невозможность использовать нормальные указатели на объект (нельзя указывать на отдельный бит). Если есть такие проблемы, можно использовать std::vector<char> , std::vector<int> , std::deque<bool> .

std::vector<bool> или std::dynamic_bitset

std::vector<bool> отличается крайней бедностью доступных операций над битами. В нем отсутствуют элементарные групповые операции над битами, которые, как уже ранее писал, процессор умеет выполнять на порядки более эффективно, чем через for-цикл.

Есть его более продвинутый аналог в Boost — boost::dynamic_bitset 25 . В нем есть быстрая реализация всех операций над битсетом, которые только можно представить. Этот контейнер используется во многих проектах, у него широкий спектр применения.

«Неклассические» контейнеры хороши тем, что их можно достаточно быстро улучшать, отправляя туда патчи. Несколько лет назад я отправил в boost::dynamic_bitset пару патчей, которые ускоряли подсчет битов и добавляли новые методы для управления последовательностью битов 26 .

Static vector

Рассматриваемый ранее std::array<T, N> имеет свойство, что все N объектов инициализируются сразу. Если такое свойство не нравится, и хочется управлять памятью под N объектов, то можно использовать boost::static_vector 27 .

boost::static_vector<T, 8>

Этот контейнер ведет себя как обычный std::vector , но память у него аллоцирована на стеке под N объектов.

Каким образом можно получить сырую память на стеке, не имея создаваемого объекта? До C++23 это делается через std::aligned_storage 28 , с высоким риском для программиста сделать что-то не так и отстрелить себе ногу. Начиная с С++23 можно будет делать попроще:

и потом создавать объекты в buff через ставший привычный нам placement new.

По умолчанию, при попытке добавить N+1 объект в boost::static_vector выбросится исключение. Можно написать код и запустить через godbolt (он поддерживает Boost) 29 . Для максимального перформанса можно в шаблон передать настройку не выбрасывать исключение, тогда программа просто схлопнется 30 .

Small vector

boost::small_vector 31 это гибрид boost::static_vector и std::vector . В нем статически отводится память под N объектов, но при переполнении аллоцируется память в куче.

boost::small_vec<T, 8> с 13 объектами

На изображении показано, что N объектов лежит на стеке и size — N объектов в куче. Но есть реализации, где все size объектов выкидываются в кучу, чтобы обеспечить нахождение объектов в непрерывном участке памяти (при size > N ).

Этот контейнер хорош, если количество объектов с большой вероятностью не превосходит заранее известное число.

Авторы этого контейнера пишут, что вдохновлялись SmallVector’ом из LLVM 32 . Это неудивительно — описываемые в статье контейнеры много где переизобретались заново.

В boost есть свой велосипед реализация собственно STL-овых контейнеров с разными фичами, например можно задавать growth factor у vector 33 или размер блока у deque.

Devector

boost::devector это гибрид std::vector и std::deque . В этом контейнере есть быстрая вставка в начало и в конец, как в deque, но при этом сохраняются свойства vector, в частности непрерывный участок памяти и условия инвалидации указателей/итераторов.

boost::devector<T>, size = 5, front_capacity = 1, back_capacity = 2

При переаллокации вектора выбирается, в какую сторону девектор нужно расширять — слева или справо, в зависимости от того, какая граница была «пробита».

Если sizeof(std::vector) == 3 * sizeof(T*) , то devector требуется дополнительный указатель, то есть sizeof(boost::devector) == 4 * sizeof(T*) .

Stable vector

boost::stable_vector 34 это гибрид std::vector и std::list .

В std::vector есть минус — легко инвалидирующиеся ссылки и итераторы. Они инвалидируются, когда вектор реаллоцируется, или когда удаляется/вставляется объект ближе к началу.

Можно поделить контейнеры на «стабильные» и «нестабильные». В «стабильных» контейнерах ссылки и итераторы на объект остаются валидными до тех пор, пока объект не удален из контейнера. Пример «стабильного» контейнера — std::list . Понятно, что std::vector — «нестабильный» контейнер.

Если у std::vector убрать требование на последовательное расположение объектов в памяти, то можно реализовать «стабильный» аналог вектора:

boost::stable_vector<T>, содержит 5 объектов

Там, где у std::vector лежат объекты, у boost::stable_vector вместо них лежит массив со ссылками на node.

node содержит в себе value — сам объект, и up — обратную ссылку на место в массиве, чье значение указывает на node.

Так же, как в std::list , node для каждого объекта аллоцируется отдельно.

Итератором на объект является ссылка на node.

Ссылки и итераторы на объект валидны до тех пор, пока объект не удалят из контейнера. Вставка/удаление объекта, который «ближе» к началу вектора, перепишет указатель up , но ни ссылка (на value ), ни итератор (node*) не изменятся. Реаллокация массива ссылок на ноды также не инвалидирует ссылки/итераторы на объект (контейнер пофиксит значения up во время реаллокации).

Покажем на oversimplified псевдокоде, как работает итератор. Пусть есть вектор с указателями на ноды (как на картинке):

В ноде два значения: ссылка на место в массиве ссылок на ноды; и сам объект

Итератор работает со ссылкой на ноду:

Чтобы получить ссылку на «следующую» ноду, надо пройти по up в то место массива, где лежит текущая ссылка, сдвинуться на следующее место, и разыменовать получившееся значение.

Алгоритмическая сложность всех методов boost::stable_vector точно такая же, как у соответствующих методов std::vector . В частности, в отличие от std::list можно за получить объект по произвольному индексу.

Circular buffer

Про кольцевой буфер есть статья на Wikipedia 35 . В C++ его можно реализовать в виде контейнера фиксированной длины N (на стеке или в куче), где при выходе за границу массива объект создается в начале массива.

Кольцевой буфер с памятью на стеке на 8 объектов; start = 5, size = 5

Кольцевой буфер может быть реализован как обычный vector. Плюс контейнера — быстрое удаление/вставка в начале. Минус контейнера — жесткое ограничение по памяти в N объектов. Больше этот контейнер ничем не интересен.

Реализация кольцевого буфера есть в boost: boost::circular_buffer 36 .

Colony

Контейнер colony (колония) это гибрид std::deque и std::list . Этот контейнер предлагали к внесению в стандарт С++, но пока не внесли. Есть документ с максимально подробным описанием контейнера 37 .

Во многих проектах объекты чаще не «владеют» другими объектами, а только ссылаются на них. Например, в видеоиграх объект сущности может ссылаться на общие ресурсы: объекты звуков, объекты спрайтов.

Эти общие ресурсы живут в контейнерах. Если ресурсы часто видоизменяются (выгружаются/загружаются), то контейнер должен быть «стабильным». К сожалению, std::vector не является «стабильным», а std::list не дружит с кэшем и тормозит, особенно при итерировании по нему.

Колония это достаточно быстрый «стабильный» контейнер. Объекты в нем лежат разделенные по чанкам, как в std::deque . Если в std::deque объекты лежат «плотно», то в колонии в чанках могут быть «прорехи». Общий вид колонии за годы несколько раз менялся, но абстракто он выглядит так:

colony<T>

Когда из колонии удаляют объект, то объекты «справа» от него не будут сдвигаться на освободившееся место. Таким образом указатели на объект не могут инвалидироваться.

Колония держит структуру skipfield, в которой кодирует информацию о «прорехах». «Прорехи» переиспользуются — при добавлении нового объекта он записывается в самую левую «прореху». Также skipfield используется для быстрого итерирования по «живым» объектам.

Кроме стабильности, контейнер имеет такие гарантии по базовым операциям:

вставка (одного объекта):

вставка ( N объектов):

удаление (одного объекта):

удаление ( N объектов): если тип не trivially destructible, если trivially destructible

std::find : ; для поиска объекта нужно проитерироваться по всему контейнеру

Random access (оператор [] ): ; из-за «прорех» доступ к произвольному объекту за невозможен

Этот контейнер подходит, если нужна какая-то структура, куда можно быстро добавлять и удалять объекты, и чтобы ссылка на эти объекты не инвалидировалась, и чтобы это работало быстрее чем в std::list . Быстро получить объект по произвольному индексу нельзя, для этого контейнер не предназначен.

Реализацию контейнера можно посмотреть на github 38 .

Как выбрать подходящий контейнер?

Теперь, когда мы рассмотрели классические и неклассические контейнеры, можно представить себе практический кейс.

Допустим, что вы программируете показ рекламы фастфуда �������� на сайтах. Надо показать топ-5 наиболее подходящих блюд. Формула оценки довольно сложная: зависит от региона юзера, доступности блюд в ближайшей точке, маркетинговых акций, текущего времени, etc.

Запросы приходят в API вашего сервиса. Пусть все данные для оценки представлены классами/структурами на C++.

Представим себе API-класс, который описывает одну из ближайших к юзеру точек питания. У него есть расстояние до юзера (чем дольше, тем меньше «вес» в оценке), загруженность, наличие разных блюд, акции, а также история посещений юзером.

Некоторыми данными объект «владеет» (как историей посещения), а на некоторые просто ссылается, потому что они общие для всех.

Здесь получаем проблему — пусть у нас где-то в программе лежат объекты блюд std::vector<Meal> Meals . Если мы создадим Restaurant -ы, а потом добавим какое-то новое блюдо, то можно попасть на переаллокацию вектора, и в таком случае все ссылки Meal* станут висячими.

Можно обернуть объекты в умный указатель std::vector<std::shared_ptr<Meal>> Meals , но это не бесплатно и некрасиво.

Есть способ, который решает несколько проблем — все API-классы нужно объявить non-copyable 39 И non-movable. Какие будут плюсы:

Объекты невозможно случайно передать по значению/скопировать/переместить.

Указатели на объекты живут столько же, сколько контейнер, где содержится объект.

Компилятор C++ не даст заиспользовать контейнер как std::vector , который потенциально сможет инвалидировать ссылки. Скомпилируется использование безопасного контейнера, например std::list . Из неклассических контейнеров скомпилируется использование, например, stable_vector или colony .