# Архитектура ## Представления `AdaptiveSequence` хранит `variant, TieredStorage>`. Contiguous vector выгоден для малых последовательностей и индексного чтения. Tiered storage состоит из независимо выделенных циклических leaf-блоков (`RingBlock`) и многоуровневого каталога весов. У обоих backend есть единая **логическая вместимость** `capacity()`. Это не сумма физического slack в leaf-блоках, а управляющая граница, на которой разрешена автоматическая O(N)-перестройка. Текущий `TieredStorage` остаётся сегментированным исследовательским вариантом, а не полной реализацией implicit tiered vector с offsets/carry на каждом внутреннем узле. Offsets используются внутри leaf, но split/merge может менять массив leaf-дескрипторов и перестраивать каталог за O(number_of_leaves). Это ограничение нужно учитывать при интерпретации результатов. ## Текущая default-policy: перестройка только с capacity `ResizePolicy` не пытается распознать workload после каждой операции. В auto-mode представление и геометрия пересматриваются только вместе с изменением логической вместимости: 1. Перед вставкой, которая не помещается, capacity удваивается до достаточного значения. Для обычного роста это одна граница `C -> 2C`. 2. После удаления при `size <= capacity / 8`, то есть при заполнении не более 12.5%, capacity уменьшается на один шаг `C -> C/2` (но не ниже `size`). 3. Внутри той же перестройки выбираются mode, leaf geometry и размер hash table. Между такими границами они остаются неизменными. В auto-mode целевое представление определяется размером на момент перестройки: ```text target_size < 4096 -> vector target_size >= 4096 -> tiered ``` `4096` — cutoff, подтверждённый текущим focused-run 7 x 100000 для `AdaptiveSequence` и заданного mix; это не универсальный результат для всех типов и workload. Само пересечение `size=4096` немедленного перехода не вызывает: mode меняется только на следующей capacity-boundary. Например, при обычном последовательном росте контейнер остаётся vector при capacity 4096 и переходит в tiered, когда следующая вставка меняет capacity на 8192. На shrink boundary правило применяется заново, поэтому возможен обратный переход `tiered -> vector`. Явные `force_vector_mode()`, `force_tiered_mode()` и `reserve()` остаются пользовательскими управляющими операциями и не являются автоматической адаптацией. ## Геометрия tiered storage При capacity-boundary размер малого массива вычисляется из фактического размера последовательности на этой границе: ```text leaf_capacity = max(4, ceil(sqrt(target_size))) ``` Значения fanout и допустимой глубины каталога берутся из `TieredConfig`. `leaf_capacity` не подстраивается после каждой вставки или удаления: новое `sqrt(N)` применяется только в общей перестройке. Поэтому rebuild одновременно может выполнить `vector -> tiered`, `tiered -> vector` или `tiered -> tiered` с новой геометрией. ## Flat hash index `AdaptiveSequence` использует open-addressed flat table `value -> {head_id,count}`. Дубликаты связаны через компактные intrusive links в ID metadata. `find_one` возвращает любой экземпляр, `find_all_ids` — unordered stable IDs, а `find_all` сортирует логические позиции и может стоить O(k log k). Внутри цепочек используются 32-битные slot IDs. Освобождённые metadata slots переиспользуются через free list, а публичный 64-битный stable ID кодирует `generation + slot`. Поэтому сбалансированный insert/erase churn не наращивает metadata без границ и старый ID не оживает после повторного использования slot. Hash table следует той же capacity-policy, что и storage: ```text required_buckets = ceil(logical_capacity / 0.70) bucket_count = next_power_of_two(max(16, required_buckets)) ``` Иными словами, таблица заранее рассчитана на худший случай «один уникальный ключ на элемент» при load factor не выше 70%. При росте bucket reserve/rehash выполняется перед перестройкой storage, при shrink — после неё. Целевое число buckets пересчитывается только при изменении логической capacity; если оно не изменилось, отдельного rehash нет. Обычные вставки и удаления между границами не запускают независимое увеличение hash table. Такой выбор сохраняет O(1) expected lookup и включает стоимость редкого rehash в ту же измеряемую capacity-перестройку, где уже оплачивается перенос storage. Flat hash остаётся compile-time optional: вариант `AdaptiveSequence` не несёт его память; тот же API поиска по значению работает линейным обходом. ## Инвалидация - const-чтение и hash lookup ничего не инвалидируют; - `set()` не меняет логические позиции, но ссылка на заменённое значение не должна использоваться как ссылка на старый объект; - вставка или удаление инвалидирует позиционные references, pointers и iterators согласно структурному изменению; capacity-boundary дополнительно может перестроить весь backend; - conversion, geometry rebuild, `force_*`, `reserve`, `clear` и `make_contiguous()` инвалидируют всё позиционное; - stable ID переживает shifts, split и смену представления и перестаёт быть живым только после удаления соответствующего элемента или `clear()`. Stable ID имеет область действия конкретного состояния конкретного контейнера. Copy/move assignment заменяет это состояние: ранее полученные ID обеих сторон после assignment использовать нельзя (их числовое значение может совпасть с ID элемента нового состояния). Move construction переносит состояние целиком и сохраняет его ID в новом объекте. Debug iterator хранит structural generation и бросает `logic_error` после инвалидирования. ## Historical / retired: operation-window CostModelPolicy До текущей постановки default-policy собирала `OperationSample`, оценивала vector и набор фиксированных leaf 64/128/256/512/1024, применяла EWMA, hysteresis и прогноз окупаемости O(N)-перехода: ```text (current_cost - candidate_cost) * forecast > rebuild_cost * safety_factor ``` Также исследовались deferred/eager read adaptation, minimum residency и отдельные `vector -> tiered`, `tiered -> vector`, `tiered -> tiered` решения. Эта схема и соответствующая benchmark-матрица **retired**: они сохранены для воспроизводимости старых CSV и для экспериментов с явно выбранной `CostModelPolicy`, но не описывают текущую default-policy и не используются для нового cutoff.