YT-18571: library/cpp/yt/small_containers -> library/cpp/yt/compact_containers

commit_hash:fc31d2770ebeffeb513c4535bd146c731b7f78fb

17 files changed, 4260 insertions, 0 deletions

diff --git a/library/cpp/yt/compact_containers/compact_flat_map-inl.h b/library/cpp/yt/compact_containers/compact_flat_map-inl.h
new file mode 100644
index 00000000000..e781569d9da
--- /dev/null
+++ b/library/cpp/yt/compact_containers/compact_flat_map-inl.h
@@ -0,0 +1,253 @@
+#ifndef COMPACT_FLAT_MAP_INL_H_
+#error "Direct inclusion of this file is not allowed, include compact_flat_map.h"
+// For the sake of sane code completion.
+#include "compact_flat_map.h"
+#endif
+
+namespace NYT {
+
+///////////////////////////////////////////////////////////////////////////////
+
+template <class TKey, class TValue, size_t N, class TKeyCompare>
+template <class TInputIterator>
+TCompactFlatMap<TKey, TValue, N, TKeyCompare>::TCompactFlatMap(TInputIterator begin, TInputIterator end)
+{
+    insert(begin, end);
+}
+
+template <class TKey, class TValue, size_t N, class TKeyCompare>
+TCompactFlatMap<TKey, TValue, N, TKeyCompare>::TCompactFlatMap(std::initializer_list<value_type> values)
+    : TCompactFlatMap<TKey, TValue, N, TKeyCompare>(values.begin(), values.end())
+{ }
+
+template <class TKey, class TValue, size_t N, class TKeyCompare>
+bool TCompactFlatMap<TKey, TValue, N, TKeyCompare>::operator==(const TCompactFlatMap& rhs) const
+{
+    return Storage_ == rhs.Storage_;
+}
+
+template <class TKey, class TValue, size_t N, class TKeyCompare>
+bool TCompactFlatMap<TKey, TValue, N, TKeyCompare>::operator!=(const TCompactFlatMap& rhs) const
+{
+    return !(*this == rhs);
+}
+
+template <class TKey, class TValue, size_t N, class TKeyCompare>
+typename TCompactFlatMap<TKey, TValue, N, TKeyCompare>::iterator TCompactFlatMap<TKey, TValue, N, TKeyCompare>::begin()
+{
+    return Storage_.begin();
+}
+
+template <class TKey, class TValue, size_t N, class TKeyCompare>
+typename TCompactFlatMap<TKey, TValue, N, TKeyCompare>::const_iterator TCompactFlatMap<TKey, TValue, N, TKeyCompare>::begin() const
+{
+    return Storage_.begin();
+}
+
+template <class TKey, class TValue, size_t N, class TKeyCompare>
+typename TCompactFlatMap<TKey, TValue, N, TKeyCompare>::const_iterator TCompactFlatMap<TKey, TValue, N, TKeyCompare>::cbegin() const
+{
+    return Storage_.begin();
+}
+
+template <class TKey, class TValue, size_t N, class TKeyCompare>
+typename TCompactFlatMap<TKey, TValue, N, TKeyCompare>::iterator TCompactFlatMap<TKey, TValue, N, TKeyCompare>::end()
+{
+    return Storage_.end();
+}
+
+template <class TKey, class TValue, size_t N, class TKeyCompare>
+typename TCompactFlatMap<TKey, TValue, N, TKeyCompare>::const_iterator TCompactFlatMap<TKey, TValue, N, TKeyCompare>::end() const
+{
+    return Storage_.end();
+}
+
+template <class TKey, class TValue, size_t N, class TKeyCompare>
+typename TCompactFlatMap<TKey, TValue, N, TKeyCompare>::const_iterator TCompactFlatMap<TKey, TValue, N, TKeyCompare>::cend() const
+{
+    return Storage_.end();
+}
+
+template <class TKey, class TValue, size_t N, class TKeyCompare>
+void TCompactFlatMap<TKey, TValue, N, TKeyCompare>::reserve(size_type n)
+{
+    Storage_.reserve(n);
+}
+
+template <class TKey, class TValue, size_t N, class TKeyCompare>
+typename TCompactFlatMap<TKey, TValue, N, TKeyCompare>::size_type TCompactFlatMap<TKey, TValue, N, TKeyCompare>::size() const
+{
+    return Storage_.size();
+}
+
+template <class TKey, class TValue, size_t N, class TKeyCompare>
+int TCompactFlatMap<TKey, TValue, N, TKeyCompare>::ssize() const
+{
+    return static_cast<int>(Storage_.size());
+}
+
+template <class TKey, class TValue, size_t N, class TKeyCompare>
+bool TCompactFlatMap<TKey, TValue, N, TKeyCompare>::empty() const
+{
+    return Storage_.empty();
+}
+
+template <class TKey, class TValue, size_t N, class TKeyCompare>
+void TCompactFlatMap<TKey, TValue, N, TKeyCompare>::clear()
+{
+    Storage_.clear();
+}
+
+template <class TKey, class TValue, size_t N, class TKeyCompare>
+void TCompactFlatMap<TKey, TValue, N, TKeyCompare>::shrink_to_small()
+{
+    Storage_.shrink_to_small();
+}
+
+template <class TKey, class TValue, size_t N, class TKeyCompare>
+template <NDetail::CComparisonAllowed<TKey, TKeyCompare> TOtherKey>
+typename TCompactFlatMap<TKey, TValue, N, TKeyCompare>::iterator TCompactFlatMap<TKey, TValue, N, TKeyCompare>::find(const TOtherKey& k)
+{
+    auto [rangeBegin, rangeEnd] = equal_range(k);
+    return rangeBegin == rangeEnd ? end() : rangeBegin;
+}
+
+template <class TKey, class TValue, size_t N, class TKeyCompare>
+template <NDetail::CComparisonAllowed<TKey, TKeyCompare> TOtherKey>
+typename TCompactFlatMap<TKey, TValue, N, TKeyCompare>::const_iterator TCompactFlatMap<TKey, TValue, N, TKeyCompare>::find(const TOtherKey& k) const
+{
+    auto [rangeBegin, rangeEnd] = equal_range(k);
+    return rangeBegin == rangeEnd ? end() : rangeBegin;
+}
+
+template <class TKey, class TValue, size_t N, class TKeyCompare>
+template <NDetail::CComparisonAllowed<TKey, TKeyCompare> TOtherKey>
+bool TCompactFlatMap<TKey, TValue, N, TKeyCompare>::contains(const TOtherKey& k) const
+{
+    return find(k) != end();
+}
+
+template <class TKey, class TValue, size_t N, class TKeyCompare>
+auto TCompactFlatMap<TKey, TValue, N, TKeyCompare>::insert(const value_type& value) -> std::pair<iterator, bool>
+{
+    return do_insert(value);
+}
+
+template <class TKey, class TValue, size_t N, class TKeyCompare>
+auto TCompactFlatMap<TKey, TValue, N, TKeyCompare>::insert(value_type&& value) -> std::pair<iterator, bool>
+{
+    return do_insert(std::move(value));
+}
+
+template <class TKey, class TValue, size_t N, class TKeyCompare>
+template <class TArg>
+auto TCompactFlatMap<TKey, TValue, N, TKeyCompare>::do_insert(TArg&& value) -> std::pair<iterator, bool>
+{
+    auto [rangeBegin, rangeEnd] = equal_range(value.first);
+    if (rangeBegin != rangeEnd) {
+        return {rangeBegin, false};
+    } else {
+        auto it = Storage_.insert(rangeBegin, std::forward<TArg>(value));
+        return {it, true};
+    }
+}
+
+template <class TKey, class TValue, size_t N, class TKeyCompare>
+template <class TInputIterator>
+void TCompactFlatMap<TKey, TValue, N, TKeyCompare>::insert(TInputIterator begin, TInputIterator end)
+{
+    for (auto it = begin; it != end; ++it) {
+        insert(*it);
+    }
+}
+
+template <class TKey, class TValue, size_t N, class TKeyCompare>
+template <class... TArgs>
+auto TCompactFlatMap<TKey, TValue, N, TKeyCompare>::emplace(TArgs&&... args) -> std::pair<iterator, bool>
+{
+    return insert(value_type(std::forward<TArgs>(args)...));
+}
+
+template <class TKey, class TValue, size_t N, class TKeyCompare>
+TValue& TCompactFlatMap<TKey, TValue, N, TKeyCompare>::operator[](const TKey& k)
+{
+    auto [it, inserted] = insert({k, TValue()});
+    return it->second;
+}
+
+template <class TKey, class TValue, size_t N, class TKeyCompare>
+void TCompactFlatMap<TKey, TValue, N, TKeyCompare>::erase(const TKey& k)
+{
+    auto [rangeBegin, rangeEnd] = equal_range(k);
+    erase(rangeBegin, rangeEnd);
+}
+
+template <class TKey, class TValue, size_t N, class TKeyCompare>
+void TCompactFlatMap<TKey, TValue, N, TKeyCompare>::erase(iterator pos)
+{
+    Storage_.erase(pos);
+
+    // Try to keep the storage inline. This is why erase doesn't return an iterator.
+    Storage_.shrink_to_small();
+}
+
+template <class TKey, class TValue, size_t N, class TKeyCompare>
+void TCompactFlatMap<TKey, TValue, N, TKeyCompare>::erase(iterator b, iterator e)
+{
+    Storage_.erase(b, e);
+
+    // Try to keep the storage inline. This is why erase doesn't return an iterator.
+    Storage_.shrink_to_small();
+}
+
+template <class TKey, class TValue, size_t N, class TKeyCompare>
+template <NDetail::CComparisonAllowed<TKey, TKeyCompare> TOtherKey>
+std::pair<typename TCompactFlatMap<TKey, TValue, N, TKeyCompare>::iterator, typename TCompactFlatMap<TKey, TValue, N, TKeyCompare>::iterator>
+TCompactFlatMap<TKey, TValue, N, TKeyCompare>::equal_range(const TOtherKey& k)
+{
+    auto result = std::ranges::equal_range(Storage_, k, {}, &value_type::first);
+    YT_ASSERT(result.size() <= 1);
+    return result;
+}
+
+template <class TKey, class TValue, size_t N, class TKeyCompare>
+template <NDetail::CComparisonAllowed<TKey, TKeyCompare> TOtherKey>
+std::pair<typename TCompactFlatMap<TKey, TValue, N, TKeyCompare>::const_iterator, typename TCompactFlatMap<TKey, TValue, N, TKeyCompare>::const_iterator>
+TCompactFlatMap<TKey, TValue, N, TKeyCompare>::equal_range(const TOtherKey& k) const
+{
+    auto result = std::ranges::equal_range(Storage_, k, {}, &value_type::first);
+    YT_ASSERT(result.size() <= 1);
+    return result;
+}
+
+template <class TKey, class TValue, size_t N, class TKeyCompare>
+template <NDetail::CComparisonAllowed<TKey, TKeyCompare> TOtherKey>
+typename TCompactFlatMap<TKey, TValue, N, TKeyCompare>::const_iterator TCompactFlatMap<TKey, TValue, N, TKeyCompare>::lower_bound(const TOtherKey& k) const
+{
+    return std::ranges::lower_bound(Storage_, k, {}, &value_type::first);
+}
+
+template <class TKey, class TValue, size_t N, class TKeyCompare>
+template <NDetail::CComparisonAllowed<TKey, TKeyCompare> TOtherKey>
+typename TCompactFlatMap<TKey, TValue, N, TKeyCompare>::iterator TCompactFlatMap<TKey, TValue, N, TKeyCompare>::lower_bound(const TOtherKey& k)
+{
+    return std::ranges::lower_bound(Storage_, k, {}, &value_type::first);
+}
+
+template <class TKey, class TValue, size_t N, class TKeyCompare>
+template <NDetail::CComparisonAllowed<TKey, TKeyCompare> TOtherKey>
+typename TCompactFlatMap<TKey, TValue, N, TKeyCompare>::const_iterator TCompactFlatMap<TKey, TValue, N, TKeyCompare>::upper_bound(const TOtherKey& k) const
+{
+    return std::ranges::upper_bound(Storage_, k, {}, &value_type::first);
+}
+
+template <class TKey, class TValue, size_t N, class TKeyCompare>
+template <NDetail::CComparisonAllowed<TKey, TKeyCompare> TOtherKey>
+typename TCompactFlatMap<TKey, TValue, N, TKeyCompare>::iterator TCompactFlatMap<TKey, TValue, N, TKeyCompare>::upper_bound(const TOtherKey& k)
+{
+    return std::ranges::upper_bound(Storage_, k, {}, &value_type::first);
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+} // namespace NYT
diff --git a/library/cpp/yt/compact_containers/compact_flat_map.h b/library/cpp/yt/compact_containers/compact_flat_map.h
new file mode 100644
index 00000000000..d4e93668430
--- /dev/null
+++ b/library/cpp/yt/compact_containers/compact_flat_map.h
@@ -0,0 +1,134 @@
+#pragma once
+
+#include "compact_vector.h"
+
+namespace NYT {
+
+///////////////////////////////////////////////////////////////////////////////
+
+namespace NDetail {
+
+template <typename T>
+concept CHasIsTransparentFlag = requires {
+    typename T::is_transparent;
+};
+
+template <typename T, typename U, typename TCompare>
+concept CComparisonAllowed = std::same_as<T, U> || CHasIsTransparentFlag<TCompare>;
+
+} // namespace NDetail
+
+///////////////////////////////////////////////////////////////////////////////
+
+//! A flat map implementation over TCompactTValueector that tries to keep data inline.
+/*!
+ *  Similarly to SmallSet, this is implemented via binary search over a sorted
+ *  vector. Unlike SmallSet, however, this one never falls back to std::map (or
+ *  set) for larger sizes. This means that the flat map is only useful
+ *    - at small sizes, when there's absolutely no chance of it getting big, or
+ *    - when it's filled once and is then only read from.
+ *
+ *  In return, the flat map provides
+ *    - a smaller size overhead and
+ *    - a guarantee that if data fits into inline storage, it goes there.
+ *
+ *  Because of the latter, one should be very careful with iterators: virtually
+ *  any call to insert or erase may potentially invalidate all iterators.
+ */
+template <class TKey, class TValue, size_t N, class TKeyCompare = std::ranges::less>
+class TCompactFlatMap
+{
+public:
+    // NB: can't make this pair<const TKey, TValue> as TCompactTValueector requires its type
+    // parameter to be copy-assignable.
+    using value_type = std::pair<TKey, TValue>;
+    using key_type = TKey;
+    using mapped_type = TValue;
+    using key_compare = TKeyCompare;
+
+private:
+    using TStorage = TCompactVector<value_type, N>;
+
+public:
+    using iterator = typename TStorage::iterator;
+    using const_iterator = typename TStorage::const_iterator;
+    using size_type = size_t;
+
+    TCompactFlatMap() = default;
+
+    template <class TInputIterator>
+    TCompactFlatMap(TInputIterator begin, TInputIterator end);
+
+    TCompactFlatMap(std::initializer_list<value_type> values);
+
+    bool operator==(const TCompactFlatMap& rhs) const;
+    bool operator!=(const TCompactFlatMap& rhs) const;
+
+    iterator begin();
+    const_iterator begin() const;
+    const_iterator cbegin() const;
+
+    iterator end();
+    const_iterator end() const;
+    const_iterator cend() const;
+
+    void reserve(size_type n);
+
+    size_type size() const;
+    int ssize() const;
+
+    [[nodiscard]] bool empty() const;
+    void clear();
+
+    void shrink_to_small();
+
+    template <NDetail::CComparisonAllowed<TKey, TKeyCompare> TOtherKey>
+    iterator find(const TOtherKey& k);
+    template <NDetail::CComparisonAllowed<TKey, TKeyCompare> TOtherKey>
+    const_iterator find(const TOtherKey& k) const;
+
+    template <NDetail::CComparisonAllowed<TKey, TKeyCompare> TOtherKey>
+    iterator lower_bound(const TOtherKey& k);
+    template <NDetail::CComparisonAllowed<TKey, TKeyCompare> TOtherKey>
+    const_iterator lower_bound(const TOtherKey& k) const;
+    template <NDetail::CComparisonAllowed<TKey, TKeyCompare> TOtherKey>
+    iterator upper_bound(const TOtherKey& k);
+    template <NDetail::CComparisonAllowed<TKey, TKeyCompare> TOtherKey>
+    const_iterator upper_bound(const TOtherKey& k) const;
+    template <NDetail::CComparisonAllowed<TKey, TKeyCompare> TOtherKey>
+    std::pair<iterator, iterator> equal_range(const TOtherKey& k);
+    template <NDetail::CComparisonAllowed<TKey, TKeyCompare> TOtherKey>
+    std::pair<const_iterator, const_iterator> equal_range(const TOtherKey& k) const;
+
+    template <NDetail::CComparisonAllowed<TKey, TKeyCompare> TOtherKey>
+    bool contains(const TOtherKey& k) const;
+
+    std::pair<iterator, bool> insert(const value_type& value);
+    std::pair<iterator, bool> insert(value_type&& value);
+
+    template <class TInputIterator>
+    void insert(TInputIterator begin, TInputIterator end);
+
+    template <class... TArgs>
+    std::pair<iterator, bool> emplace(TArgs&&... args);
+
+    TValue& operator[](const TKey& k);
+
+    void erase(const TKey& k);
+    void erase(iterator pos);
+    void erase(iterator b, iterator e);
+
+private:
+    TStorage Storage_;
+
+    template <class TArg>
+    std::pair<iterator, bool> do_insert(TArg&& value);
+};
+
+////////////////////////////////////////////////////////////////////////////////
+
+} // namespace NYT
+
+#define COMPACT_FLAT_MAP_INL_H_
+#include "compact_flat_map-inl.h"
+#undef COMPACT_FLAT_MAP_INL_H_
diff --git a/library/cpp/yt/compact_containers/compact_heap-inl.h b/library/cpp/yt/compact_containers/compact_heap-inl.h
new file mode 100644
index 00000000000..2c6b3507ba5
--- /dev/null
+++ b/library/cpp/yt/compact_containers/compact_heap-inl.h
@@ -0,0 +1,152 @@
+#ifndef COMPACT_HEAP_INL_H_
+#error "Direct inclusion of this file is not allowed, include compact_heap.h"
+// For the sake of sane code completion.
+#include "compact_heap.h"
+#endif
+
+#include <library/cpp/yt/assert/assert.h>
+
+#include <algorithm>
+
+namespace NYT {
+
+////////////////////////////////////////////////////////////////////////////////
+
+template <class T, size_t N, class C>
+TCompactHeap<T, N, C>::TCompactHeap(C comparator) noexcept
+    : Comparator_(TReverseComparator(std::move(comparator)))
+{ }
+
+template <class T, size_t N, class C>
+void TCompactHeap<T, N, C>::push(T value)
+{
+    bool wasInline = IsInline();
+    Heap_.push_back(std::move(value));
+    if (Y_UNLIKELY(!IsInline())) {
+        if (wasInline) {
+            std::make_heap(Heap_.begin(), Heap_.end(), Comparator_);
+        } else {
+            std::push_heap(Heap_.begin(), Heap_.end(), Comparator_);
+        }
+    }
+}
+
+template <class T, size_t N, class C>
+void TCompactHeap<T, N, C>::pop()
+{
+    YT_ASSERT(!empty());
+
+    if (Y_LIKELY(IsInline())) {
+        auto minIt = std::max_element(Heap_.begin(), Heap_.end(), Comparator_);
+        std::swap(*minIt, Heap_.back());
+        Heap_.pop_back();
+    } else {
+        std::pop_heap(Heap_.begin(), Heap_.end(), Comparator_);
+        Heap_.pop_back();
+    }
+}
+
+template <class T, size_t N, class C>
+auto TCompactHeap<T, N, C>::get_min() const -> const_reference
+{
+    YT_ASSERT(!empty());
+
+    if (Y_LIKELY(IsInline())) {
+        return *std::max_element(Heap_.begin(), Heap_.end(), Comparator_);
+    } else {
+        return Heap_.front();
+    }
+}
+
+template <class T, size_t N, class C>
+auto TCompactHeap<T, N, C>::extract_min() -> value_type
+{
+    YT_ASSERT(!empty());
+
+    if (Y_LIKELY(IsInline())) {
+        auto minIt = std::max_element(Heap_.begin(), Heap_.end(), Comparator_);
+        std::swap(*minIt, Heap_.back());
+        auto value = Heap_.back();
+        Heap_.pop_back();
+
+        return value;
+    } else {
+        std::pop_heap(Heap_.begin(), Heap_.end(), Comparator_);
+        auto value = std::move(Heap_.back());
+        Heap_.pop_back();
+
+        return value;
+    }
+}
+
+template <class T, size_t N, class C>
+auto TCompactHeap<T, N, C>::begin() const -> const_iterator
+{
+    return Heap_.begin();
+}
+
+template <class T, size_t N, class C>
+auto TCompactHeap<T, N, C>::end() const -> const_iterator
+{
+    return Heap_.end();
+}
+
+template <class T, size_t N, class C>
+void TCompactHeap<T, N, C>::swap(TCompactHeap<T, N, C>& other)
+{
+    Heap_.swap(other.Heap_);
+    std::swap(Comparator_, other.Comparator_);
+}
+
+template <class T, size_t N, class C>
+size_t TCompactHeap<T, N, C>::size() const
+{
+    return Heap_.size();
+}
+
+template <class T, size_t N, class C>
+size_t TCompactHeap<T, N, C>::capacity() const
+{
+    return Heap_.capacity();
+}
+
+template <class T, size_t N, class C>
+size_t TCompactHeap<T, N, C>::max_size() const
+{
+    return Heap_.max_size();
+}
+
+template <class T, size_t N, class C>
+bool TCompactHeap<T, N, C>::empty() const
+{
+    return Heap_.empty();
+}
+
+template <class T, size_t N, class C>
+void TCompactHeap<T, N, C>::shrink_to_small()
+{
+    Heap_.shrink_to_small();
+}
+
+template <class T, size_t N, class C>
+bool TCompactHeap<T, N, C>::IsInline() const
+{
+    return Heap_.capacity() == N;
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+template <class T, size_t N, class C>
+TCompactHeap<T, N, C>::TReverseComparator::TReverseComparator(C underlying)
+    : Underlying_(std::move(underlying))
+{ }
+
+template <class T, size_t N, class C>
+bool TCompactHeap<T, N, C>::TReverseComparator::operator()(const T& lhs, const T& rhs) const
+{
+    return Underlying_(rhs, lhs);
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+} // namespace NYT
diff --git a/library/cpp/yt/compact_containers/compact_heap.h b/library/cpp/yt/compact_containers/compact_heap.h
new file mode 100644
index 00000000000..951b36962d7
--- /dev/null
+++ b/library/cpp/yt/compact_containers/compact_heap.h
@@ -0,0 +1,75 @@
+#pragma once
+
+#include "compact_vector.h"
+
+namespace NYT {
+
+////////////////////////////////////////////////////////////////////////////////
+
+//! A heap structure optimized for storing elements inline
+//! and with little memory overhead. See TCompactVector.
+/*!
+ *  When inline, uses linear search for selecting minimum
+ *  instead of storing heap.
+ */
+template <class T, size_t N, class C = std::less<T>>
+class TCompactHeap
+{
+public:
+    static_assert(N <= 8, "TCompactHeap is not optimal for large N");
+
+    explicit TCompactHeap(C comparator = C()) noexcept;
+
+    using value_type = T;
+
+    using const_reference = const T&;
+
+    using const_iterator = const T*;
+
+    using difference_type = ptrdiff_t;
+    using size_type = size_t;
+
+    void push(T value);
+    void pop();
+
+    const_reference get_min() const;
+    value_type extract_min();
+
+    const_iterator begin() const;
+    const_iterator end() const;
+
+    void swap(TCompactHeap<T, N, C>& other);
+
+    size_t size() const;
+    size_t capacity() const;
+    size_t max_size() const;
+
+    bool empty() const;
+
+    void shrink_to_small();
+
+private:
+    TCompactVector<T, N> Heap_;
+
+    class TReverseComparator
+    {
+    public:
+        explicit TReverseComparator(C underlying);
+
+        bool operator()(const T& lhs, const T& rhs) const;
+
+    private:
+        C Underlying_;
+    };
+    TReverseComparator Comparator_;
+
+    bool IsInline() const;
+};
+
+////////////////////////////////////////////////////////////////////////////////
+
+} // namespace NYT
+
+#define COMPACT_HEAP_INL_H_
+#include "compact_heap-inl.h"
+#undef COMPACT_HEAP_INL_H_
diff --git a/library/cpp/yt/compact_containers/compact_queue-inl.h b/library/cpp/yt/compact_containers/compact_queue-inl.h
new file mode 100644
index 00000000000..6e085ab260a
--- /dev/null
+++ b/library/cpp/yt/compact_containers/compact_queue-inl.h
@@ -0,0 +1,71 @@
+#include "compact_queue.h"
+
+namespace NYT {
+
+////////////////////////////////////////////////////////////////////////////////
+
+template <class T, size_t N>
+void TCompactQueue<T, N>::Push(T value)
+{
+    if (Size_ == Queue_.size()) {
+        auto oldSize = Queue_.size();
+        Queue_.resize(2 * oldSize);
+
+        if (FrontIndex_ + Size_ > oldSize) {
+            std::move(
+                Queue_.begin(),
+                Queue_.begin() + FrontIndex_,
+                Queue_.begin() + Size_);
+        }
+    }
+
+    auto index = FrontIndex_ + Size_;
+    if (index >= Queue_.size()) {
+        index -= Queue_.size();
+    }
+    Queue_[index] = std::move(value);
+    ++Size_;
+}
+
+template <class T, size_t N>
+T TCompactQueue<T, N>::Pop()
+{
+    YT_VERIFY(!Empty());
+
+    auto value = std::move(Queue_[FrontIndex_]);
+    ++FrontIndex_;
+    if (FrontIndex_ >= Queue_.size()) {
+        FrontIndex_ -= Queue_.size();
+    }
+    --Size_;
+
+    return value;
+}
+
+template <class T, size_t N>
+const T& TCompactQueue<T, N>::Front() const
+{
+    return Queue_[FrontIndex_];
+}
+
+template <class T, size_t N>
+size_t TCompactQueue<T, N>::Size() const
+{
+    return Size_;
+}
+
+template <class T, size_t N>
+size_t TCompactQueue<T, N>::Capacity() const
+{
+    return Queue_.capacity();
+}
+
+template <class T, size_t N>
+bool TCompactQueue<T, N>::Empty() const
+{
+    return Size_ == 0;
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+} // namespace NYT
diff --git a/library/cpp/yt/compact_containers/compact_queue.h b/library/cpp/yt/compact_containers/compact_queue.h
new file mode 100644
index 00000000000..1852d297065
--- /dev/null
+++ b/library/cpp/yt/compact_containers/compact_queue.h
@@ -0,0 +1,37 @@
+#pragma once
+
+#include "compact_vector.h"
+
+namespace NYT {
+
+////////////////////////////////////////////////////////////////////////////////
+
+//! A queue optimized for storing elements inline
+//! and with little memory overhead. See TCompactVector.
+template <class T, size_t N>
+class TCompactQueue
+{
+public:
+    void Push(T value);
+    T Pop();
+
+    const T& Front() const;
+
+    size_t Size() const;
+    size_t Capacity() const;
+
+    bool Empty() const;
+
+private:
+    TCompactVector<T, N> Queue_ = TCompactVector<T, N>(N);
+    size_t FrontIndex_ = 0;
+    size_t Size_ = 0;
+};
+
+////////////////////////////////////////////////////////////////////////////////
+
+} // namespace NYT
+
+#define COMPACT_QUEUE_INL_H_
+#include "compact_queue-inl.h"
+#undef COMPACT_QUEUE_INL_H_
diff --git a/library/cpp/yt/compact_containers/compact_set-inl.h b/library/cpp/yt/compact_containers/compact_set-inl.h
new file mode 100644
index 00000000000..20736f50833
--- /dev/null
+++ b/library/cpp/yt/compact_containers/compact_set-inl.h
@@ -0,0 +1,334 @@
+#ifndef COMPACT_SET_INL_H_
+#error "Direct inclusion of this file is not allowed, include compact_set.h"
+// For the sake of sane code completion.
+#include "compact_set.h"
+#endif
+
+#include <library/cpp/yt/assert/assert.h>
+
+namespace NYT {
+
+////////////////////////////////////////////////////////////////////////////////
+
+template <typename T, size_t N,  typename C, typename A>
+class TCompactSet<T, N, C, A>::const_iterator
+{
+private:
+    friend class TCompactSet<T, N, C, A>;
+
+    union
+    {
+        TVectorConstIterator VIter;
+        TSetConstIterator SIter;
+    };
+
+    bool Small;
+
+    const_iterator(TVectorConstIterator it)
+        : VIter(it)
+        , Small(true)
+    { }
+
+    const_iterator(TSetConstIterator it)
+        : SIter(it)
+        , Small(false)
+    { }
+
+    template <typename TOther>
+    void ConstructFrom(TOther&& rhs)
+    {
+        YT_ASSERT(Small == rhs.Small);
+
+        if (Small) {
+            new (&VIter)TVectorConstIterator(std::forward<TOther>(rhs).VIter);
+        } else {
+            new (&SIter)TSetConstIterator(std::forward<TOther>(rhs).SIter);
+        }
+    }
+
+    template <typename TOther>
+    const_iterator& AssignFrom(TOther&& rhs)
+    {
+        if (this == &rhs) {
+            return *this;
+        }
+
+        if (Small && rhs.Small) {
+            VIter = std::forward<TOther>(rhs).VIter;
+        } else if (!Small && !rhs.Small) {
+            SIter = std::forward<TOther>(rhs).SIter;
+        } else {
+            if (Small) {
+                VIter.~TVectorConstIterator();
+            } else {
+                SIter.~TSetConstIterator();
+            }
+
+            if (rhs.Small) {
+                new (&VIter)TVectorConstIterator(std::forward<TOther>(rhs).VIter);
+            } else {
+                new (&SIter)TSetConstIterator(std::forward<TOther>(rhs).SIter);
+            }
+        }
+
+        Small = rhs.Small;
+
+        return *this;
+    }
+
+public:
+    static_assert(std::is_same_v<
+        typename std::iterator_traits<TVectorConstIterator>::difference_type,
+        typename std::iterator_traits<TSetConstIterator>::difference_type>);
+    static_assert(std::is_same_v<
+        typename std::iterator_traits<TVectorConstIterator>::value_type,
+        typename std::iterator_traits<TSetConstIterator>::value_type>);
+    static_assert(std::is_same_v<
+        typename std::iterator_traits<TVectorConstIterator>::pointer,
+        typename std::iterator_traits<TSetConstIterator>::pointer>);
+    static_assert(std::is_same_v<
+        typename std::iterator_traits<TVectorConstIterator>::reference,
+        typename std::iterator_traits<TSetConstIterator>::reference>);
+
+    using difference_type = typename std::iterator_traits<TVectorConstIterator>::difference_type;
+    using value_type = typename std::iterator_traits<TVectorConstIterator>::value_type;
+    using pointer = typename std::iterator_traits<TVectorConstIterator>::pointer;
+    using reference = typename std::iterator_traits<TVectorConstIterator>::reference;
+    using iterator_category = std::bidirectional_iterator_tag;
+
+    const_iterator(const const_iterator& rhs)
+        : Small(rhs.Small)
+    {
+        ConstructFrom(rhs);
+    }
+
+    const_iterator(const_iterator&& rhs)
+        : Small(rhs.Small)
+    {
+        ConstructFrom(std::move(rhs));
+    }
+
+    ~const_iterator()
+    {
+        if (Small) {
+            VIter.~TVectorConstIterator();
+        } else {
+            SIter.~TSetConstIterator();
+        }
+    }
+
+    const_iterator& operator=(const const_iterator& rhs)
+    {
+        return AssignFrom(rhs);
+    }
+
+    const_iterator& operator=(const_iterator&& rhs)
+    {
+        return AssignFrom(std::move(rhs));
+    }
+
+    const_iterator& operator++()
+    {
+        if (Small) {
+            ++VIter;
+        } else {
+            ++SIter;
+        }
+
+        return *this;
+    }
+
+    const_iterator operator++(int)
+    {
+        auto result = *this;
+
+        if (Small) {
+            ++VIter;
+        } else {
+            ++SIter;
+        }
+
+        return result;
+    }
+
+    const_iterator& operator--()
+    {
+        if (Small) {
+            --VIter;
+        } else {
+            --SIter;
+        }
+
+        return *this;
+    }
+
+    const_iterator operator--(int)
+    {
+        auto result = *this;
+
+        if (Small) {
+            --VIter;
+        } else {
+            --SIter;
+        }
+
+        return result;
+    }
+
+    bool operator==(const const_iterator& rhs) const
+    {
+        if (Small != rhs.Small) {
+            return false;
+        }
+
+        return Small ? (VIter == rhs.VIter) : (SIter == rhs.SIter);
+    }
+
+    bool operator!=(const const_iterator& rhs) const
+    {
+        return !(*this == rhs);
+    }
+
+    const T& operator*() const
+    {
+        return Small ? *VIter : *SIter;
+    }
+
+    const T* operator->() const
+    {
+        return &operator*();
+    }
+};
+
+////////////////////////////////////////////////////////////////////////////////
+
+template <typename T, size_t N,  typename C, typename A>
+TCompactSet<T, N, C, A>::TCompactSet(const A& allocator)
+    : Set_(allocator)
+{ }
+
+template <typename T, size_t N,  typename C, typename A>
+bool TCompactSet<T, N, C, A>::empty() const
+{
+    return Vector_.empty() && Set_.empty();
+}
+
+template <typename T, size_t N,  typename C, typename A>
+typename TCompactSet<T, N, C, A>::size_type TCompactSet<T, N, C, A>::size() const
+{
+    return IsSmall() ? Vector_.size() : Set_.size();
+}
+
+template <typename T, size_t N,  typename C, typename A>
+const T& TCompactSet<T, N, C, A>::front() const
+{
+    return IsSmall() ? Vector_.front() : *Set_.begin();
+}
+
+template <typename T, size_t N,  typename C, typename A>
+typename TCompactSet<T, N, C, A>::size_type TCompactSet<T, N, C, A>::count(const T& v) const
+{
+    if (IsSmall()) {
+        return std::binary_search(Vector_.begin(), Vector_.end(), v, C()) ? 1 : 0;
+    } else {
+        return Set_.count(v);
+    }
+}
+
+template <typename T, size_t N,  typename C, typename A>
+bool TCompactSet<T, N, C, A>::contains(const T& v) const
+{
+    return count(v) == 1;
+}
+
+template <typename T, size_t N,  typename C, typename A>
+std::pair<typename TCompactSet<T, N, C, A>::const_iterator, bool> TCompactSet<T, N, C, A>::insert(const T& v)
+{
+    if (!IsSmall()) {
+        auto [it, inserted] = Set_.insert(v);
+        return {const_iterator(std::move(it)), inserted};
+    }
+
+    auto it = std::lower_bound(Vector_.begin(), Vector_.end(), v, C());
+    if (it != Vector_.end() && !C()(v, *it)) {
+        return {const_iterator(std::move(it)), false}; // Don't reinsert if it already exists.
+    }
+
+    if (Vector_.size() < N) {
+        auto newIt = Vector_.insert(it, v);
+        return {const_iterator(std::move(newIt)), true};
+    }
+
+    Set_.insert(Vector_.begin(), Vector_.end());
+    Vector_.clear();
+
+    auto [newIt, inserted] = Set_.insert(v);
+    YT_ASSERT(inserted);
+    return {const_iterator(std::move(newIt)), true};
+}
+
+template <typename T, size_t N,  typename C, typename A>
+template <typename TIter>
+void TCompactSet<T, N, C, A>::insert(TIter i, TIter e)
+{
+    for (; i != e; ++i) {
+        insert(*i);
+    }
+}
+
+template <typename T, size_t N,  typename C, typename A>
+bool TCompactSet<T, N, C, A>::erase(const T& v)
+{
+    if (!IsSmall()) {
+        return Set_.erase(v);
+    }
+
+    auto [rangeBegin, rangeEnd] = std::equal_range(Vector_.begin(), Vector_.end(), v, C());
+    if (rangeBegin != rangeEnd) {
+        Vector_.erase(rangeBegin, rangeEnd);
+        return true;
+    } else {
+        return false;
+    }
+}
+
+template <typename T, size_t N,  typename C, typename A>
+void TCompactSet<T, N, C, A>::clear()
+{
+    Vector_.clear();
+    Set_.clear();
+}
+
+template <typename T, size_t N,  typename C, typename A>
+typename TCompactSet<T, N, C, A>::const_iterator TCompactSet<T, N, C, A>::begin() const
+{
+    return IsSmall() ? const_iterator(Vector_.begin()) : const_iterator(Set_.begin());
+}
+
+template <typename T, size_t N,  typename C, typename A>
+typename TCompactSet<T, N, C, A>::const_iterator TCompactSet<T, N, C, A>::cbegin() const
+{
+    return begin();
+}
+
+template <typename T, size_t N,  typename C, typename A>
+typename TCompactSet<T, N, C, A>::const_iterator TCompactSet<T, N, C, A>::end() const
+{
+    return IsSmall() ? const_iterator(Vector_.end()) : const_iterator(Set_.end());
+}
+
+template <typename T, size_t N,  typename C, typename A>
+typename TCompactSet<T, N, C, A>::const_iterator TCompactSet<T, N, C, A>::cend() const
+{
+    return end();
+}
+
+template <typename T, size_t N,  typename C, typename A>
+bool TCompactSet<T, N, C, A>::IsSmall() const
+{
+    return Set_.empty();
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+} // namespace NYT
diff --git a/library/cpp/yt/compact_containers/compact_set.h b/library/cpp/yt/compact_containers/compact_set.h
new file mode 100644
index 00000000000..354fad195cd
--- /dev/null
+++ b/library/cpp/yt/compact_containers/compact_set.h
@@ -0,0 +1,92 @@
+// This is based on the following:
+//===- llvm/ADT/SmallSet.h - 'Normally small' sets --------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the CompactSet class.
+//
+//===----------------------------------------------------------------------===//
+
+#pragma once
+
+#include "compact_vector.h"
+
+#include <cstddef>
+#include <iterator>
+#include <set>
+#include <type_traits>
+
+namespace NYT {
+
+///////////////////////////////////////////////////////////////////////////////
+
+//! Maintains a set of unique values, optimizing for the case
+//! when the set is small (less than N).
+/*!
+ *  In this case, the set can be maintained with no mallocs.
+ *  If the set gets large, we expand to using an
+ *  std::set to maintain reasonable lookup times.
+ *
+ *  Note that any modification of the set may invalidate *all* iterators.
+ */
+template <typename T, size_t N, typename C = std::less<T>, typename A = std::allocator<T>>
+class TCompactSet
+{
+public:
+    class const_iterator;
+    using size_type = std::size_t;
+    using key_type = T;
+
+    TCompactSet() = default;
+    TCompactSet(const A& allocator);
+
+    [[nodiscard]] bool empty() const;
+
+    size_type size() const;
+
+    const T& front() const;
+
+    size_type count(const T& v) const;
+
+    bool contains(const T& v) const;
+
+    std::pair<const_iterator, bool> insert(const T& v);
+
+    template <typename TIter>
+    void insert(TIter i, TIter e);
+
+    bool erase(const T& v);
+
+    void clear();
+
+    const_iterator begin() const;
+    const_iterator cbegin() const;
+
+    const_iterator end() const;
+    const_iterator cend() const;
+
+private:
+    // Use a TCompactVector to hold the elements here (even though it will never
+    // reach its 'large' stage) to avoid calling the default ctors of elements
+    // we will never use.
+    TCompactVector<T, N> Vector_;
+    std::set<T, C, A> Set_;
+
+    using TSetConstIterator = typename std::set<T, C, A>::const_iterator;
+    using TVectorConstIterator = typename TCompactVector<T, N>::const_iterator;
+
+    bool IsSmall() const;
+};
+
+///////////////////////////////////////////////////////////////////////////////
+
+} // namespace NYT
+
+#define COMPACT_SET_INL_H_
+#include "compact_set-inl.h"
+#undef COMPACT_SET_INL_H_
diff --git a/library/cpp/yt/compact_containers/compact_vector-inl.h b/library/cpp/yt/compact_containers/compact_vector-inl.h
new file mode 100644
index 00000000000..3bb9576d3ea
--- /dev/null
+++ b/library/cpp/yt/compact_containers/compact_vector-inl.h
@@ -0,0 +1,1026 @@
+#ifndef COMPACT_VECTOR_INL_H_
+#error "Direct inclusion of this file is not allowed, include compact_vector.h"
+// For the sake of sane code completion.
+#include "compact_vector.h"
+#endif
+#undef COMPACT_VECTOR_INL_H_
+
+#include <library/cpp/yt/assert/assert.h>
+
+#include <library/cpp/yt/malloc/malloc.h>
+
+#include <library/cpp/yt/misc/hash.h>
+
+#include <util/system/compiler.h>
+
+#include <algorithm>
+#include <bit>
+
+#include <string.h>
+
+namespace NYT {
+
+////////////////////////////////////////////////////////////////////////////////
+
+static_assert(sizeof(uintptr_t) == 8);
+static_assert(std::endian::native == std::endian::little);
+
+////////////////////////////////////////////////////////////////////////////////
+
+template <class T>
+struct TCompactVectorOnHeapStorage
+{
+    T* End;
+    T* Capacity;
+    T Elements[0];
+};
+
+////////////////////////////////////////////////////////////////////////////////
+
+template <class TVector, class TPtr>
+class TCompactVectorReallocationPtrAdjuster
+{
+public:
+    TCompactVectorReallocationPtrAdjuster(TVector* vector, TPtr& ptr)
+        : Vector_(vector)
+        , Ptr_(ptr)
+        , Index_(ptr >= Vector_->begin() && ptr <= Vector_->end()
+            ? std::distance(Vector_->begin(), const_cast<typename TVector::iterator>(ptr))
+            : -1)
+    { }
+
+    ~TCompactVectorReallocationPtrAdjuster()
+    {
+        if (Index_ >= 0) {
+            Ptr_ = Vector_->begin() + Index_;
+        }
+    }
+
+private:
+    TVector* const Vector_;
+    TPtr& Ptr_;
+    const ptrdiff_t Index_;
+};
+
+template <class TVector>
+class TCompactVectorReallocationPtrAdjuster<TVector, std::nullptr_t>
+{
+public:
+    TCompactVectorReallocationPtrAdjuster(TVector* /*vector*/, std::nullptr_t /*ptr*/)
+    { }
+};
+
+////////////////////////////////////////////////////////////////////////////////
+
+template <class T, size_t N>
+TCompactVector<T, N>::TCompactVector() noexcept
+{
+    InlineMeta_.SizePlusOne = 1;
+}
+
+template <class T, size_t N>
+TCompactVector<T, N>::TCompactVector(const TCompactVector& other)
+    : TCompactVector()
+{
+    assign(other.begin(), other.end());
+}
+
+template <class T, size_t N>
+template <size_t OtherN>
+TCompactVector<T, N>::TCompactVector(const TCompactVector<T, OtherN>& other)
+    : TCompactVector()
+{
+    assign(other.begin(), other.end());
+}
+
+template <class T, size_t N>
+TCompactVector<T, N>::TCompactVector(TCompactVector&& other) noexcept(std::is_nothrow_move_constructible_v<T>)
+    : TCompactVector()
+{
+    swap(other);
+}
+
+template <class T, size_t N>
+template <size_t OtherN>
+TCompactVector<T, N>::TCompactVector(TCompactVector<T, OtherN>&& other)
+    : TCompactVector()
+{
+    swap(other);
+}
+
+template <class T, size_t N>
+TCompactVector<T, N>::TCompactVector(size_type count)
+    : TCompactVector()
+{
+    assign(count, T());
+}
+
+template <class T, size_t N>
+TCompactVector<T, N>::TCompactVector(size_type count, const T& value)
+    : TCompactVector()
+{
+    assign(count, value);
+}
+
+template <class T, size_t N>
+template <class TIterator>
+TCompactVector<T, N>::TCompactVector(TIterator first, TIterator last)
+    : TCompactVector()
+{
+    assign(first, last);
+}
+
+template <class T, size_t N>
+TCompactVector<T, N>::TCompactVector(std::initializer_list<T> list)
+    : TCompactVector()
+{
+    assign(list.begin(), list.end());
+}
+
+template <class T, size_t N>
+TCompactVector<T, N>::~TCompactVector()
+{
+    if (Y_LIKELY(IsInline())) {
+        Destroy(&InlineElements_[0], &InlineElements_[InlineMeta_.SizePlusOne - 1]);
+    } else {
+        auto* storage = OnHeapMeta_.Storage;
+        Destroy(storage->Elements, storage->End);
+        ::free(storage);
+    }
+}
+
+template <class T, size_t N>
+bool TCompactVector<T, N>::empty() const
+{
+    if (Y_LIKELY(IsInline())) {
+        return InlineMeta_.SizePlusOne == 1;
+    } else {
+        const auto* storage = OnHeapMeta_.Storage;
+        return storage->Elements == storage->End;
+    }
+}
+
+template <class T, size_t N>
+auto TCompactVector<T, N>::begin() -> iterator
+{
+    return Y_LIKELY(IsInline()) ? &InlineElements_[0] : OnHeapMeta_.Storage->Elements;
+}
+
+template <class T, size_t N>
+auto TCompactVector<T, N>::begin() const -> const_iterator
+{
+    return const_cast<TCompactVector*>(this)->begin();
+}
+
+template <class T, size_t N>
+auto TCompactVector<T, N>::end() -> iterator
+{
+    return Y_LIKELY(IsInline()) ? &InlineElements_[InlineMeta_.SizePlusOne - 1] : OnHeapMeta_.Storage->End;
+}
+
+template <class T, size_t N>
+auto TCompactVector<T, N>::end() const -> const_iterator
+{
+    return const_cast<TCompactVector*>(this)->end();
+}
+
+template <class T, size_t N>
+auto TCompactVector<T, N>::rbegin() -> reverse_iterator
+{
+    return static_cast<reverse_iterator>(end());
+}
+
+template <class T, size_t N>
+auto TCompactVector<T, N>::rbegin() const -> const_reverse_iterator
+{
+    return static_cast<const_reverse_iterator>(end());
+}
+
+template <class T, size_t N>
+auto TCompactVector<T, N>::rend() -> reverse_iterator
+{
+    return static_cast<reverse_iterator>(begin());
+}
+
+template <class T, size_t N>
+auto TCompactVector<T, N>::rend() const -> const_reverse_iterator
+{
+    return static_cast<const_reverse_iterator>(begin());
+}
+
+template <class T, size_t N>
+auto TCompactVector<T, N>::size() const -> size_type
+{
+    if (Y_LIKELY(IsInline())) {
+        return InlineMeta_.SizePlusOne - 1;
+    } else {
+        const auto* storage = OnHeapMeta_.Storage;
+        return storage->End - storage->Elements;
+    }
+}
+
+template <class T, size_t N>
+auto TCompactVector<T, N>::capacity() const -> size_type
+{
+    if (Y_LIKELY(IsInline())) {
+        return N;
+    } else {
+        const auto* storage = OnHeapMeta_.Storage;
+        return storage->Capacity - storage->Elements;
+    }
+}
+
+template <class T, size_t N>
+auto TCompactVector<T, N>::max_size() const -> size_type
+{
+    return static_cast<size_type>(-1) / sizeof(T);
+}
+
+template <class T, size_t N>
+auto TCompactVector<T, N>::data() -> pointer
+{
+    return static_cast<pointer>(begin());
+}
+
+template <class T, size_t N>
+auto TCompactVector<T, N>::data() const -> const_pointer
+{
+    return static_cast<const_pointer>(begin());
+}
+
+template <class T, size_t N>
+auto TCompactVector<T, N>::operator[](size_type index) -> reference
+{
+    YT_ASSERT(index < size());
+    return begin()[index];
+}
+
+template <class T, size_t N>
+auto TCompactVector<T, N>::operator[](size_type index) const -> const_reference
+{
+    return const_cast<TCompactVector*>(this)->operator[](index);
+}
+
+template <class T, size_t N>
+auto TCompactVector<T, N>::front() -> reference
+{
+    YT_ASSERT(!empty());
+    return begin()[0];
+}
+
+template <class T, size_t N>
+auto TCompactVector<T, N>::front() const -> const_reference
+{
+    return const_cast<TCompactVector*>(this)->front();
+}
+
+template <class T, size_t N>
+auto TCompactVector<T, N>::back() -> reference
+{
+    YT_ASSERT(!empty());
+    return end()[-1];
+}
+
+template <class T, size_t N>
+auto TCompactVector<T, N>::back() const -> const_reference
+{
+    return const_cast<TCompactVector*>(this)->back();
+}
+
+template <class T, size_t N>
+void TCompactVector<T, N>::push_back(const T& value)
+{
+    PushBackImpl(
+        &value,
+        [&] (T* dst, const T* value) {
+            ::new(dst) T(*value);
+        });
+}
+
+template <class T, size_t N>
+void TCompactVector<T, N>::push_back(T&& value)
+{
+    PushBackImpl(
+        &value,
+        [&] (T* dst, T* value) {
+            ::new(dst) T(std::move(*value));
+        });
+}
+
+template <class T, size_t N>
+template <class... TArgs>
+auto TCompactVector<T, N>::emplace(const_iterator pos, TArgs&&... args) -> iterator
+{
+    return InsertOneImpl(
+        pos,
+        nullptr,
+        [&] (auto* dst, std::nullptr_t) {
+            ::new(dst) T(std::forward<TArgs>(args)...);
+        },
+        [&] (auto* dst, std::nullptr_t) {
+            *dst = T(std::forward<TArgs>(args)...);
+        });
+}
+
+template <class T, size_t N>
+template <class... TArgs>
+auto TCompactVector<T, N>::emplace_back(TArgs&&... args) -> reference
+{
+    return PushBackImpl(
+        nullptr,
+        [&] (T* dst, std::nullptr_t) {
+            ::new(dst) T(std::forward<TArgs>(args)...);
+        });
+}
+
+template <class T, size_t N>
+void TCompactVector<T, N>::pop_back()
+{
+    YT_ASSERT(!empty());
+
+    if (Y_LIKELY(IsInline())) {
+        InlineElements_[InlineMeta_.SizePlusOne - 2].T::~T();
+        --InlineMeta_.SizePlusOne;
+    } else {
+        auto* storage = OnHeapMeta_.Storage;
+        storage->End[-1].T::~T();
+        --storage->End;
+    }
+}
+
+template <class T, size_t N>
+auto TCompactVector<T, N>::erase(const_iterator pos) -> iterator
+{
+    YT_ASSERT(pos >= begin());
+    YT_ASSERT(pos < end());
+
+    auto* mutablePos = const_cast<iterator>(pos);
+    Move(mutablePos + 1, end(), mutablePos);
+    pop_back();
+
+    return mutablePos;
+}
+
+template <class T, size_t N>
+auto TCompactVector<T, N>::erase(const_iterator first, const_iterator last) -> iterator
+{
+    YT_ASSERT(first >= begin());
+    YT_ASSERT(last <= end());
+
+    auto* mutableFirst = const_cast<iterator>(first);
+    auto* mutableLast = const_cast<iterator>(last);
+    auto count = std::distance(mutableFirst, mutableLast);
+
+    if (Y_LIKELY(IsInline())) {
+        auto* end = &InlineElements_[0] + InlineMeta_.SizePlusOne - 1;
+        Move(mutableLast, end, mutableFirst);
+        Destroy(end - count, end);
+        InlineMeta_.SizePlusOne -= count;
+    } else {
+        auto* storage = OnHeapMeta_.Storage;
+        auto* end = storage->End;
+        Move(mutableLast, storage->End, mutableFirst);
+        Destroy(end - count, end);
+        storage->End -= count;
+    }
+
+    return mutableFirst;
+}
+
+template <class T, size_t N>
+void TCompactVector<T, N>::clear()
+{
+    if (Y_LIKELY(IsInline())) {
+        Destroy(&InlineElements_[0], &InlineElements_[InlineMeta_.SizePlusOne - 1]);
+        InlineMeta_.SizePlusOne = 1;
+    } else {
+        auto* storage = OnHeapMeta_.Storage;
+        Destroy(storage->Elements, storage->End);
+        storage->End = storage->Elements;
+    }
+}
+
+template <class T, size_t N>
+void TCompactVector<T, N>::resize(size_type newSize)
+{
+    ResizeImpl(
+        newSize,
+        [] (auto* dst) {
+            ::new(dst) T();
+        });
+}
+
+template <class T, size_t N>
+void TCompactVector<T, N>::resize(size_type newSize, const T& value)
+{
+    ResizeImpl(
+        newSize,
+        [&] (auto* dst) {
+            ::new(dst) T(value);
+        });
+}
+
+template <class T, size_t N>
+void TCompactVector<T, N>::reserve(size_t newCapacity)
+{
+    if (Y_UNLIKELY(newCapacity > N)) {
+        EnsureOnHeapCapacity(newCapacity, /*incremental*/ false);
+    }
+}
+
+template <class T, size_t N>
+void TCompactVector<T, N>::swap(TCompactVector& other)
+{
+    if (this == &other) {
+        return;
+    }
+
+    if (!IsInline() && !other.IsInline()) {
+        std::swap(OnHeapMeta_.Storage, other.OnHeapMeta_.Storage);
+        return;
+    }
+
+    auto* lhs = this;
+    auto* rhs = &other;
+    if (lhs->size() < rhs->size()) {
+        std::swap(lhs, rhs);
+    }
+
+    size_t rhsSize = rhs->size();
+    size_t lhsSize = lhs->size();
+    if (lhsSize > rhs->capacity()) {
+        rhs->EnsureOnHeapCapacity(lhs->size(), /*incremental*/ false);
+    }
+
+    for (size_t index = 0; index < rhsSize; ++index) {
+        std::swap((*lhs)[index], (*rhs)[index]);
+    }
+
+    UninitializedMove(lhs->begin() + rhsSize, lhs->end(), rhs->end());
+    Destroy(lhs->begin() + rhsSize, lhs->end());
+
+    rhs->SetSize(lhsSize);
+    lhs->SetSize(rhsSize);
+}
+
+template <class T, size_t N>
+void TCompactVector<T, N>::assign(size_type count, const T& value)
+{
+    clear();
+
+    if (Y_UNLIKELY(count > capacity())) {
+        EnsureOnHeapCapacity(count, /*incremental*/ false);
+    }
+
+    auto* dst = begin();
+    std::uninitialized_fill(dst, dst + count, value);
+
+    SetSize(count);
+}
+
+template <class T, size_t N>
+template <class TIterator>
+void TCompactVector<T, N>::assign(TIterator first, TIterator last)
+{
+    clear();
+
+    auto count = std::distance(first, last);
+    if (Y_UNLIKELY(count > static_cast<ptrdiff_t>(capacity()))) {
+        EnsureOnHeapCapacity(count, /*incremental*/ false);
+    }
+
+    std::uninitialized_copy(first, last, begin());
+
+    SetSize(count);
+}
+
+template <class T, size_t N>
+void TCompactVector<T, N>::assign(std::initializer_list<T> list)
+{
+    assign(list.begin(), list.end());
+}
+
+template <class T, size_t N>
+template <size_t OtherN>
+void TCompactVector<T, N>::assign(const TCompactVector<T, OtherN>& other)
+{
+    if constexpr(N == OtherN) {
+        if (this == &other) {
+            return;
+        }
+    }
+
+    auto otherSize = other.size();
+    auto otherBegin = other.begin();
+
+    if (capacity() >= otherSize) {
+        const auto* src = other.begin();
+        auto* dst = begin();
+
+        auto thisSize = size();
+        auto copySize = std::min(thisSize, otherSize);
+        Copy(src, src + copySize, dst);
+        src += copySize;
+        dst += copySize;
+
+        auto uninitializedCopySize = otherSize - copySize;
+        UninitializedCopy(src, src + uninitializedCopySize, dst);
+        // NB: src += uninitializedCopySize is not needed.
+        dst += uninitializedCopySize;
+
+        if (thisSize > otherSize) {
+            Destroy(dst, end());
+        }
+
+        SetSize(otherSize);
+        return;
+    }
+
+    clear();
+
+    EnsureOnHeapCapacity(otherSize, /*incremental*/ false);
+
+    YT_ASSERT(!IsInline());
+    auto* storage = OnHeapMeta_.Storage;
+    UninitializedCopy(otherBegin, otherBegin + otherSize, storage->Elements);
+    storage->End = storage->Elements + otherSize;
+}
+
+template <class T, size_t N>
+template <size_t OtherN>
+void TCompactVector<T, N>::assign(TCompactVector<T, OtherN>&& other)
+{
+    if constexpr(N == OtherN) {
+        if (this == &other) {
+            return;
+        }
+    }
+
+    clear();
+
+    if (!other.IsInline()) {
+        if (Y_UNLIKELY(!IsInline())) {
+            ::free(OnHeapMeta_.Storage);
+        }
+        OnHeapMeta_.Storage = other.OnHeapMeta_.Storage;
+        other.InlineMeta_.SizePlusOne = 1;
+        return;
+    }
+
+    auto otherSize = other.size();
+    if (Y_UNLIKELY(otherSize > capacity())) {
+        EnsureOnHeapCapacity(otherSize, /*incremental*/ false);
+    }
+
+    auto* otherBegin = other.begin();
+    UninitializedMove(otherBegin, otherBegin + otherSize, begin());
+    SetSize(otherSize);
+
+    other.clear();
+}
+
+template <class T, size_t N>
+auto TCompactVector<T, N>::operator=(const TCompactVector& other) -> TCompactVector&
+{
+    assign(other);
+    return *this;
+}
+
+template <class T, size_t N>
+template <size_t OtherN>
+auto TCompactVector<T, N>::operator=(const TCompactVector<T, OtherN>& other) -> TCompactVector&
+{
+    assign(other);
+    return *this;
+}
+
+template <class T, size_t N>
+auto TCompactVector<T, N>::operator=(TCompactVector&& other) -> TCompactVector&
+{
+    assign(std::move(other));
+    return *this;
+}
+
+template <class T, size_t N>
+template <size_t OtherN>
+auto TCompactVector<T, N>::operator=(TCompactVector<T, OtherN>&& other) -> TCompactVector&
+{
+    assign(std::move(other));
+    return *this;
+}
+
+template <class T, size_t N>
+auto TCompactVector<T, N>::operator=(std::initializer_list<T> list) -> TCompactVector&
+{
+    assign(list);
+    return *this;
+}
+
+template <class T, size_t N>
+auto TCompactVector<T, N>::insert(const_iterator pos, const T& value) -> iterator
+{
+    return InsertOneImpl(
+        pos,
+        &value,
+        [&] (auto* dst, const auto* value) {
+            ::new(dst) T(*value);
+        },
+        [&] (auto* dst, const auto* value) {
+            *dst = *value;
+        });
+}
+
+template <class T, size_t N>
+auto TCompactVector<T, N>::insert(const_iterator pos, T&& value) -> iterator
+{
+    return InsertOneImpl(
+        pos,
+        &value,
+        [&] (auto* dst, auto* value) {
+            ::new(dst) T(std::move(*value));
+        },
+        [&] (auto* dst, auto* value) {
+            *dst = std::move(*value);
+        });
+}
+
+template <class T, size_t N>
+auto TCompactVector<T, N>::insert(const_iterator pos, size_type count, const T& value) -> iterator
+{
+    return InsertManyImpl(
+        pos,
+        count,
+        [&] (auto* dstFirst, auto* dstLast) {
+            for (auto* dst = dstFirst; dst != dstLast; ++dst) {
+                ::new(dst) T(value);
+            }
+        },
+        [&] (auto* dstFirst, auto* dstLast) {
+            for (auto* dst = dstFirst; dst != dstLast; ++dst) {
+                *dst = value;
+            }
+        });
+}
+
+template <class T, size_t N>
+template <class TIterator>
+auto TCompactVector<T, N>::insert(const_iterator pos, TIterator first, TIterator last) -> iterator
+{
+    auto current = first;
+    return InsertManyImpl(
+        pos,
+        std::distance(first, last),
+        [&] (auto* dstFirst, auto* dstLast) {
+            for (auto* dst = dstFirst; dst != dstLast; ++dst) {
+                ::new(dst) T(*current++);
+            }
+        },
+        [&] (auto* dstFirst, auto* dstLast) {
+            for (auto* dst = dstFirst; dst != dstLast; ++dst) {
+                *dst = *current++;
+            }
+        });
+}
+
+template <class T, size_t N>
+auto TCompactVector<T, N>::insert(const_iterator pos, std::initializer_list<T> list) -> iterator
+{
+    return insert(pos, list.begin(), list.end());
+}
+
+template <class T, size_t N>
+void TCompactVector<T, N>::shrink_to_small()
+{
+    if (Y_LIKELY(IsInline())) {
+        return;
+    }
+
+    auto size = this->size();
+    if (size > N) {
+        return;
+    }
+
+    auto* storage = OnHeapMeta_.Storage;
+    UninitializedMove(storage->Elements, storage->End, &InlineElements_[0]);
+    Destroy(storage->Elements, storage->End);
+    ::free(storage);
+
+    InlineMeta_.SizePlusOne = size + 1;
+}
+
+template <class T, size_t N>
+bool TCompactVector<T, N>::IsInline() const
+{
+    return InlineMeta_.SizePlusOne != 0;
+}
+
+template <class T, size_t N>
+void TCompactVector<T, N>::SetSize(size_t newSize)
+{
+    if (Y_LIKELY(IsInline())) {
+        InlineMeta_.SizePlusOne = newSize + 1;
+    } else {
+        auto* storage = OnHeapMeta_.Storage;
+        storage->End = storage->Elements + newSize;
+    }
+}
+
+template <class T, size_t N>
+void TCompactVector<T, N>::EnsureOnHeapCapacity(size_t newCapacity, bool incremental)
+{
+    newCapacity = std::max(newCapacity, N + 1);
+    if (incremental) {
+        newCapacity = std::max(newCapacity, capacity() * 2);
+    }
+
+    auto byteSize = sizeof(TOnHeapStorage) + newCapacity * sizeof(T);
+    byteSize = nallocx(byteSize, 0);
+
+    newCapacity = (byteSize - sizeof(TOnHeapStorage)) / sizeof(T);
+
+    auto* newStorage = static_cast<TOnHeapStorage*>(::malloc(byteSize));
+    YT_VERIFY((reinterpret_cast<uintptr_t>(newStorage) >> 56) == 0);
+
+    newStorage->Capacity = newStorage->Elements + newCapacity;
+
+    size_t size;
+    if (IsInline()) {
+        size = InlineMeta_.SizePlusOne - 1;
+        UninitializedMove(&InlineElements_[0], &InlineElements_[0] + size, newStorage->Elements);
+        Destroy(&InlineElements_[0], &InlineElements_[0] + size);
+    } else {
+        auto* storage = OnHeapMeta_.Storage;
+        size = storage->End - storage->Elements;
+        UninitializedMove(storage->Elements, storage->End, newStorage->Elements);
+        Destroy(storage->Elements, storage->End);
+        ::free(storage);
+    }
+
+    newStorage->End = newStorage->Elements + size;
+    OnHeapMeta_.Storage = newStorage;
+}
+
+template <class T, size_t N>
+template <class TPtr, class F>
+auto TCompactVector<T, N>::PushBackImpl(TPtr valuePtr, F&& func) -> reference
+{
+    auto sizePlusOne = InlineMeta_.SizePlusOne;
+    if (Y_LIKELY(sizePlusOne != 0 && sizePlusOne != N + 1)) {
+        auto* dst = &InlineElements_[sizePlusOne - 1];
+        func(dst, valuePtr);
+        ++InlineMeta_.SizePlusOne;
+        return *dst;
+    }
+
+    auto hasSpareOnHeapCapacity = [&] {
+        if (sizePlusOne != 0) {
+            return false;
+        }
+        auto* storage = OnHeapMeta_.Storage;
+        return storage->End < storage->Capacity;
+    };
+
+    if (Y_UNLIKELY(!hasSpareOnHeapCapacity())) {
+        TCompactVectorReallocationPtrAdjuster<TCompactVector, TPtr> valuePtrAdjuster(this, valuePtr);
+        EnsureOnHeapCapacity(0, /*incremental*/ true);
+    }
+
+    YT_ASSERT(!IsInline());
+    auto* storage = OnHeapMeta_.Storage;
+    auto* dst = storage->End++;
+    func(dst, valuePtr);
+
+    return *dst;
+}
+
+template <class T, size_t N>
+template <class F>
+void TCompactVector<T, N>::ResizeImpl(size_type newSize, F&& func)
+{
+    auto size = this->size();
+    if (newSize > size) {
+        if (Y_UNLIKELY(newSize > capacity())) {
+            EnsureOnHeapCapacity(newSize, /*incremental*/ false);
+        }
+
+        auto* first = end();
+        auto* last = first + newSize - size;
+        for (auto* current = first; current != last; ++current) {
+            func(current);
+        }
+    } else if (newSize < size) {
+        Destroy(begin() + newSize, end());
+    }
+
+    SetSize(newSize);
+}
+
+template <class T, size_t N>
+template <class TPtr, class UninitializedF, class InitializedF>
+auto TCompactVector<T, N>::InsertOneImpl(const_iterator pos, TPtr valuePtr, UninitializedF&& uninitializedFunc, InitializedF&& initializedFunc) -> iterator
+{
+    YT_ASSERT(pos >= begin());
+    YT_ASSERT(pos <= end());
+
+    auto* mutablePos = const_cast<iterator>(pos);
+
+    auto newSize = size() + 1;
+    if (Y_UNLIKELY(newSize > capacity())) {
+        TCompactVectorReallocationPtrAdjuster<TCompactVector, iterator> mutablePosAdjuster(this, mutablePos);
+        TCompactVectorReallocationPtrAdjuster<TCompactVector, TPtr> valuePtrAdjuster(this, valuePtr);
+        EnsureOnHeapCapacity(newSize, /*incremental*/ true);
+    }
+
+    auto* end = this->end();
+
+    if constexpr(!std::is_same_v<TPtr, std::nullptr_t>) {
+        if (valuePtr >= mutablePos && valuePtr < end) {
+            ++valuePtr;
+        }
+    }
+
+    auto moveCount = std::distance(mutablePos, end);
+    if (moveCount == 0) {
+        uninitializedFunc(end, valuePtr);
+    } else {
+        if constexpr(std::is_trivially_copyable_v<T>) {
+            ::memmove(mutablePos + 1, mutablePos, moveCount * sizeof(T));
+        } else {
+            ::new(end) T(std::move(end[-1]));
+            MoveBackward(mutablePos, end - 1, mutablePos + 1);
+        }
+        initializedFunc(mutablePos, valuePtr);
+    }
+
+    SetSize(newSize);
+
+    return mutablePos;
+}
+
+template <class T, size_t N>
+template <class UninitializedF, class InitializedF>
+auto TCompactVector<T, N>::InsertManyImpl(const_iterator pos, size_t insertCount, UninitializedF&& uninitializedFunc, InitializedF&& initializedFunc) -> iterator
+{
+    YT_ASSERT(pos >= begin());
+    YT_ASSERT(pos <= end());
+
+    auto* mutablePos = const_cast<iterator>(pos);
+    if (insertCount == 0) {
+        return mutablePos;
+    }
+
+    auto size = this->size();
+    auto newSize = size + insertCount;
+    if (Y_UNLIKELY(newSize > capacity())) {
+        auto index = std::distance(begin(), mutablePos);
+        EnsureOnHeapCapacity(newSize, /*incremental*/ true);
+        mutablePos = begin() + index;
+    }
+
+    auto* end = this->end();
+    auto moveCount = std::distance(mutablePos, end);
+    if constexpr(std::is_trivially_copyable_v<T>) {
+        ::memmove(mutablePos + insertCount, mutablePos, moveCount * sizeof(T));
+        initializedFunc(mutablePos, mutablePos + insertCount);
+    } else {
+        if (static_cast<ptrdiff_t>(insertCount) >= moveCount) {
+            UninitializedMove(mutablePos, end, mutablePos + insertCount);
+            initializedFunc(mutablePos, end);
+            uninitializedFunc(end, end + insertCount - moveCount);
+        } else {
+            auto overlapCount = moveCount - insertCount;
+            UninitializedMove(mutablePos + overlapCount, end, mutablePos + overlapCount + insertCount);
+            MoveBackward(mutablePos, mutablePos + overlapCount, mutablePos + insertCount);
+            initializedFunc(mutablePos, mutablePos + insertCount);
+        }
+    }
+
+    SetSize(newSize);
+
+    return mutablePos;
+}
+
+template <class T, size_t N>
+void TCompactVector<T, N>::Destroy(T* first, T* last)
+{
+    if constexpr(!std::is_trivially_destructible_v<T>) {
+        for (auto* current = first; current != last; ++current) {
+            current->T::~T();
+        }
+    }
+}
+
+template <class T, size_t N>
+template <class T1, class T2>
+void TCompactVector<T, N>::Copy(const T1* srcFirst, const T1* srcLast, T2* dst)
+{
+    if constexpr(std::is_trivially_copyable_v<T1> && std::is_same_v<T1, T2>) {
+        ::memcpy(dst, srcFirst, (srcLast - srcFirst) * sizeof(T));
+    } else {
+        std::copy(srcFirst, srcLast, dst);
+    }
+}
+
+template <class T, size_t N>
+template <class T1, class T2>
+void TCompactVector<T, N>::UninitializedCopy(const T1* srcFirst, const T1* srcLast, T2* dst)
+{
+    if constexpr(std::is_trivially_copyable_v<T1> && std::is_same_v<T1, T2>) {
+        ::memcpy(dst, srcFirst, (srcLast - srcFirst) * sizeof(T));
+    } else {
+        std::uninitialized_copy(srcFirst, srcLast, dst);
+    }
+}
+
+template <class T, size_t N>
+void TCompactVector<T, N>::Move(T* srcFirst, T* srcLast, T* dst)
+{
+    if constexpr(std::is_trivially_copyable_v<T>) {
+        ::memmove(dst, srcFirst, (srcLast - srcFirst) * sizeof(T));
+    } else {
+        std::move(srcFirst, srcLast, dst);
+    }
+}
+
+template <class T, size_t N>
+void TCompactVector<T, N>::UninitializedMove(T* srcFirst, T* srcLast, T* dst)
+{
+    if constexpr(std::is_trivially_copyable_v<T>) {
+        ::memcpy(dst, srcFirst, (srcLast - srcFirst) * sizeof(T));
+    } else {
+        std::uninitialized_move(srcFirst, srcLast, dst);
+    }
+}
+
+template <class T, size_t N>
+void TCompactVector<T, N>::MoveBackward(T* srcFirst, T* srcLast, T* dst)
+{
+    auto* src = srcLast;
+    dst += std::distance(srcFirst, srcLast);
+    while (src > srcFirst) {
+        *--dst = std::move(*--src);
+    }
+}
+
+/////////////////////////////////////////////////////////////////////////////
+
+template <class T, size_t LhsN, size_t RhsN>
+bool operator==(const TCompactVector<T, LhsN>& lhs, const TCompactVector<T, RhsN>& rhs)
+{
+    if constexpr(LhsN == RhsN) {
+        if (&lhs == &rhs) {
+            return true;
+        }
+    }
+
+    if (lhs.size() != rhs.size()) {
+        return false;
+    }
+
+    return std::equal(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
+}
+
+template <class T, size_t LhsN, size_t RhsN>
+bool operator!=(const TCompactVector<T, LhsN>& lhs, const TCompactVector<T, RhsN>& rhs)
+{
+    return !(lhs == rhs);
+}
+
+template <class T, size_t LhsN, size_t RhsN>
+bool operator<(const TCompactVector<T, LhsN>& lhs, const TCompactVector<T, RhsN>& rhs)
+{
+    return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+template <class T, size_t N>
+void swap(TCompactVector<T, N>& lhs, TCompactVector<T, N>& rhs) // NOLINT
+{
+    lhs.swap(rhs);
+}
+
+/////////////////////////////////////////////////////////////////////////////
+
+} // namespace NYT
+
+namespace std {
+
+////////////////////////////////////////////////////////////////////////////////
+
+template <class T, size_t N>
+struct hash<NYT::TCompactVector<T, N>>
+{
+    size_t operator()(const NYT::TCompactVector<T, N>& container) const
+    {
+        size_t result = 0;
+        for (const auto& element : container) {
+            NYT::HashCombine(result, element);
+        }
+        return result;
+    }
+};
+
+////////////////////////////////////////////////////////////////////////////////
+
+} // namespace std
diff --git a/library/cpp/yt/compact_containers/compact_vector.h b/library/cpp/yt/compact_containers/compact_vector.h
new file mode 100644
index 00000000000..07fd9f89244
--- /dev/null
+++ b/library/cpp/yt/compact_containers/compact_vector.h
@@ -0,0 +1,230 @@
+#pragma once
+
+#include <util/system/defaults.h>
+
+#include <cstdint>
+#include <iterator>
+#include <limits>
+
+namespace NYT {
+
+////////////////////////////////////////////////////////////////////////////////
+
+template <class T>
+struct TCompactVectorOnHeapStorage;
+
+//! A vector-like structure optimized for storing elements inline
+//! and with little memory overhead.
+/*!
+ *  Stores up to #N (<= 254) elements inline.
+ *
+ *  When capacity starts exceeding #N, moves all elements to heap;
+ *  \see #TCompactVectorOnHeapStorage.
+ *
+ *  When linked with YTAlloc, employs its API to adjust the on-heap capacity in accordance
+ *  to the actual size of the allocated region.
+ *
+ *  Assuming the entropy and the alignment constraints, yields a seemingly optimal memory overhead.
+ *  E.g. TCompactVector<uint8_t, 7> takes 8 bytes and TCompactVector<uint32_t, 3> takes 16 bytes.
+ *  \see #ByteSize.
+ *
+ *  Assumes (and asserts) the following:
+ *  1) the platform is 64 bit;
+ *  2) the highest 8 bits of pointers returned by |malloc| are zeroes;
+ *  3) the platform is little-endian.
+ */
+template <class T, size_t N>
+class TCompactVector
+{
+public:
+    static_assert(N < std::numeric_limits<uint8_t>::max());
+
+    using size_type = size_t;
+    using difference_type = ptrdiff_t;
+
+    using value_type = T;
+
+    using iterator = T*;
+    using const_iterator = const T*;
+
+    using const_reverse_iterator = std::reverse_iterator<const_iterator>;
+    using reverse_iterator = std::reverse_iterator<iterator>;
+
+    using reference = T&;
+    using const_reference = const T&;
+
+    using pointer = T*;
+    using const_pointer = const T*;
+
+    TCompactVector() noexcept;
+    TCompactVector(const TCompactVector& other);
+    template <size_t OtherN>
+    TCompactVector(const TCompactVector<T, OtherN>& other);
+    TCompactVector(TCompactVector&& other) noexcept(std::is_nothrow_move_constructible_v<T>);
+    template <size_t OtherN>
+    TCompactVector(TCompactVector<T, OtherN>&& other);
+    explicit TCompactVector(size_type count);
+    TCompactVector(size_type count, const T& value);
+    template <class TIterator>
+    TCompactVector(TIterator first, TIterator last);
+    TCompactVector(std::initializer_list<T> list);
+
+    ~TCompactVector();
+
+    [[nodiscard]] bool empty() const;
+
+    iterator begin();
+    const_iterator begin() const;
+    iterator end();
+    const_iterator end() const;
+
+    reverse_iterator rbegin();
+    const_reverse_iterator rbegin() const;
+    reverse_iterator rend();
+    const_reverse_iterator rend() const;
+
+    size_type size() const;
+    size_type capacity() const;
+    size_type max_size() const;
+
+    pointer data();
+    const_pointer data() const;
+
+    reference operator[](size_type index);
+    const_reference operator[](size_type index) const;
+
+    reference front();
+    const_reference front() const;
+    reference back();
+    const_reference back() const;
+
+    void push_back(const T& value);
+    void push_back(T&& value);
+
+    template <class... TArgs>
+    iterator emplace(const_iterator pos, TArgs&&... args);
+    template <class... TArgs>
+    reference emplace_back(TArgs&&... args);
+
+    void pop_back();
+
+    iterator erase(const_iterator pos);
+    iterator erase(const_iterator first, const_iterator last);
+
+    void clear();
+
+    void resize(size_type newSize);
+    void resize(size_type newSize, const T& value);
+
+    void reserve(size_type newCapacity);
+
+    void swap(TCompactVector& other);
+
+    void assign(size_type count, const T& value);
+    template <class TIterator>
+    void assign(TIterator first, TIterator last);
+    void assign(std::initializer_list<T> list);
+    template <size_t OtherN>
+    void assign(const TCompactVector<T, OtherN>& other);
+    template <size_t OtherN>
+    void assign(TCompactVector<T, OtherN>&& other);
+
+    TCompactVector& operator=(const TCompactVector& other);
+    template <size_t OtherN>
+    TCompactVector& operator=(const TCompactVector<T, OtherN>& other);
+    TCompactVector& operator=(TCompactVector&& other);
+    template <size_t OtherN>
+    TCompactVector& operator=(TCompactVector<T, OtherN>&& other);
+    TCompactVector& operator=(std::initializer_list<T> list);
+
+    iterator insert(const_iterator pos, const T& value);
+    iterator insert(const_iterator pos, T&& value);
+    iterator insert(const_iterator pos, size_type count, const T& value);
+    template <class TIterator>
+    iterator insert(const_iterator pos, TIterator first, TIterator last);
+    iterator insert(const_iterator pos, std::initializer_list<T> list);
+
+    void shrink_to_small();
+
+private:
+    template <class OtherT, size_t OtherN>
+    friend class TCompactVector;
+
+    using TOnHeapStorage = TCompactVectorOnHeapStorage<T>;
+
+    static constexpr size_t ByteSize =
+        (sizeof(T) * N + alignof(T) + sizeof(uintptr_t) - 1) &
+        ~(sizeof(uintptr_t) - 1);
+
+    struct TInlineMeta
+    {
+        char Padding[ByteSize - sizeof(uint8_t)];
+        //  > 0 indicates inline storage
+        // == 0 indicates on-heap storage
+        uint8_t SizePlusOne;
+    } alias_hack;
+
+    // TODO(aleexfi): Use [[no_unique_address]] when clang will support it on windows.
+    template <class = void>
+    struct TOnHeapMeta
+    {
+        char Padding[ByteSize - sizeof(uintptr_t)];
+        TOnHeapStorage* Storage;
+    } alias_hack;
+
+    template <class _>
+        requires (ByteSize == sizeof(uintptr_t))
+    struct TOnHeapMeta<_>
+    {
+        TOnHeapStorage* Storage;
+    } alias_hack;
+
+    static_assert(sizeof(TOnHeapMeta<>) == ByteSize);
+
+    union
+    {
+        T InlineElements_[N];
+        TInlineMeta InlineMeta_;
+        TOnHeapMeta<> OnHeapMeta_;
+    };
+
+    bool IsInline() const;
+    void SetSize(size_t newSize);
+    void EnsureOnHeapCapacity(size_t newCapacity, bool incremental);
+    template <class TPtr, class F>
+    reference PushBackImpl(TPtr valuePtr, F&& func);
+    template <class F>
+    void ResizeImpl(size_t newSize, F&& func);
+    template <class TPtr, class UninitializedF, class InitializedF>
+    iterator InsertOneImpl(const_iterator pos, TPtr valuePtr, UninitializedF&& uninitializedFunc, InitializedF&& initializedFunc);
+    template <class UninitializedF, class InitializedF>
+    iterator InsertManyImpl(const_iterator pos, size_t insertCount, UninitializedF&& uninitializedFunc, InitializedF&& initializedFunc);
+
+    static void Destroy(T* first, T* last);
+    template <class T1, class T2>
+    static void Copy(const T1* srcFirst, const T1* srcLast, T2* dst);
+    template <class T1, class T2>
+    static void UninitializedCopy(const T1* srcFirst, const T1* srcLast, T2* dst);
+    static void Move(T* srcFirst, T* srcLast, T* dst);
+    static void MoveBackward(T* srcFirst, T* srcLast, T* dst);
+    static void UninitializedMove(T* srcFirst, T* srcLast, T* dst);
+};
+
+////////////////////////////////////////////////////////////////////////////////
+
+template <class T, size_t LhsN, size_t RhsN>
+bool operator==(const TCompactVector<T, LhsN>& lhs, const TCompactVector<T, RhsN>& rhs);
+
+template <class T, size_t LhsN, size_t RhsN>
+bool operator!=(const TCompactVector<T, LhsN>& lhs, const TCompactVector<T, RhsN>& rhs);
+
+template <class T, size_t LhsN, size_t RhsN>
+bool operator<(const TCompactVector<T, LhsN>& lhs, const TCompactVector<T, RhsN>& rhs);
+
+////////////////////////////////////////////////////////////////////////////////
+
+} // namespace NYT
+
+#define COMPACT_VECTOR_INL_H_
+#include "compact_vector-inl.h"
+#undef COMPACT_VECTOR_INL_H_
diff --git a/library/cpp/yt/compact_containers/unittests/compact_flat_map_ut.cpp b/library/cpp/yt/compact_containers/unittests/compact_flat_map_ut.cpp
new file mode 100644
index 00000000000..9683d2a267f
--- /dev/null
+++ b/library/cpp/yt/compact_containers/unittests/compact_flat_map_ut.cpp
@@ -0,0 +1,285 @@
+#include <library/cpp/yt/compact_containers/compact_flat_map.h>
+
+#include <library/cpp/testing/gtest/gtest.h>
+
+#include <string>
+#include <vector>
+
+namespace NYT {
+namespace {
+
+////////////////////////////////////////////////////////////////////////////////
+
+using TMap = TCompactFlatMap<std::string, std::string, 2>;
+
+TMap CreateMap()
+{
+    std::vector<std::pair<std::string, std::string>> data = {{"I", "met"}, {"a", "traveller"}, {"from", "an"}, {"antique", "land"}};
+    return {data.begin(), data.end()};
+}
+
+TEST(TCompactFlatMapTest, DefaultEmpty)
+{
+    TMap m;
+    EXPECT_TRUE(m.empty());
+    EXPECT_EQ(m.begin(), m.end());
+}
+
+TEST(TCompactFlatMapTest, Reserve)
+{
+    // No real way to test reserve - just use it and wiggle about.
+    auto m1 = CreateMap();
+    TMap m2;
+    m2.reserve(m1.size());
+    m2.insert(m1.begin(), m1.end());
+    EXPECT_EQ(m1.size(), m2.size());
+}
+
+TEST(TCompactFlatMapTest, Size)
+{
+    auto m = CreateMap();
+
+    EXPECT_EQ(m.size(), 4u);
+    EXPECT_EQ(m.ssize(), 4);
+
+    m.insert({"Who", "said"});
+
+    EXPECT_EQ(m.size(), 5u);
+    EXPECT_EQ(m.ssize(), 5);
+
+    m.erase("antique");
+
+    EXPECT_EQ(m.size(), 4u);
+    EXPECT_EQ(m.ssize(), 4);
+}
+
+TEST(TCompactFlatMapTest, ClearAndEmpty)
+{
+    auto m = CreateMap();
+
+    EXPECT_FALSE(m.empty());
+    EXPECT_NE(m.begin(), m.end());
+
+    m.clear();
+
+    EXPECT_TRUE(m.empty());
+    EXPECT_EQ(m.begin(), m.end());
+
+    m.insert({"Who", "said"});
+
+    EXPECT_FALSE(m.empty());
+    EXPECT_NE(m.begin(), m.end());
+}
+
+TEST(TCompactFlatMapTest, FindMutable)
+{
+    auto m = CreateMap();
+    {
+        auto it = m.find("from");
+        EXPECT_NE(it, m.end());
+        EXPECT_EQ(it->second, "an");
+        it->second = "the";
+    }
+    {
+        auto it = m.find("from");
+        EXPECT_NE(it, m.end());
+        EXPECT_EQ(it->second, "the");
+    }
+    {
+        auto it = m.find("Who");
+        EXPECT_EQ(it, m.end());
+    }
+}
+
+TEST(TCompactFlatMapTest, FindConst)
+{
+    const auto& m = CreateMap();
+    {
+        auto it = m.find("from");
+        EXPECT_NE(it, m.end());
+        EXPECT_EQ(it->second, "an");
+    }
+    {
+        auto it = m.find("Who");
+        EXPECT_EQ(it, m.end());
+    }
+}
+
+TEST(TCompactFlatMapTest, Insert)
+{
+    auto m = CreateMap();
+
+    auto [it, inserted] = m.insert({"Who", "said"});
+    EXPECT_TRUE(inserted);
+    EXPECT_EQ(m.ssize(), 5);
+    EXPECT_NE(it, m.end());
+    EXPECT_EQ(it, m.find("Who"));
+    EXPECT_EQ(it->second, "said");
+
+    auto [it2, inserted2] = m.insert({"Who", "told"});
+    EXPECT_FALSE(inserted2);
+    EXPECT_EQ(m.ssize(), 5);
+    EXPECT_EQ(it2, it);
+    EXPECT_EQ(it->second, "said");
+
+    std::vector<std::pair<std::string, std::string>> data = {{"Two", "vast"}, {"and", "trunkless"}, {"legs", "of"}, {"stone", "Stand"}, {"in", "the"}, {"desert", "..."}};
+    m.insert(data.begin(), data.end());
+    EXPECT_EQ(m.ssize(), 11);
+    EXPECT_NE(m.find("and"), m.end());
+    EXPECT_EQ(m.find("and")->second, "trunkless");
+}
+
+TEST(TCompactFlatMapTest, Emplace)
+{
+    auto m = CreateMap();
+
+    auto [it, inserted] = m.emplace("Far", "place");
+    EXPECT_TRUE(inserted);
+    EXPECT_EQ(m.ssize(), 5);
+    EXPECT_NE(it, m.end());
+    EXPECT_EQ(it, m.find("Far"));
+    EXPECT_EQ(it->second, "place");
+
+    auto [it2, inserted2] = m.emplace("Far", "behind");
+    EXPECT_FALSE(inserted2);
+    EXPECT_EQ(m.ssize(), 5);
+    EXPECT_EQ(it2, it);
+    EXPECT_EQ(it->second, "place");
+}
+
+TEST(TCompactFlatMapTest, Subscript)
+{
+    auto m = CreateMap();
+
+    EXPECT_EQ(m["antique"], "land");
+    EXPECT_EQ(m.ssize(), 4);
+
+    EXPECT_EQ(m["Who"], "");
+    EXPECT_EQ(m.ssize(), 5);
+}
+
+TEST(TCompactFlatMapTest, Erase)
+{
+    auto m = CreateMap();
+
+    m.erase("antique");
+    EXPECT_EQ(m.ssize(), 3);
+
+    m.erase("Who");
+    EXPECT_EQ(m.ssize(), 3);
+
+    m.erase(m.begin(), m.end());
+    EXPECT_TRUE(m.empty());
+}
+
+TEST(TCompactFlatMapTest, GrowShrink)
+{
+    TMap m;
+    m.insert({"Two", "vast"});
+    m.insert({"and", "trunkless"});
+    m.insert({"legs", "of"});
+    m.insert({"stone", "Stand"});
+    m.insert({"in", "the"});
+    m.insert({"desert", "..."});
+
+    m.erase("legs");
+    m.erase("stone");
+    m.erase("in");
+    m.erase("desert");
+
+    EXPECT_EQ(m.ssize(), 2);
+
+    // Must not crash or trigger asan.
+}
+
+TEST(TCompactFlatMapTest, GrowShrinkGrow)
+{
+    TMap m;
+    m.insert({"Two", "vast"});
+    m.insert({"and", "trunkless"});
+    m.insert({"legs", "of"});
+    m.insert({"stone", "Stand"});
+    m.insert({"in", "the"});
+    m.insert({"desert", "..."});
+
+    m.erase("legs");
+    m.erase("stone");
+    m.erase("in");
+    m.erase("desert");
+
+    EXPECT_EQ(m.ssize(), 2);
+
+    m.insert({"I", "met"});
+    m.insert({"a", "traveller"});
+    m.insert({"from", "an"});
+    m.insert({"antique", "land"});
+
+    EXPECT_EQ(m.ssize(), 6);
+
+    // Must not crash or trigger asan.
+}
+
+TEST(TCompactFlatMapTest, LowerBound)
+{
+    TMap m;
+    EXPECT_EQ(m.lower_bound("a"), m.end());
+
+    m.emplace("b", "value");
+    EXPECT_EQ(m.lower_bound("a")->second, "value");
+    EXPECT_EQ(m.lower_bound("b")->second, "value");
+
+    m.emplace("c", "value2");
+
+    // Grows here.
+    m.emplace("d", "value3");
+    EXPECT_EQ(m.lower_bound("a")->second, "value");
+    EXPECT_EQ(m.lower_bound("e"), m.end());
+}
+
+TEST(TCompactFlatMapTest, UpperBound)
+{
+    using TKeyValue = std::pair<std::string, std::string>;
+    TMap m;
+    EXPECT_EQ(m.upper_bound("a"), m.end());
+
+    m.emplace("b", "value");
+    EXPECT_EQ(m.upper_bound("a")->second, "value");
+    EXPECT_EQ(m.upper_bound("b"), m.end());
+
+    m.emplace("c", "value2");
+
+    // Grows here.
+    m.emplace("d", "value3");
+
+    EXPECT_EQ(*m.upper_bound("a"), TKeyValue("b", "value"));
+    EXPECT_EQ(*m.upper_bound("b"), TKeyValue("c", "value2"));
+    EXPECT_EQ(m.upper_bound("d"), m.end());
+}
+
+TEST(TCompactFlatMapTest, EqualRange)
+{
+    TMap m;
+    EXPECT_EQ(m.equal_range("a"), std::pair(m.end(), m.end()));
+
+    m.emplace("b", "value-b");
+    EXPECT_EQ(m.equal_range("a"), std::pair(m.begin(), m.begin()));
+    EXPECT_EQ(m.equal_range("b"), std::pair(m.begin(), m.end()));
+    EXPECT_EQ(m.equal_range("c"), std::pair(m.end(), m.end()));
+
+    m.emplace("c", "value-c");
+    m.emplace("d", "value-d");
+
+    auto it = m.begin();
+    EXPECT_EQ(m.equal_range("a"), std::pair(it, it));
+    EXPECT_EQ(m.equal_range("b"), std::pair(it, std::next(it)));
+    ++it;
+    EXPECT_EQ(m.equal_range("c"), std::pair(it, std::next(it)));
+    ++it;
+    EXPECT_EQ(m.equal_range("d"), std::pair(it, std::next(it)));
+    EXPECT_EQ(m.equal_range("e"), std::pair(m.end(), m.end()));
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+} // namespace
+} // namespace NYT
diff --git a/library/cpp/yt/compact_containers/unittests/compact_heap_ut.cpp b/library/cpp/yt/compact_containers/unittests/compact_heap_ut.cpp
new file mode 100644
index 00000000000..4cd66443563
--- /dev/null
+++ b/library/cpp/yt/compact_containers/unittests/compact_heap_ut.cpp
@@ -0,0 +1,108 @@
+#include <library/cpp/yt/compact_containers/compact_heap.h>
+
+#include <library/cpp/testing/gtest/gtest.h>
+
+#include <random>
+
+namespace NYT {
+namespace {
+
+////////////////////////////////////////////////////////////////////////////////
+
+TEST(CompactHeapTest, Simple)
+{
+    TCompactHeap<int, 2> heap;
+    heap.push(3);
+    heap.push(1);
+    heap.push(2);
+
+    EXPECT_EQ(3u, heap.size());
+    EXPECT_EQ(1, heap.extract_min());
+
+    EXPECT_EQ(2, heap.get_min());
+    EXPECT_EQ(2, heap.extract_min());
+
+    EXPECT_EQ(3, heap.extract_min());
+
+    EXPECT_TRUE(heap.empty());
+}
+
+TEST(CompactHeapTest, SimpleComparator)
+{
+    TCompactHeap<int, 2, std::greater<int>> heap;
+    heap.push(3);
+    heap.push(1);
+    heap.push(2);
+
+    EXPECT_EQ(3u, heap.size());
+    EXPECT_EQ(3, heap.extract_min());
+    EXPECT_EQ(2, heap.get_min());
+    EXPECT_EQ(2, heap.extract_min());
+    EXPECT_EQ(1, heap.extract_min());
+    EXPECT_TRUE(heap.empty());
+}
+
+TEST(CompactHeapTest, Capacity)
+{
+    TCompactHeap<int, 2> heap;
+    EXPECT_EQ(2u, heap.capacity());
+    EXPECT_EQ(0u, heap.size());
+
+    for (int i = 0; i < 100; ++i) {
+        heap.push(i);
+    }
+    EXPECT_LE(100u, heap.capacity());
+    EXPECT_EQ(100u, heap.size());
+
+    for (int i = 0; i < 99; ++i) {
+        heap.pop();
+    }
+    EXPECT_LE(100u, heap.capacity());
+    EXPECT_EQ(1u, heap.size());
+
+    heap.shrink_to_small();
+
+    EXPECT_EQ(2u, heap.capacity());
+    EXPECT_EQ(1u, heap.size());
+}
+
+TEST(CompactHeapTest, Stress)
+{
+    TCompactHeap<int, 3, std::greater<int>> heap;
+    std::vector<int> values;
+
+    std::mt19937 rng(42);
+    for (int iteration = 0; iteration < 1000; ++iteration) {
+        EXPECT_EQ(values.size(), heap.size());
+        EXPECT_EQ(values.empty(), heap.empty());
+
+        {
+            std::vector<int> content(heap.begin(), heap.end());
+            std::sort(content.rbegin(), content.rend());
+            EXPECT_EQ(values, content);
+        }
+
+        if (!values.empty()) {
+            EXPECT_EQ(values[0], heap.get_min());
+        }
+
+        if (values.empty() || rng() % 2 == 0) {
+            int x = rng() % 100;
+            heap.push(x);
+            values.push_back(x);
+            std::sort(values.rbegin(), values.rend());
+        } else {
+            if (rng() % 2 == 0) {
+                EXPECT_EQ(values[0], heap.extract_min());
+            } else {
+                heap.pop();
+            }
+            values.erase(values.begin());
+        }
+    }
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+} // namespace
+} // namespace NYT
diff --git a/library/cpp/yt/compact_containers/unittests/compact_queue_ut.cpp b/library/cpp/yt/compact_containers/unittests/compact_queue_ut.cpp
new file mode 100644
index 00000000000..463d4ec4970
--- /dev/null
+++ b/library/cpp/yt/compact_containers/unittests/compact_queue_ut.cpp
@@ -0,0 +1,114 @@
+#include <library/cpp/yt/compact_containers/compact_queue.h>
+
+#include <library/cpp/testing/gtest/gtest.h>
+
+#include <queue>
+#include <random>
+
+namespace NYT {
+namespace {
+
+////////////////////////////////////////////////////////////////////////////////
+
+TEST(TCompactQueueTest, Simple)
+{
+    TCompactQueue<int, 4> queue;
+    queue.Push(1);
+    queue.Push(2);
+    queue.Push(3);
+
+    for (int i = 1; i <= 10; i++) {
+        EXPECT_EQ(queue.Size(), 3u);
+        EXPECT_EQ(queue.Front(), i);
+        EXPECT_EQ(queue.Pop(), i);
+        queue.Push(i + 3);
+    }
+
+    for (int i = 11; i <= 13; i++) {
+        EXPECT_EQ(queue.Front(), i);
+        queue.Pop();
+    }
+
+    EXPECT_TRUE(queue.Empty());
+}
+
+TEST(TCompactQueueTest, Reallocation1)
+{
+    TCompactQueue<int, 2> queue;
+    queue.Push(1);
+    queue.Push(2);
+    queue.Push(3);
+
+    for (int i = 1; i <= 10; i++) {
+        EXPECT_EQ(queue.Size(), 3u);
+        EXPECT_EQ(queue.Front(), i);
+        EXPECT_EQ(queue.Pop(), i);
+        queue.Push(i + 3);
+    }
+
+    for (int i = 11; i <= 13; i++) {
+        EXPECT_EQ(queue.Front(), i);
+        queue.Pop();
+    }
+
+    EXPECT_TRUE(queue.Empty());
+}
+
+TEST(TCompactQueueTest, Reallocation2)
+{
+    TCompactQueue<int, 3> queue;
+    queue.Push(1);
+    queue.Push(2);
+    queue.Push(3);
+    EXPECT_EQ(queue.Pop(), 1);
+    queue.Push(4);
+    queue.Push(5);
+
+    EXPECT_EQ(queue.Size(), 4u);
+
+    for (int i = 2; i <= 10; i++) {
+        EXPECT_EQ(queue.Size(), 4u);
+        EXPECT_EQ(queue.Front(), i);
+        EXPECT_EQ(queue.Pop(), i);
+        queue.Push(i + 4);
+    }
+
+    for (int i = 11; i <= 14; i++) {
+        EXPECT_EQ(queue.Front(), i);
+        queue.Pop();
+    }
+
+    EXPECT_TRUE(queue.Empty());
+}
+
+TEST(TCompactQueueTest, Stress)
+{
+    std::mt19937_64 rng(42);
+
+    for (int iteration = 0; iteration < 1000; ++iteration) {
+        TCompactQueue<int, 4> queue1;
+        std::queue<int> queue2;
+
+        for (int step = 0; step < 10'000; ++step) {
+            EXPECT_EQ(queue1.Size(), queue2.size());
+            EXPECT_EQ(queue1.Empty(), queue2.empty());
+            if (!queue1.Empty()) {
+                EXPECT_EQ(queue1.Front(), queue2.front());
+            }
+
+            if (queue2.empty() || rng() % 2 == 0) {
+                int value = rng() % 1'000'000;
+                queue1.Push(value);
+                queue2.push(value);
+            } else {
+                queue1.Pop();
+                queue2.pop();
+            }
+        }
+    }
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+} // namespace
+} // namespace NYT
diff --git a/library/cpp/yt/compact_containers/unittests/compact_set_ut.cpp b/library/cpp/yt/compact_containers/unittests/compact_set_ut.cpp
new file mode 100644
index 00000000000..203a6f75f58
--- /dev/null
+++ b/library/cpp/yt/compact_containers/unittests/compact_set_ut.cpp
@@ -0,0 +1,211 @@
+//===- llvm/unittest/ADT/SmallSetTest.cpp ---------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// CompactSet unit tests.
+//
+//===----------------------------------------------------------------------===//
+
+#include <library/cpp/yt/compact_containers/compact_set.h>
+
+#include <library/cpp/testing/gtest/gtest.h>
+
+#include <string>
+
+namespace NYT {
+namespace {
+
+////////////////////////////////////////////////////////////////////////////////
+
+TEST(TCompactSetTest, Insert)
+{
+    TCompactSet<int, 4> s1;
+
+    for (int i = 0; i < 4; i++)
+        s1.insert(i);
+
+    for (int i = 0; i < 4; i++)
+        s1.insert(i);
+
+    EXPECT_EQ(4u, s1.size());
+
+    for (int i = 0; i < 4; i++)
+        EXPECT_EQ(1u, s1.count(i));
+
+    EXPECT_EQ(0u, s1.count(4));
+}
+
+TEST(TCompactSetTest, Grow)
+{
+    TCompactSet<int, 4> s1;
+
+    for (int i = 0; i < 8; i++)
+        s1.insert(i);
+
+    EXPECT_EQ(8u, s1.size());
+
+    for (int i = 0; i < 8; i++)
+        EXPECT_EQ(1u, s1.count(i));
+
+    EXPECT_EQ(0u, s1.count(8));
+}
+
+TEST(TCompactSetTest, Erase)
+{
+    TCompactSet<int, 4> s1;
+
+    for (int i = 0; i < 8; i++)
+        s1.insert(i);
+
+    EXPECT_EQ(8u, s1.size());
+
+    // Remove elements one by one and check if all other elements are still there.
+    for (int i = 0; i < 8; i++) {
+        EXPECT_EQ(1u, s1.count(i));
+        EXPECT_TRUE(s1.erase(i));
+        EXPECT_EQ(0u, s1.count(i));
+        EXPECT_EQ(8u - i - 1, s1.size());
+        for (int j = i + 1; j < 8; j++)
+            EXPECT_EQ(1u, s1.count(j));
+    }
+
+    EXPECT_EQ(0u, s1.count(8));
+}
+
+TEST(TCompactSetTest, IteratorInt)
+{
+    TCompactSet<int, 4> s1;
+
+    // Test the 'small' case.
+    for (int i = 0; i < 3; i++)
+        s1.insert(i);
+
+    std::vector<int> V(s1.begin(), s1.end());
+    // Make sure the elements are in the expected order.
+    std::sort(V.begin(), V.end());
+    for (int i = 0; i < 3; i++)
+        EXPECT_EQ(i, V[i]);
+
+    // Test the 'big' case by adding a few more elements to switch to std::set
+    // internally.
+    for (int i = 3; i < 6; i++)
+        s1.insert(i);
+
+    V.assign(s1.begin(), s1.end());
+    // Make sure the elements are in the expected order.
+    std::sort(V.begin(), V.end());
+    for (int i = 0; i < 6; i++)
+        EXPECT_EQ(i, V[i]);
+}
+
+TEST(TCompactSetTest, IteratorString)
+{
+    // Test CompactSetIterator for TCompactSet with a type with non-trivial
+    // ctors/dtors.
+    TCompactSet<std::string, 2> s1;
+
+    s1.insert("str 1");
+    s1.insert("str 2");
+    s1.insert("str 1");
+
+    std::vector<std::string> V(s1.begin(), s1.end());
+    std::sort(V.begin(), V.end());
+    EXPECT_EQ(2u, s1.size());
+    EXPECT_EQ("str 1", V[0]);
+    EXPECT_EQ("str 2", V[1]);
+
+    s1.insert("str 4");
+    s1.insert("str 0");
+    s1.insert("str 4");
+
+    V.assign(s1.begin(), s1.end());
+    // Make sure the elements are in the expected order.
+    std::sort(V.begin(), V.end());
+    EXPECT_EQ(4u, s1.size());
+    EXPECT_EQ("str 0", V[0]);
+    EXPECT_EQ("str 1", V[1]);
+    EXPECT_EQ("str 2", V[2]);
+    EXPECT_EQ("str 4", V[3]);
+}
+
+TEST(TCompactSetTest, IteratorIncMoveCopy)
+{
+    // Test CompactSetIterator for TCompactSet with a type with non-trivial
+    // ctors/dtors.
+    TCompactSet<std::string, 2> s1;
+
+    s1.insert("str 1");
+    s1.insert("str 2");
+
+    auto Iter = s1.begin();
+    EXPECT_EQ("str 1", *Iter);
+    ++Iter;
+    EXPECT_EQ("str 2", *Iter);
+
+    s1.insert("str 4");
+    s1.insert("str 0");
+    auto Iter2 = s1.begin();
+    Iter = std::move(Iter2);
+    EXPECT_EQ("str 0", *Iter);
+}
+
+// These test weren't taken from llvm.
+
+TEST(TCompactSetTest, Empty)
+{
+    TCompactSet<int, 10> v;
+    EXPECT_TRUE(v.empty());
+
+    auto data = {1, 2, 3, 4, 5};
+
+    v.insert(data.begin(), data.end()); // not crossing size threshold
+    v.erase(4);
+    v.erase(2);
+    v.erase(3);
+    v.erase(5);
+    v.erase(1);
+    EXPECT_TRUE(v.empty());
+
+    auto data2 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
+    v.insert(data2.begin(), data2.end()); // crossing size threshold
+    v.erase(7);
+    v.erase(3);
+    v.erase(1);
+    v.erase(10);
+    v.erase(9);
+    v.erase(0);
+    v.erase(2);
+    v.erase(6);
+    v.erase(4);
+    v.erase(5);
+    v.erase(8);
+    EXPECT_TRUE(v.empty());
+}
+
+TEST(TCompactSetTest, ForEach)
+{
+    TCompactSet<int, 10> v;
+
+    auto data = {10, 9, 3, 4, 1, 5, 6, 8};
+
+    v.insert(data.begin(), data.end());
+
+    std::vector<int> buf(v.begin(), v.end());
+    std::vector<int> expected{1, 3, 4, 5, 6, 8, 9, 10};
+    EXPECT_EQ(expected, buf);
+
+    auto data2 = {7, 1, 2, 0};
+    v.insert(data2.begin(), data2.end());
+    buf.assign(v.begin(), v.end());
+    expected = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
+    EXPECT_EQ(expected, buf);
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+} // namespace
+} // namespace NYT
diff --git a/library/cpp/yt/compact_containers/unittests/compact_vector_ut.cpp b/library/cpp/yt/compact_containers/unittests/compact_vector_ut.cpp
new file mode 100644
index 00000000000..5ffc04efdc4
--- /dev/null
+++ b/library/cpp/yt/compact_containers/unittests/compact_vector_ut.cpp
@@ -0,0 +1,1097 @@
+// Adapted from the following:
+//===- llvm/unittest/ADT/CompactVectorTest.cpp ------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// TCompactVector unit tests.
+//
+//===----------------------------------------------------------------------===//
+
+#include <library/cpp/yt/compact_containers/compact_vector.h>
+
+#include <library/cpp/testing/gtest/gtest.h>
+
+#include <util/string/cast.h>
+
+#include <algorithm>
+#include <list>
+
+#include <stdarg.h>
+
+namespace NYT {
+namespace {
+
+////////////////////////////////////////////////////////////////////////////////
+
+/// A helper class that counts the total number of constructor and
+/// destructor calls.
+class Constructable {
+private:
+  static int numConstructorCalls;
+  static int numMoveConstructorCalls;
+  static int numCopyConstructorCalls;
+  static int numDestructorCalls;
+  static int numAssignmentCalls;
+  static int numMoveAssignmentCalls;
+  static int numCopyAssignmentCalls;
+
+  bool constructed;
+  int value;
+
+public:
+  Constructable() : constructed(true), value(0) {
+    ++numConstructorCalls;
+  }
+
+  Constructable(int val) : constructed(true), value(val) {
+    ++numConstructorCalls;
+  }
+
+  Constructable(const Constructable & src) : constructed(true) {
+    value = src.value;
+    ++numConstructorCalls;
+    ++numCopyConstructorCalls;
+  }
+
+  Constructable(Constructable && src) : constructed(true) {
+    value = src.value;
+    ++numConstructorCalls;
+    ++numMoveConstructorCalls;
+  }
+
+  ~Constructable() {
+    EXPECT_TRUE(constructed);
+    ++numDestructorCalls;
+    constructed = false;
+  }
+
+  Constructable & operator=(const Constructable & src) {
+    EXPECT_TRUE(constructed);
+    value = src.value;
+    ++numAssignmentCalls;
+    ++numCopyAssignmentCalls;
+    return *this;
+  }
+
+  Constructable & operator=(Constructable && src) {
+    EXPECT_TRUE(constructed);
+    value = src.value;
+    ++numAssignmentCalls;
+    ++numMoveAssignmentCalls;
+    return *this;
+  }
+
+  int getValue() const {
+    return abs(value);
+  }
+
+  static void reset() {
+    numConstructorCalls = 0;
+    numMoveConstructorCalls = 0;
+    numCopyConstructorCalls = 0;
+    numDestructorCalls = 0;
+    numAssignmentCalls = 0;
+    numMoveAssignmentCalls = 0;
+    numCopyAssignmentCalls = 0;
+  }
+
+  static int getNumConstructorCalls() {
+    return numConstructorCalls;
+  }
+
+  static int getNumMoveConstructorCalls() {
+    return numMoveConstructorCalls;
+  }
+
+  static int getNumCopyConstructorCalls() {
+    return numCopyConstructorCalls;
+  }
+
+  static int getNumDestructorCalls() {
+    return numDestructorCalls;
+  }
+
+  static int getNumAssignmentCalls() {
+    return numAssignmentCalls;
+  }
+
+  static int getNumMoveAssignmentCalls() {
+    return numMoveAssignmentCalls;
+  }
+
+  static int getNumCopyAssignmentCalls() {
+    return numCopyAssignmentCalls;
+  }
+
+  friend bool operator==(const Constructable & c0, const Constructable & c1) {
+    return c0.getValue() == c1.getValue();
+  }
+};
+
+int Constructable::numConstructorCalls;
+int Constructable::numCopyConstructorCalls;
+int Constructable::numMoveConstructorCalls;
+int Constructable::numDestructorCalls;
+int Constructable::numAssignmentCalls;
+int Constructable::numCopyAssignmentCalls;
+int Constructable::numMoveAssignmentCalls;
+
+struct NonCopyable {
+  NonCopyable() {}
+  NonCopyable(NonCopyable &&) {}
+  NonCopyable &operator=(NonCopyable &&) { return *this; }
+private:
+  NonCopyable(const NonCopyable &) = delete;
+  NonCopyable &operator=(const NonCopyable &) = delete;
+};
+
+[[maybe_unused]] void CompileTest() {
+  TCompactVector<NonCopyable, 0> V;
+  V.resize(42);
+}
+
+class CompactVectorTestBase : public testing::Test {
+protected:
+
+  void SetUp() override {
+    Constructable::reset();
+  }
+
+  template <typename VectorT>
+  void assertEmpty(VectorT & v) {
+    // Size tests
+    EXPECT_EQ(0u, v.size());
+    EXPECT_TRUE(v.empty());
+
+    // Iterator tests
+    EXPECT_TRUE(v.begin() == v.end());
+  }
+
+  // Assert that v contains the specified values, in order.
+  template <typename VectorT>
+  void assertValuesInOrder(VectorT & v, size_t size, ...) {
+    EXPECT_EQ(size, v.size());
+
+    va_list ap;
+    va_start(ap, size);
+    for (size_t i = 0; i < size; ++i) {
+      int value = va_arg(ap, int);
+      EXPECT_EQ(value, v[i].getValue());
+    }
+
+    va_end(ap);
+  }
+
+  // Generate a sequence of values to initialize the vector.
+  template <typename VectorT>
+  void makeSequence(VectorT & v, int start, int end) {
+    for (int i = start; i <= end; ++i) {
+      v.push_back(Constructable(i));
+    }
+  }
+};
+
+// Test fixture class
+template <typename VectorT>
+class CompactVectorTest : public CompactVectorTestBase {
+protected:
+  VectorT theVector;
+  VectorT otherVector;
+};
+
+
+using CompactVectorTestTypes = ::testing::Types<TCompactVector<Constructable, 0>,
+                         TCompactVector<Constructable, 1>,
+                         TCompactVector<Constructable, 2>,
+                         TCompactVector<Constructable, 4>,
+                         TCompactVector<Constructable, 5>
+                         >;
+TYPED_TEST_SUITE(CompactVectorTest, CompactVectorTestTypes);
+
+// New vector test.
+TYPED_TEST(CompactVectorTest, EmptyVectorTest) {
+  SCOPED_TRACE("EmptyVectorTest");
+  this->assertEmpty(this->theVector);
+  EXPECT_TRUE(this->theVector.rbegin() == this->theVector.rend());
+  EXPECT_EQ(0, Constructable::getNumConstructorCalls());
+  EXPECT_EQ(0, Constructable::getNumDestructorCalls());
+}
+
+// Simple insertions and deletions.
+TYPED_TEST(CompactVectorTest, PushPopTest) {
+  SCOPED_TRACE("PushPopTest");
+
+  // Track whether the vector will potentially have to grow.
+  bool RequiresGrowth = this->theVector.capacity() < 3;
+
+  // Push an element
+  this->theVector.push_back(Constructable(1));
+
+  // Size tests
+  this->assertValuesInOrder(this->theVector, 1u, 1);
+  EXPECT_FALSE(this->theVector.begin() == this->theVector.end());
+  EXPECT_FALSE(this->theVector.empty());
+
+  // Push another element
+  this->theVector.push_back(Constructable(2));
+  this->assertValuesInOrder(this->theVector, 2u, 1, 2);
+
+  // Insert at beginning
+  this->theVector.insert(this->theVector.begin(), this->theVector[1]);
+  this->assertValuesInOrder(this->theVector, 3u, 2, 1, 2);
+
+  // Pop one element
+  this->theVector.pop_back();
+  this->assertValuesInOrder(this->theVector, 2u, 2, 1);
+
+  // Pop remaining elements
+  this->theVector.pop_back();
+  this->theVector.pop_back();
+  this->assertEmpty(this->theVector);
+
+  // Check number of constructor calls. Should be 2 for each list element,
+  // one for the argument to push_back, one for the argument to insert,
+  // and one for the list element itself.
+  if (!RequiresGrowth) {
+    EXPECT_EQ(5, Constructable::getNumConstructorCalls());
+    EXPECT_EQ(5, Constructable::getNumDestructorCalls());
+  } else {
+    // If we had to grow the vector, these only have a lower bound, but should
+    // always be equal.
+    EXPECT_LE(5, Constructable::getNumConstructorCalls());
+    EXPECT_EQ(Constructable::getNumConstructorCalls(),
+              Constructable::getNumDestructorCalls());
+  }
+}
+
+TYPED_TEST(CompactVectorTest, InsertEnd)
+{
+    SCOPED_TRACE("InsertEnd");
+
+    TCompactVector<TString, 5> vector;
+    for (int index = 0; index < 10; ++index) {
+        vector.insert(vector.end(), ToString(index));
+    }
+    for (int index = 0; index < 10; ++index) {
+        EXPECT_EQ(vector[index], ToString(index));
+    }
+}
+
+TYPED_TEST(CompactVectorTest, ShrinkToSmall)
+{
+    SCOPED_TRACE("ShrinkToSmall");
+
+    TCompactVector<TString, 5> vector;
+    for (int index = 0; index < 10; ++index) {
+        vector.shrink_to_small();
+        vector.push_back(ToString(index));
+    }
+
+    for (int index = 0; index < 6; ++index) {
+        vector.pop_back();
+    }
+
+    EXPECT_EQ(std::ssize(vector), 4);
+    EXPECT_GE(static_cast<int>(vector.capacity()), 10);
+    vector.shrink_to_small();
+    EXPECT_EQ(std::ssize(vector), 4);
+    EXPECT_EQ(static_cast<int>(vector.capacity()), 5);
+    for (int index = 0; index < 4; ++index) {
+        EXPECT_EQ(vector[index], ToString(index));
+    }
+}
+
+// Clear test.
+TYPED_TEST(CompactVectorTest, ClearTest) {
+  SCOPED_TRACE("ClearTest");
+
+  this->theVector.reserve(2);
+  this->makeSequence(this->theVector, 1, 2);
+  this->theVector.clear();
+
+  this->assertEmpty(this->theVector);
+  EXPECT_EQ(4, Constructable::getNumConstructorCalls());
+  EXPECT_EQ(4, Constructable::getNumDestructorCalls());
+}
+
+// Resize smaller test.
+TYPED_TEST(CompactVectorTest, ResizeShrinkTest) {
+  SCOPED_TRACE("ResizeShrinkTest");
+
+  this->theVector.reserve(3);
+  this->makeSequence(this->theVector, 1, 3);
+  this->theVector.resize(1);
+
+  this->assertValuesInOrder(this->theVector, 1u, 1);
+  EXPECT_EQ(6, Constructable::getNumConstructorCalls());
+  EXPECT_EQ(5, Constructable::getNumDestructorCalls());
+}
+
+// Resize bigger test.
+TYPED_TEST(CompactVectorTest, ResizeGrowTest) {
+  SCOPED_TRACE("ResizeGrowTest");
+
+  this->theVector.resize(2);
+
+  EXPECT_EQ(2, Constructable::getNumConstructorCalls());
+  EXPECT_EQ(0, Constructable::getNumDestructorCalls());
+  EXPECT_EQ(2u, this->theVector.size());
+}
+
+TYPED_TEST(CompactVectorTest, ResizeWithElementsTest) {
+  this->theVector.resize(2);
+
+  Constructable::reset();
+
+  this->theVector.resize(4);
+
+  size_t Ctors = Constructable::getNumConstructorCalls();
+  EXPECT_TRUE(Ctors == 2 || Ctors == 4);
+  size_t MoveCtors = Constructable::getNumMoveConstructorCalls();
+  EXPECT_TRUE(MoveCtors == 0 || MoveCtors == 2);
+  size_t Dtors = Constructable::getNumDestructorCalls();
+  EXPECT_TRUE(Dtors == 0 || Dtors == 2);
+}
+
+// Resize with fill value.
+TYPED_TEST(CompactVectorTest, ResizeFillTest) {
+  SCOPED_TRACE("ResizeFillTest");
+
+  this->theVector.resize(3, Constructable(77));
+  this->assertValuesInOrder(this->theVector, 3u, 77, 77, 77);
+}
+
+// Overflow past fixed size.
+TYPED_TEST(CompactVectorTest, OverflowTest) {
+  SCOPED_TRACE("OverflowTest");
+
+  // Push more elements than the fixed size.
+  this->makeSequence(this->theVector, 1, 10);
+
+  // Test size and values.
+  EXPECT_EQ(10u, this->theVector.size());
+  for (int i = 0; i < 10; ++i) {
+    EXPECT_EQ(i+1, this->theVector[i].getValue());
+  }
+
+  // Now resize back to fixed size.
+  this->theVector.resize(1);
+
+  this->assertValuesInOrder(this->theVector, 1u, 1);
+}
+
+// Iteration tests.
+TYPED_TEST(CompactVectorTest, IterationTest) {
+  this->makeSequence(this->theVector, 1, 2);
+
+  // Forward Iteration
+  typename TypeParam::iterator it = this->theVector.begin();
+  EXPECT_TRUE(*it == this->theVector.front());
+  EXPECT_TRUE(*it == this->theVector[0]);
+  EXPECT_EQ(1, it->getValue());
+  ++it;
+  EXPECT_TRUE(*it == this->theVector[1]);
+  EXPECT_TRUE(*it == this->theVector.back());
+  EXPECT_EQ(2, it->getValue());
+  ++it;
+  EXPECT_TRUE(it == this->theVector.end());
+  --it;
+  EXPECT_TRUE(*it == this->theVector[1]);
+  EXPECT_EQ(2, it->getValue());
+  --it;
+  EXPECT_TRUE(*it == this->theVector[0]);
+  EXPECT_EQ(1, it->getValue());
+
+  // Reverse Iteration
+  typename TypeParam::reverse_iterator rit = this->theVector.rbegin();
+  EXPECT_TRUE(*rit == this->theVector[1]);
+  EXPECT_EQ(2, rit->getValue());
+  ++rit;
+  EXPECT_TRUE(*rit == this->theVector[0]);
+  EXPECT_EQ(1, rit->getValue());
+  ++rit;
+  EXPECT_TRUE(rit == this->theVector.rend());
+  --rit;
+  EXPECT_TRUE(*rit == this->theVector[0]);
+  EXPECT_EQ(1, rit->getValue());
+  --rit;
+  EXPECT_TRUE(*rit == this->theVector[1]);
+  EXPECT_EQ(2, rit->getValue());
+}
+
+// Swap test.
+TYPED_TEST(CompactVectorTest, SwapTest) {
+  SCOPED_TRACE("SwapTest");
+
+  this->makeSequence(this->theVector, 1, 2);
+  std::swap(this->theVector, this->otherVector);
+
+  this->assertEmpty(this->theVector);
+  this->assertValuesInOrder(this->otherVector, 2u, 1, 2);
+}
+
+// Append test
+TYPED_TEST(CompactVectorTest, AppendTest) {
+  SCOPED_TRACE("AppendTest");
+
+  this->makeSequence(this->otherVector, 2, 3);
+
+  this->theVector.push_back(Constructable(1));
+  this->theVector.insert(this->theVector.end(), this->otherVector.begin(), this->otherVector.end());
+
+  this->assertValuesInOrder(this->theVector, 3u, 1, 2, 3);
+}
+
+// Append repeated test
+TYPED_TEST(CompactVectorTest, AppendRepeatedTest) {
+  SCOPED_TRACE("AppendRepeatedTest");
+
+  this->theVector.push_back(Constructable(1));
+  this->theVector.insert(this->theVector.end(), 2, Constructable(77));
+  this->assertValuesInOrder(this->theVector, 3u, 1, 77, 77);
+}
+
+// Assign test
+TYPED_TEST(CompactVectorTest, AssignTest) {
+  SCOPED_TRACE("AssignTest");
+
+  this->theVector.push_back(Constructable(1));
+  this->theVector.assign(2, Constructable(77));
+  this->assertValuesInOrder(this->theVector, 2u, 77, 77);
+}
+
+// Move-assign test
+TYPED_TEST(CompactVectorTest, MoveAssignTest) {
+  SCOPED_TRACE("MoveAssignTest");
+
+  // Set up our vector with a single element, but enough capacity for 4.
+  this->theVector.reserve(4);
+  this->theVector.push_back(Constructable(1));
+
+  // Set up the other vector with 2 elements.
+  this->otherVector.push_back(Constructable(2));
+  this->otherVector.push_back(Constructable(3));
+
+  // Move-assign from the other vector.
+  this->theVector = std::move(this->otherVector);
+
+  // Make sure we have the right result.
+  this->assertValuesInOrder(this->theVector, 2u, 2, 3);
+
+  // Make sure the # of constructor/destructor calls line up. There
+  // are two live objects after clearing the other vector.
+  this->otherVector.clear();
+  EXPECT_EQ(Constructable::getNumConstructorCalls()-2,
+            Constructable::getNumDestructorCalls());
+
+  // There shouldn't be any live objects any more.
+  this->theVector.clear();
+  EXPECT_EQ(Constructable::getNumConstructorCalls(),
+            Constructable::getNumDestructorCalls());
+}
+
+// Erase a single element
+TYPED_TEST(CompactVectorTest, EraseTest) {
+  SCOPED_TRACE("EraseTest");
+
+  this->makeSequence(this->theVector, 1, 3);
+  this->theVector.erase(this->theVector.begin());
+  this->assertValuesInOrder(this->theVector, 2u, 2, 3);
+}
+
+// Erase a range of elements
+TYPED_TEST(CompactVectorTest, EraseRangeTest) {
+  SCOPED_TRACE("EraseRangeTest");
+
+  this->makeSequence(this->theVector, 1, 3);
+  this->theVector.erase(this->theVector.begin(), this->theVector.begin() + 2);
+  this->assertValuesInOrder(this->theVector, 1u, 3);
+}
+
+// Insert a single element.
+TYPED_TEST(CompactVectorTest, InsertTest) {
+  SCOPED_TRACE("InsertTest");
+
+  this->makeSequence(this->theVector, 1, 3);
+  typename TypeParam::iterator I =
+    this->theVector.insert(this->theVector.begin() + 1, Constructable(77));
+  EXPECT_EQ(this->theVector.begin() + 1, I);
+  this->assertValuesInOrder(this->theVector, 4u, 1, 77, 2, 3);
+}
+
+// Insert a copy of a single element.
+TYPED_TEST(CompactVectorTest, InsertCopy) {
+  SCOPED_TRACE("InsertTest");
+
+  this->makeSequence(this->theVector, 1, 3);
+  Constructable C(77);
+  typename TypeParam::iterator I =
+      this->theVector.insert(this->theVector.begin() + 1, C);
+  EXPECT_EQ(this->theVector.begin() + 1, I);
+  this->assertValuesInOrder(this->theVector, 4u, 1, 77, 2, 3);
+}
+
+// Insert repeated elements.
+TYPED_TEST(CompactVectorTest, InsertRepeatedTest) {
+  SCOPED_TRACE("InsertRepeatedTest");
+
+  this->makeSequence(this->theVector, 1, 4);
+  Constructable::reset();
+  auto I =
+      this->theVector.insert(this->theVector.begin() + 1, 2, Constructable(16));
+  // Move construct the top element into newly allocated space, and optionally
+  // reallocate the whole buffer, move constructing into it.
+  // FIXME: This is inefficient, we shouldn't move things into newly allocated
+  // space, then move them up/around, there should only be 2 or 4 move
+  // constructions here.
+  EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 2 ||
+              Constructable::getNumMoveConstructorCalls() == 6);
+  // Move assign the next two to shift them up and make a gap.
+  EXPECT_EQ(1, Constructable::getNumMoveAssignmentCalls());
+  // Copy construct the two new elements from the parameter.
+  EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls());
+  // All without any copy construction.
+  EXPECT_EQ(0, Constructable::getNumCopyConstructorCalls());
+  EXPECT_EQ(this->theVector.begin() + 1, I);
+  this->assertValuesInOrder(this->theVector, 6u, 1, 16, 16, 2, 3, 4);
+}
+
+
+TYPED_TEST(CompactVectorTest, InsertRepeatedAtEndTest) {
+  SCOPED_TRACE("InsertRepeatedTest");
+
+  this->makeSequence(this->theVector, 1, 4);
+  Constructable::reset();
+  auto I = this->theVector.insert(this->theVector.end(), 2, Constructable(16));
+  // Just copy construct them into newly allocated space
+  EXPECT_EQ(2, Constructable::getNumCopyConstructorCalls());
+  // Move everything across if reallocation is needed.
+  EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 0 ||
+              Constructable::getNumMoveConstructorCalls() == 4);
+  // Without ever moving or copying anything else.
+  EXPECT_EQ(0, Constructable::getNumCopyAssignmentCalls());
+  EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls());
+
+  EXPECT_EQ(this->theVector.begin() + 4, I);
+  this->assertValuesInOrder(this->theVector, 6u, 1, 2, 3, 4, 16, 16);
+}
+
+TYPED_TEST(CompactVectorTest, InsertRepeatedEmptyTest) {
+  SCOPED_TRACE("InsertRepeatedTest");
+
+  this->makeSequence(this->theVector, 10, 15);
+
+  // Empty insert.
+  EXPECT_EQ(this->theVector.end(),
+            this->theVector.insert(this->theVector.end(),
+                                   0, Constructable(42)));
+  EXPECT_EQ(this->theVector.begin() + 1,
+            this->theVector.insert(this->theVector.begin() + 1,
+                                   0, Constructable(42)));
+}
+
+// Insert range.
+TYPED_TEST(CompactVectorTest, InsertRangeTest) {
+  SCOPED_TRACE("InsertRangeTest");
+
+  Constructable Arr[3] =
+    { Constructable(77), Constructable(77), Constructable(77) };
+
+  this->makeSequence(this->theVector, 1, 3);
+  Constructable::reset();
+  auto I = this->theVector.insert(this->theVector.begin() + 1, Arr, Arr + 3);
+  // Move construct the top 3 elements into newly allocated space.
+  // Possibly move the whole sequence into new space first.
+  // FIXME: This is inefficient, we shouldn't move things into newly allocated
+  // space, then move them up/around, there should only be 2 or 3 move
+  // constructions here.
+  EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 2 ||
+              Constructable::getNumMoveConstructorCalls() == 5);
+  // Copy assign the lower 2 new elements into existing space.
+  EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls());
+  // Copy construct the third element into newly allocated space.
+  EXPECT_EQ(1, Constructable::getNumCopyConstructorCalls());
+  EXPECT_EQ(this->theVector.begin() + 1, I);
+  this->assertValuesInOrder(this->theVector, 6u, 1, 77, 77, 77, 2, 3);
+}
+
+
+TYPED_TEST(CompactVectorTest, InsertRangeAtEndTest) {
+  SCOPED_TRACE("InsertRangeTest");
+
+  Constructable Arr[3] =
+    { Constructable(77), Constructable(77), Constructable(77) };
+
+  this->makeSequence(this->theVector, 1, 3);
+
+  // Insert at end.
+  Constructable::reset();
+  auto I = this->theVector.insert(this->theVector.end(), Arr, Arr+3);
+  // Copy construct the 3 elements into new space at the top.
+  EXPECT_EQ(3, Constructable::getNumCopyConstructorCalls());
+  // Don't copy/move anything else.
+  EXPECT_EQ(0, Constructable::getNumCopyAssignmentCalls());
+  // Reallocation might occur, causing all elements to be moved into the new
+  // buffer.
+  EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 0 ||
+              Constructable::getNumMoveConstructorCalls() == 3);
+  EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls());
+  EXPECT_EQ(this->theVector.begin() + 3, I);
+  this->assertValuesInOrder(this->theVector, 6u,
+                            1, 2, 3, 77, 77, 77);
+}
+
+TYPED_TEST(CompactVectorTest, InsertEmptyRangeTest) {
+  SCOPED_TRACE("InsertRangeTest");
+
+  this->makeSequence(this->theVector, 1, 3);
+
+  // Empty insert.
+  EXPECT_EQ(this->theVector.end(),
+            this->theVector.insert(this->theVector.end(),
+                                   this->theVector.begin(),
+                                   this->theVector.begin()));
+  EXPECT_EQ(this->theVector.begin() + 1,
+            this->theVector.insert(this->theVector.begin() + 1,
+                                   this->theVector.begin(),
+                                   this->theVector.begin()));
+}
+
+// Comparison tests.
+TYPED_TEST(CompactVectorTest, ComparisonTest) {
+  SCOPED_TRACE("ComparisonTest");
+
+  this->makeSequence(this->theVector, 1, 3);
+  this->makeSequence(this->otherVector, 1, 3);
+
+  EXPECT_TRUE(this->theVector == this->otherVector);
+  EXPECT_FALSE(this->theVector != this->otherVector);
+
+  this->otherVector.clear();
+  this->makeSequence(this->otherVector, 2, 4);
+
+  EXPECT_FALSE(this->theVector == this->otherVector);
+  EXPECT_TRUE(this->theVector != this->otherVector);
+}
+
+// Constant vector tests.
+TYPED_TEST(CompactVectorTest, ConstVectorTest) {
+  const TypeParam constVector;
+
+  EXPECT_EQ(0u, constVector.size());
+  EXPECT_TRUE(constVector.empty());
+  EXPECT_TRUE(constVector.begin() == constVector.end());
+}
+
+// Direct array access.
+TYPED_TEST(CompactVectorTest, DirectVectorTest) {
+  EXPECT_EQ(0u, this->theVector.size());
+  this->theVector.reserve(4);
+  EXPECT_LE(4u, this->theVector.capacity());
+  EXPECT_EQ(0, Constructable::getNumConstructorCalls());
+  this->theVector.push_back(1);
+  this->theVector.push_back(2);
+  this->theVector.push_back(3);
+  this->theVector.push_back(4);
+  EXPECT_EQ(4u, this->theVector.size());
+  EXPECT_EQ(8, Constructable::getNumConstructorCalls());
+  EXPECT_EQ(1, this->theVector[0].getValue());
+  EXPECT_EQ(2, this->theVector[1].getValue());
+  EXPECT_EQ(3, this->theVector[2].getValue());
+  EXPECT_EQ(4, this->theVector[3].getValue());
+}
+
+TYPED_TEST(CompactVectorTest, IteratorTest) {
+  std::list<int> L;
+  this->theVector.insert(this->theVector.end(), L.begin(), L.end());
+}
+
+template <typename InvalidType> class DualCompactVectorsTest;
+
+template <typename VectorT1, typename VectorT2>
+class DualCompactVectorsTest<std::pair<VectorT1, VectorT2>> : public CompactVectorTestBase {
+protected:
+  VectorT1 theVector;
+  VectorT2 otherVector;
+
+  template <typename T, size_t N>
+  static size_t NumBuiltinElts(const TCompactVector<T, N>&) { return N; }
+};
+
+using DualCompactVectorTestTypes = ::testing::Types<
+    // Small mode -> Small mode.
+    std::pair<TCompactVector<Constructable, 4>, TCompactVector<Constructable, 4>>,
+    // Small mode -> Big mode.
+    std::pair<TCompactVector<Constructable, 4>, TCompactVector<Constructable, 2>>,
+    // Big mode -> Small mode.
+    std::pair<TCompactVector<Constructable, 2>, TCompactVector<Constructable, 4>>,
+    // Big mode -> Big mode.
+    std::pair<TCompactVector<Constructable, 2>, TCompactVector<Constructable, 2>>
+  >;
+
+TYPED_TEST_SUITE(DualCompactVectorsTest, DualCompactVectorTestTypes);
+
+TYPED_TEST(DualCompactVectorsTest, MoveAssignment) {
+  SCOPED_TRACE("MoveAssignTest-DualVectorTypes");
+
+  // Set up our vector with four elements.
+  for (unsigned I = 0; I < 4; ++I)
+    this->otherVector.push_back(Constructable(I));
+
+  const Constructable *OrigDataPtr = this->otherVector.data();
+
+  // Move-assign from the other vector.
+  this->theVector =
+    std::move(this->otherVector);
+
+  // Make sure we have the right result.
+  this->assertValuesInOrder(this->theVector, 4u, 0, 1, 2, 3);
+
+  // Make sure the # of constructor/destructor calls line up. There
+  // are two live objects after clearing the other vector.
+  this->otherVector.clear();
+  EXPECT_EQ(Constructable::getNumConstructorCalls()-4,
+            Constructable::getNumDestructorCalls());
+
+  // If the source vector (otherVector) was in small-mode, assert that we just
+  // moved the data pointer over.
+  EXPECT_TRUE(this->NumBuiltinElts(this->otherVector) == 4 ||
+              this->theVector.data() == OrigDataPtr);
+
+  // There shouldn't be any live objects any more.
+  this->theVector.clear();
+  EXPECT_EQ(Constructable::getNumConstructorCalls(),
+            Constructable::getNumDestructorCalls());
+
+  // We shouldn't have copied anything in this whole process.
+  EXPECT_EQ(Constructable::getNumCopyConstructorCalls(), 0);
+}
+
+struct notassignable {
+  int &x;
+  notassignable(int &x) : x(x) {}
+};
+
+TEST(CompactVectorCustomTest, NoAssignTest) {
+  int x = 0;
+  TCompactVector<notassignable, 2> vec;
+  vec.push_back(notassignable(x));
+  x = 42;
+  EXPECT_EQ(42, vec.back().x);
+}
+
+struct MovedFrom {
+  bool hasValue;
+  MovedFrom() : hasValue(true) {
+  }
+  MovedFrom(MovedFrom&& m) : hasValue(m.hasValue) {
+    m.hasValue = false;
+  }
+  MovedFrom &operator=(MovedFrom&& m) {
+    hasValue = m.hasValue;
+    m.hasValue = false;
+    return *this;
+  }
+};
+
+TEST(CompactVectorTest, MidInsert) {
+  TCompactVector<MovedFrom, 3> v;
+  v.push_back(MovedFrom());
+  v.insert(v.begin(), MovedFrom());
+  for (MovedFrom &m : v)
+    EXPECT_TRUE(m.hasValue);
+}
+
+enum EmplaceableArgState {
+  EAS_Defaulted,
+  EAS_Arg,
+  EAS_LValue,
+  EAS_RValue,
+  EAS_Failure
+};
+template <int I> struct EmplaceableArg {
+  EmplaceableArgState State;
+  EmplaceableArg() : State(EAS_Defaulted) {}
+  EmplaceableArg(EmplaceableArg &&X)
+      : State(X.State == EAS_Arg ? EAS_RValue : EAS_Failure) {}
+  EmplaceableArg(EmplaceableArg &X)
+      : State(X.State == EAS_Arg ? EAS_LValue : EAS_Failure) {}
+
+  explicit EmplaceableArg(bool) : State(EAS_Arg) {}
+
+private:
+  EmplaceableArg &operator=(EmplaceableArg &&) = delete;
+  EmplaceableArg &operator=(const EmplaceableArg &) = delete;
+};
+
+enum EmplaceableState { ES_Emplaced, ES_Moved };
+struct Emplaceable {
+  EmplaceableArg<0> A0;
+  EmplaceableArg<1> A1;
+  EmplaceableArg<2> A2;
+  EmplaceableArg<3> A3;
+  EmplaceableState State;
+
+  Emplaceable() : State(ES_Emplaced) {}
+
+  template <class A0Ty>
+  explicit Emplaceable(A0Ty &&A0)
+      : A0(std::forward<A0Ty>(A0)), State(ES_Emplaced) {}
+
+  template <class A0Ty, class A1Ty>
+  Emplaceable(A0Ty &&A0, A1Ty &&A1)
+      : A0(std::forward<A0Ty>(A0)), A1(std::forward<A1Ty>(A1)),
+        State(ES_Emplaced) {}
+
+  template <class A0Ty, class A1Ty, class A2Ty>
+  Emplaceable(A0Ty &&A0, A1Ty &&A1, A2Ty &&A2)
+      : A0(std::forward<A0Ty>(A0)), A1(std::forward<A1Ty>(A1)),
+        A2(std::forward<A2Ty>(A2)), State(ES_Emplaced) {}
+
+  template <class A0Ty, class A1Ty, class A2Ty, class A3Ty>
+  Emplaceable(A0Ty &&A0, A1Ty &&A1, A2Ty &&A2, A3Ty &&A3)
+      : A0(std::forward<A0Ty>(A0)), A1(std::forward<A1Ty>(A1)),
+        A2(std::forward<A2Ty>(A2)), A3(std::forward<A3Ty>(A3)),
+        State(ES_Emplaced) {}
+
+  Emplaceable(Emplaceable &&) : State(ES_Moved) {}
+  Emplaceable &operator=(Emplaceable &&) {
+    State = ES_Moved;
+    return *this;
+  }
+
+private:
+  Emplaceable(const Emplaceable &) = delete;
+  Emplaceable &operator=(const Emplaceable &) = delete;
+};
+
+TEST(CompactVectorTest, EmplaceBack) {
+  EmplaceableArg<0> A0(true);
+  EmplaceableArg<1> A1(true);
+  EmplaceableArg<2> A2(true);
+  EmplaceableArg<3> A3(true);
+  {
+    TCompactVector<Emplaceable, 3> V;
+    V.emplace_back();
+    EXPECT_TRUE(V.size() == 1);
+    EXPECT_TRUE(V.back().State == ES_Emplaced);
+    EXPECT_TRUE(V.back().A0.State == EAS_Defaulted);
+    EXPECT_TRUE(V.back().A1.State == EAS_Defaulted);
+    EXPECT_TRUE(V.back().A2.State == EAS_Defaulted);
+    EXPECT_TRUE(V.back().A3.State == EAS_Defaulted);
+  }
+  {
+    TCompactVector<Emplaceable, 3> V;
+    V.emplace_back(std::move(A0));
+    EXPECT_TRUE(V.size() == 1);
+    EXPECT_TRUE(V.back().State == ES_Emplaced);
+    EXPECT_TRUE(V.back().A0.State == EAS_RValue);
+    EXPECT_TRUE(V.back().A1.State == EAS_Defaulted);
+    EXPECT_TRUE(V.back().A2.State == EAS_Defaulted);
+    EXPECT_TRUE(V.back().A3.State == EAS_Defaulted);
+  }
+  {
+    TCompactVector<Emplaceable, 3> V;
+    V.emplace_back(A0);
+    EXPECT_TRUE(V.size() == 1);
+    EXPECT_TRUE(V.back().State == ES_Emplaced);
+    EXPECT_TRUE(V.back().A0.State == EAS_LValue);
+    EXPECT_TRUE(V.back().A1.State == EAS_Defaulted);
+    EXPECT_TRUE(V.back().A2.State == EAS_Defaulted);
+    EXPECT_TRUE(V.back().A3.State == EAS_Defaulted);
+  }
+  {
+    TCompactVector<Emplaceable, 3> V;
+    V.emplace_back(A0, A1);
+    EXPECT_TRUE(V.size() == 1);
+    EXPECT_TRUE(V.back().State == ES_Emplaced);
+    EXPECT_TRUE(V.back().A0.State == EAS_LValue);
+    EXPECT_TRUE(V.back().A1.State == EAS_LValue);
+    EXPECT_TRUE(V.back().A2.State == EAS_Defaulted);
+    EXPECT_TRUE(V.back().A3.State == EAS_Defaulted);
+  }
+  {
+    TCompactVector<Emplaceable, 3> V;
+    V.emplace_back(std::move(A0), std::move(A1));
+    EXPECT_TRUE(V.size() == 1);
+    EXPECT_TRUE(V.back().State == ES_Emplaced);
+    EXPECT_TRUE(V.back().A0.State == EAS_RValue);
+    EXPECT_TRUE(V.back().A1.State == EAS_RValue);
+    EXPECT_TRUE(V.back().A2.State == EAS_Defaulted);
+    EXPECT_TRUE(V.back().A3.State == EAS_Defaulted);
+  }
+  {
+    TCompactVector<Emplaceable, 3> V;
+    V.emplace_back(std::move(A0), A1, std::move(A2), A3);
+    EXPECT_TRUE(V.size() == 1);
+    EXPECT_TRUE(V.back().State == ES_Emplaced);
+    EXPECT_TRUE(V.back().A0.State == EAS_RValue);
+    EXPECT_TRUE(V.back().A1.State == EAS_LValue);
+    EXPECT_TRUE(V.back().A2.State == EAS_RValue);
+    EXPECT_TRUE(V.back().A3.State == EAS_LValue);
+  }
+  {
+    TCompactVector<int, 1> V;
+    V.emplace_back();
+    V.emplace_back(42);
+    EXPECT_EQ(2U, V.size());
+    EXPECT_EQ(0, V[0]);
+    EXPECT_EQ(42, V[1]);
+  }
+}
+
+TEST(CompactVectorTest, Emplace) {
+  EmplaceableArg<0> A0(true);
+  EmplaceableArg<1> A1(true);
+  EmplaceableArg<2> A2(true);
+  EmplaceableArg<3> A3(true);
+  {
+    TCompactVector<Emplaceable, 3> V;
+    V.emplace(V.end());
+    EXPECT_TRUE(V.size() == 1);
+    EXPECT_TRUE(V.back().State == ES_Emplaced);
+    EXPECT_TRUE(V.back().A0.State == EAS_Defaulted);
+    EXPECT_TRUE(V.back().A1.State == EAS_Defaulted);
+    EXPECT_TRUE(V.back().A2.State == EAS_Defaulted);
+    EXPECT_TRUE(V.back().A3.State == EAS_Defaulted);
+  }
+  {
+    TCompactVector<Emplaceable, 3> V;
+    V.emplace(V.end(), std::move(A0));
+    EXPECT_TRUE(V.size() == 1);
+    EXPECT_TRUE(V.back().State == ES_Emplaced);
+    EXPECT_TRUE(V.back().A0.State == EAS_RValue);
+    EXPECT_TRUE(V.back().A1.State == EAS_Defaulted);
+    EXPECT_TRUE(V.back().A2.State == EAS_Defaulted);
+    EXPECT_TRUE(V.back().A3.State == EAS_Defaulted);
+  }
+  {
+    TCompactVector<Emplaceable, 3> V;
+    V.emplace(V.end(), A0);
+    EXPECT_TRUE(V.size() == 1);
+    EXPECT_TRUE(V.back().State == ES_Emplaced);
+    EXPECT_TRUE(V.back().A0.State == EAS_LValue);
+    EXPECT_TRUE(V.back().A1.State == EAS_Defaulted);
+    EXPECT_TRUE(V.back().A2.State == EAS_Defaulted);
+    EXPECT_TRUE(V.back().A3.State == EAS_Defaulted);
+  }
+  {
+    TCompactVector<Emplaceable, 3> V;
+    V.emplace(V.end(), A0, A1);
+    EXPECT_TRUE(V.size() == 1);
+    EXPECT_TRUE(V.back().State == ES_Emplaced);
+    EXPECT_TRUE(V.back().A0.State == EAS_LValue);
+    EXPECT_TRUE(V.back().A1.State == EAS_LValue);
+    EXPECT_TRUE(V.back().A2.State == EAS_Defaulted);
+    EXPECT_TRUE(V.back().A3.State == EAS_Defaulted);
+  }
+  {
+    TCompactVector<Emplaceable, 3> V;
+    V.emplace(V.end(), std::move(A0), std::move(A1));
+    EXPECT_TRUE(V.size() == 1);
+    EXPECT_TRUE(V.back().State == ES_Emplaced);
+    EXPECT_TRUE(V.back().A0.State == EAS_RValue);
+    EXPECT_TRUE(V.back().A1.State == EAS_RValue);
+    EXPECT_TRUE(V.back().A2.State == EAS_Defaulted);
+    EXPECT_TRUE(V.back().A3.State == EAS_Defaulted);
+  }
+  {
+    TCompactVector<Emplaceable, 3> V;
+    V.emplace(V.end(), std::move(A0), A1, std::move(A2), A3);
+    EXPECT_TRUE(V.size() == 1);
+    EXPECT_TRUE(V.back().State == ES_Emplaced);
+    EXPECT_TRUE(V.back().A0.State == EAS_RValue);
+    EXPECT_TRUE(V.back().A1.State == EAS_LValue);
+    EXPECT_TRUE(V.back().A2.State == EAS_RValue);
+    EXPECT_TRUE(V.back().A3.State == EAS_LValue);
+  }
+  {
+    TCompactVector<int, 1> V;
+    V.emplace_back(42);
+    V.emplace(V.begin(), 0);
+    EXPECT_EQ(2U, V.size());
+    EXPECT_EQ(0, V[0]);
+    EXPECT_EQ(42, V[1]);
+  }
+}
+
+template <class T, size_t N>
+class TStubArray
+{
+public:
+    TStubArray(const TCompactVector<T, N>& vector)
+        : Vector_(vector)
+    { }
+
+    bool equals(std::initializer_list<T> list)
+    {
+        return std::equal(Vector_.begin(), Vector_.end(), list.begin());
+    }
+
+    TCompactVector<T, N> Vector_;
+};
+
+template <typename T, size_t N>
+TStubArray<T, N> makeArrayRef(const TCompactVector<T, N>& vector)
+{
+    return TStubArray<T, N>(vector);
+}
+
+TEST(CompactVectorTest, InitializerList) {
+  TCompactVector<int, 2> V1 = {};
+  EXPECT_TRUE(V1.empty());
+  V1 = {0, 0};
+  EXPECT_TRUE(makeArrayRef(V1).equals({0, 0}));
+  V1 = {-1, -1};
+  EXPECT_TRUE(makeArrayRef(V1).equals({-1, -1}));
+
+  TCompactVector<int, 2> V2 = {1, 2, 3, 4};
+  EXPECT_TRUE(makeArrayRef(V2).equals({1, 2, 3, 4}));
+  V2.assign({4});
+  EXPECT_TRUE(makeArrayRef(V2).equals({4}));
+  V2.insert(V2.end(), {3, 2});
+  EXPECT_TRUE(makeArrayRef(V2).equals({4, 3, 2}));
+  V2.insert(V2.begin() + 1, 5);
+  EXPECT_TRUE(makeArrayRef(V2).equals({4, 5, 3, 2}));
+}
+
+TEST(CompactVectorTest, AssignToShorter) {
+  TCompactVector<TString, 4> lhs;
+  TCompactVector<TString, 4> rhs;
+  rhs.emplace_back("foo");
+  lhs = rhs;
+  EXPECT_EQ(1U, lhs.size());
+  EXPECT_EQ("foo", lhs[0]);
+}
+
+TEST(CompactVectorTest, AssignToLonger) {
+  TCompactVector<TString, 4> lhs;
+  lhs.emplace_back("bar");
+  lhs.emplace_back("baz");
+  TCompactVector<TString, 4> rhs;
+  rhs.emplace_back("foo");
+  lhs = rhs;
+  EXPECT_EQ(1U, lhs.size());
+  EXPECT_EQ("foo", lhs[0]);
+}
+
+TEST(CompactVectorTest, ZeroPaddingOnHeapMeta) {
+  TCompactVector<uint8_t, 6> vector;
+  std::vector<uint8_t> expected;
+  for (int i = 0; i < 10; ++i) {
+    vector.push_back(i);
+    expected.push_back(i);
+
+    ASSERT_THAT(vector, ::testing::ElementsAreArray(expected));
+  }
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+} // namespace
+} // namespace NYT
diff --git a/library/cpp/yt/compact_containers/unittests/ya.make b/library/cpp/yt/compact_containers/unittests/ya.make
new file mode 100644
index 00000000000..430f28fef26
--- /dev/null
+++ b/library/cpp/yt/compact_containers/unittests/ya.make
@@ -0,0 +1,18 @@
+GTEST(unittester-small-containers)
+
+INCLUDE(${ARCADIA_ROOT}/library/cpp/yt/ya_cpp.make.inc)
+
+SRCS(
+    compact_flat_map_ut.cpp
+    compact_heap_ut.cpp
+    compact_set_ut.cpp
+    compact_vector_ut.cpp
+    compact_queue_ut.cpp
+)
+
+PEERDIR(
+    library/cpp/yt/compact_containers
+    library/cpp/testing/gtest
+)
+
+END()
diff --git a/library/cpp/yt/compact_containers/ya.make b/library/cpp/yt/compact_containers/ya.make
new file mode 100644
index 00000000000..e52beb943c1
--- /dev/null
+++ b/library/cpp/yt/compact_containers/ya.make
@@ -0,0 +1,23 @@
+LIBRARY()
+
+INCLUDE(${ARCADIA_ROOT}/library/cpp/yt/ya_cpp.make.inc)
+
+PEERDIR(
+    library/cpp/yt/assert
+    library/cpp/yt/malloc
+    library/cpp/yt/misc
+)
+
+CHECK_DEPENDENT_DIRS(
+    ALLOW_ONLY ALL
+    build
+    contrib
+    library
+    util
+)
+
+END()
+
+RECURSE_FOR_TESTS(
+    unittests
+)