Вам нужен односвязный контейнер: почему у std::forward_list нет метода size()?
std::forward_list не предоставляет size(), потому что поддержка размера за O(1) потребовала бы хранить счётчик элементов и обновлять его при каждой модификации. Это увеличило бы накладные расходы контейнера и усложнило бы операции переноса диапазонов узлов. Количество элементов можно получить через std::distance, но для forward_list это линейная операция.
std::forward_list был добавлен как минималистичная реализация односвязного списка. В отличие от std::list, каждый узел хранит только ссылку на следующий элемент, поэтому контейнер занимает меньше памяти и хорошо подходит для операций вставки и удаления после известной позиции.
Отказ от обязательного счётчика размера сохраняет эту минимальность. Стандарт не требует от forward_list постоянного времени для получения количества элементов, в отличие от контейнеров, где size() является штатной операцией.
Если часто вызывать size() в цикле, линейный подсчёт через std::distance может превратить алгоритм с ожидаемой сложностью O(n) в O(n²). Это особенно опасно, когда контейнер большой или проверка размера выполняется на каждой итерации.
Поддерживать внешний счётчик тоже непросто: его нужно корректно изменять при вставках, удалениях, очистке и переносе узлов между списками. Ошибка синхронизации приведёт к неверному размеру, тогда как сам контейнер продолжит оставаться корректным.
Для forward_list переход от одного элемента к следующему выполняется за O(1), но чтобы узнать длину всего диапазона, нужно пройти его целиком. Поэтому вычисление размера через расстояние между началом и концом имеет сложность O(n).
У хранения счётчика есть компромисс. С одной стороны, size() становится O(1). С другой стороны, каждый владелец списка должен обновлять счётчик при изменении числа узлов, а перенос диапазона через splice_after потребовал бы либо заранее знать длину переносимого диапазона, либо дополнительно проходить его. Кроме того, счётчик увеличивает состояние контейнера.
std::forward_list подходит, когда нужны малые накладные расходы, последовательный обход и операции insert_after или erase_after при наличии нужного итератора. Если размер нужен постоянно, обычно выбирают std::list или другой контейнер с подходящей моделью доступа.
В обработчике сетевых событий элементы хранятся в порядке поступления, часто удаляются после текущего узла и иногда целыми диапазонами перемещаются между очередями. Рассматривались std::vector, std::list и std::forward_list.
std::vector обеспечивает хорошую локальность и быстрый подсчёт размера, но вставки и удаления в начале или середине требуют сдвига элементов. std::list даёт постоянное время получения размера и удобное перемещение узлов, однако каждый узел хранит две ссылки и хуже использует кэш процессора. std::forward_list минимален по памяти и эффективно выполняет операции после известной позиции, но подсчёт размера нельзя дёшево повторять.
Если размер очереди нужен только при редких диагностических снимках, выбран std::forward_list, а снимок строится отдельным проходом. Если же размер участвует в каждом цикле планирования, разумнее выбрать std::list либо хранить размер в отдельной структуре с чётко контролируемыми правилами изменения.
1. Можно ли считать получение размера через std::distance эквивалентом вызову size()?
Нет. Для итераторов forward_list расстояние вычисляется последовательным продвижением от начала к концу, поэтому его сложность O(n). Такая замена сохраняет корректность результата, но может существенно изменить производительность алгоритма.
2. Почему отсутствие счётчика особенно связано с операциями splice_after?
Перенос связного диапазона можно выполнить перенастройкой нескольких ссылок, не посещая каждый узел. Если контейнер обязан обновлять счётчик размера, ему нужно знать количество перенесённых узлов. Без заранее известной длины это обычно требует линейного прохода или дополнительного состояния, тогда как сама перестановка ссылок может быть константной.
3. Почему std::list не является автоматической заменой std::forward_list, если нужен постоянный размер?
У std::list есть двусвязные узлы, то есть на каждый элемент приходится дополнительная ссылка. Это увеличивает расход памяти и обычно ухудшает локальность доступа. Поэтому выбор зависит не только от сложности size(), но и от характера обхода, требований к памяти и необходимости двигаться назад по списку.