intermediate changes

ref:cde9a383711a11544ce7e107a78147fb96cc4029

5 files changed, 833 insertions, 0 deletions

diff --git a/library/cpp/containers/paged_vector/paged_vector.cpp b/library/cpp/containers/paged_vector/paged_vector.cpp
new file mode 100644
index 0000000000..e354caf09d
--- /dev/null
+++ b/library/cpp/containers/paged_vector/paged_vector.cpp
@@ -0,0 +1 @@
+#include "paged_vector.h"
diff --git a/library/cpp/containers/paged_vector/paged_vector.h b/library/cpp/containers/paged_vector/paged_vector.h
new file mode 100644
index 0000000000..6a3657d3ea
--- /dev/null
+++ b/library/cpp/containers/paged_vector/paged_vector.h
@@ -0,0 +1,432 @@
+#pragma once
+
+#include <util/generic/ptr.h>
+#include <util/generic/vector.h>
+#include <util/generic/yexception.h>
+
+#include <iterator>
+
+namespace NPagedVector {
+    template <class T, ui32 PageSize = 1u << 20, class A = std::allocator<T>>
+    class TPagedVector;
+
+    namespace NPrivate {
+        template <class T, class TT, ui32 PageSize, class A>
+        struct TPagedVectorIterator {
+        private:
+            friend class TPagedVector<TT, PageSize, A>;
+            typedef TPagedVector<TT, PageSize, A> TVec;
+            typedef TPagedVectorIterator<T, TT, PageSize, A> TSelf;
+            size_t Offset;
+            TVec* Vector;
+
+            template <class T1, class TT1, ui32 PageSize1, class A1>
+            friend struct TPagedVectorIterator;
+
+        public:
+            TPagedVectorIterator()
+                : Offset()
+                , Vector()
+            {
+            }
+
+            TPagedVectorIterator(TVec* vector, size_t offset)
+                : Offset(offset)
+                , Vector(vector)
+            {
+            }
+
+            template <class T1, class TT1, ui32 PageSize1, class A1>
+            TPagedVectorIterator(const TPagedVectorIterator<T1, TT1, PageSize1, A1>& it)
+                : Offset(it.Offset)
+                , Vector(it.Vector)
+            {
+            }
+
+            T& operator*() const {
+                return (*Vector)[Offset];
+            }
+
+            T* operator->() const {
+                return &(**this);
+            }
+
+            template <class T1, class TT1, ui32 PageSize1, class A1>
+            bool operator==(const TPagedVectorIterator<T1, TT1, PageSize1, A1>& it) const {
+                return Offset == it.Offset;
+            }
+
+            template <class T1, class TT1, ui32 PageSize1, class A1>
+            bool operator!=(const TPagedVectorIterator<T1, TT1, PageSize1, A1>& it) const {
+                return !(*this == it);
+            }
+
+            template <class T1, class TT1, ui32 PageSize1, class A1>
+            bool operator<(const TPagedVectorIterator<T1, TT1, PageSize1, A1>& it) const {
+                return Offset < it.Offset;
+            }
+
+            template <class T1, class TT1, ui32 PageSize1, class A1>
+            bool operator<=(const TPagedVectorIterator<T1, TT1, PageSize1, A1>& it) const {
+                return Offset <= it.Offset;
+            }
+
+            template <class T1, class TT1, ui32 PageSize1, class A1>
+            bool operator>(const TPagedVectorIterator<T1, TT1, PageSize1, A1>& it) const {
+                return !(*this <= it);
+            }
+
+            template <class T1, class TT1, ui32 PageSize1, class A1>
+            bool operator>=(const TPagedVectorIterator<T1, TT1, PageSize1, A1>& it) const {
+                return !(*this < it);
+            }
+
+            template <class T1, class TT1, ui32 PageSize1, class A1>
+            ptrdiff_t operator-(const TPagedVectorIterator<T1, TT1, PageSize1, A1>& it) const {
+                return Offset - it.Offset;
+            }
+
+            TSelf& operator+=(ptrdiff_t off) {
+                Offset += off;
+                return *this;
+            }
+
+            TSelf& operator-=(ptrdiff_t off) {
+                return this->operator+=(-off);
+            }
+
+            TSelf& operator++() {
+                return this->operator+=(1);
+            }
+
+            TSelf& operator--() {
+                return this->operator+=(-1);
+            }
+
+            TSelf operator++(int) {
+                TSelf it = *this;
+                this->operator+=(1);
+                return it;
+            }
+
+            TSelf operator--(int) {
+                TSelf it = *this;
+                this->operator+=(-1);
+                return it;
+            }
+
+            TSelf operator+(ptrdiff_t off) {
+                TSelf res = *this;
+                res += off;
+                return res;
+            }
+
+            TSelf operator-(ptrdiff_t off) {
+                return this->operator+(-off);
+            }
+
+            size_t GetOffset() {
+                return Offset;
+            }
+        };
+    }
+}
+
+namespace std {
+    template <class T, class TT, ui32 PageSize, class A>
+    struct iterator_traits<NPagedVector::NPrivate::TPagedVectorIterator<T, TT, PageSize, A>> {
+        typedef ptrdiff_t difference_type;
+        typedef T value_type;
+        typedef T* pointer;
+        typedef T& reference;
+        typedef random_access_iterator_tag iterator_category;
+    };
+
+}
+
+namespace NPagedVector {
+    //2-level radix tree
+    template <class T, ui32 PageSize, class A>
+    class TPagedVector: private TVector<TSimpleSharedPtr<TVector<T, A>>, A> {
+        static_assert(PageSize, "expect PageSize");
+
+        typedef TVector<T, A> TPage;
+        typedef TVector<TSimpleSharedPtr<TPage>, A> TPages;
+        typedef TPagedVector<T, PageSize, A> TSelf;
+
+    public:
+        typedef NPrivate::TPagedVectorIterator<T, T, PageSize, A> iterator;
+        typedef NPrivate::TPagedVectorIterator<const T, T, PageSize, A> const_iterator;
+        typedef std::reverse_iterator<iterator> reverse_iterator;
+        typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
+        typedef T value_type;
+        typedef value_type& reference;
+        typedef const value_type& const_reference;
+
+        TPagedVector() = default;
+
+        template <typename TIter>
+        TPagedVector(TIter b, TIter e) {
+            append(b, e);
+        }
+
+        iterator begin() {
+            return iterator(this, 0);
+        }
+
+        const_iterator begin() const {
+            return const_iterator((TSelf*)this, 0);
+        }
+
+        iterator end() {
+            return iterator(this, size());
+        }
+
+        const_iterator end() const {
+            return const_iterator((TSelf*)this, size());
+        }
+
+        reverse_iterator rbegin() {
+            return reverse_iterator(end());
+        }
+
+        const_reverse_iterator rbegin() const {
+            return const_reverse_iterator(end());
+        }
+
+        reverse_iterator rend() {
+            return reverse_iterator(begin());
+        }
+
+        const_reverse_iterator rend() const {
+            return const_reverse_iterator(begin());
+        }
+
+        void swap(TSelf& v) {
+            TPages::swap((TPages&)v);
+        }
+
+    private:
+        static size_t PageNumber(size_t idx) {
+            return idx / PageSize;
+        }
+
+        static size_t InPageIndex(size_t idx) {
+            return idx % PageSize;
+        }
+
+        static size_t Index(size_t pnum, size_t poff) {
+            return pnum * PageSize + poff;
+        }
+
+        TPage& PageAt(size_t pnum) const {
+            return *TPages::at(pnum);
+        }
+
+        TPage& CurrentPage() const {
+            return *TPages::back();
+        }
+
+        size_t CurrentPageSize() const {
+            return TPages::empty() ? 0 : CurrentPage().size();
+        }
+
+        size_t NPages() const {
+            return TPages::size();
+        }
+
+        void AllocateNewPage() {
+            TPages::push_back(new TPage());
+            CurrentPage().reserve(PageSize);
+        }
+
+        void MakeNewPage() {
+            AllocateNewPage();
+            CurrentPage().resize(PageSize);
+        }
+
+        void PrepareAppend() {
+            if (TPages::empty() || CurrentPage().size() + 1 > PageSize)
+                AllocateNewPage();
+        }
+
+    public:
+        size_t size() const {
+            return empty() ? 0 : (NPages() - 1) * PageSize + CurrentPage().size();
+        }
+
+        bool empty() const {
+            return TPages::empty() || 1 == NPages() && CurrentPage().empty();
+        }
+
+        explicit operator bool() const noexcept {
+            return !empty();
+        }
+
+        void emplace_back() {
+            PrepareAppend();
+            CurrentPage().emplace_back();
+        }
+
+        void push_back(const_reference t) {
+            PrepareAppend();
+            CurrentPage().push_back(t);
+        }
+
+        void pop_back() {
+            if (CurrentPage().empty())
+                TPages::pop_back();
+            CurrentPage().pop_back();
+        }
+
+        template <typename TIter>
+        void append(TIter b, TIter e) {
+            size_t sz = e - b;
+            size_t sz1 = Min<size_t>(sz, PageSize - CurrentPageSize());
+            size_t sz2 = (sz - sz1) / PageSize;
+            size_t sz3 = (sz - sz1) % PageSize;
+
+            if (sz1) {
+                PrepareAppend();
+                TPage& p = CurrentPage();
+                p.insert(p.end(), b, b + sz1);
+            }
+
+            for (size_t i = 0; i < sz2; ++i) {
+                AllocateNewPage();
+                TPage& p = CurrentPage();
+                p.insert(p.end(), b + sz1 + i * PageSize, b + sz1 + (i + 1) * PageSize);
+            }
+
+            if (sz3) {
+                AllocateNewPage();
+                TPage& p = CurrentPage();
+                p.insert(p.end(), b + sz1 + sz2 * PageSize, e);
+            }
+        }
+
+        iterator erase(iterator it) {
+            size_t pnum = PageNumber(it.Offset);
+            size_t pidx = InPageIndex(it.Offset);
+
+            if (CurrentPage().empty())
+                TPages::pop_back();
+
+            for (size_t p = NPages() - 1; p > pnum; --p) {
+                PageAt(p - 1).push_back(PageAt(p).front());
+                PageAt(p).erase(PageAt(p).begin());
+            }
+
+            PageAt(pnum).erase(PageAt(pnum).begin() + pidx);
+            return it;
+        }
+
+        iterator erase(iterator b, iterator e) {
+            // todo : suboptimal!
+            while (b != e) {
+                b = erase(b);
+                --e;
+            }
+
+            return b;
+        }
+
+        iterator insert(iterator it, const value_type& v) {
+            size_t pnum = PageNumber(it.Offset);
+            size_t pidx = InPageIndex(it.Offset);
+
+            PrepareAppend();
+
+            for (size_t p = NPages() - 1; p > pnum; --p) {
+                PageAt(p).insert(PageAt(p).begin(), PageAt(p - 1).back());
+                PageAt(p - 1).pop_back();
+            }
+
+            PageAt(pnum).insert(PageAt(pnum).begin() + pidx, v);
+            return it;
+        }
+
+        template <typename TIter>
+        void insert(iterator it, TIter b, TIter e) {
+            // todo : suboptimal!
+            for (; b != e; ++b, ++it)
+                it = insert(it, *b);
+        }
+
+        reference front() {
+            return TPages::front()->front();
+        }
+
+        const_reference front() const {
+            return TPages::front()->front();
+        }
+
+        reference back() {
+            return CurrentPage().back();
+        }
+
+        const_reference back() const {
+            return CurrentPage().back();
+        }
+
+        void clear() {
+            TPages::clear();
+        }
+
+        void resize(size_t sz) {
+            if (sz == size())
+                return;
+
+            const size_t npages = NPages();
+            const size_t newwholepages = sz / PageSize;
+            const size_t pagepart = sz % PageSize;
+            const size_t newpages = newwholepages + bool(pagepart);
+
+            if (npages && newwholepages >= npages)
+                CurrentPage().resize(PageSize);
+
+            if (newpages < npages)
+                TPages::resize(newpages);
+            else
+                for (size_t i = npages; i < newpages; ++i)
+                    MakeNewPage();
+
+            if (pagepart)
+                CurrentPage().resize(pagepart);
+
+            Y_VERIFY(sz == size(), "%" PRIu64 " %" PRIu64, (ui64)sz, (ui64)size());
+        }
+
+        reference at(size_t idx) {
+            return TPages::at(PageNumber(idx))->at(InPageIndex(idx));
+        }
+
+        const_reference at(size_t idx) const {
+            return TPages::at(PageNumber(idx))->at(InPageIndex(idx));
+        }
+
+        reference operator[](size_t idx) {
+            return TPages::operator[](PageNumber(idx))->operator[](InPageIndex(idx));
+        }
+
+        const_reference operator[](size_t idx) const {
+            return TPages::operator[](PageNumber(idx))->operator[](InPageIndex(idx));
+        }
+
+        friend bool operator==(const TSelf& a, const TSelf& b) {
+            return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin());
+        }
+
+        friend bool operator<(const TSelf& a, const TSelf& b) {
+            return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
+        }
+    };
+
+    namespace NPrivate {
+        typedef std::is_same<std::random_access_iterator_tag, std::iterator_traits<
+                                                                  TPagedVector<ui32>::iterator>::iterator_category>
+            TIteratorCheck;
+        static_assert(TIteratorCheck::value, "expect TIteratorCheck::Result");
+    }
+
+}
diff --git a/library/cpp/containers/paged_vector/ut/paged_vector_ut.cpp b/library/cpp/containers/paged_vector/ut/paged_vector_ut.cpp
new file mode 100644
index 0000000000..e867808ee4
--- /dev/null
+++ b/library/cpp/containers/paged_vector/ut/paged_vector_ut.cpp
@@ -0,0 +1,378 @@
+#include <library/cpp/containers/paged_vector/paged_vector.h>
+#include <library/cpp/testing/unittest/registar.h>
+
+#include <stdexcept>
+
+class TPagedVectorTest: public TTestBase {
+    UNIT_TEST_SUITE(TPagedVectorTest);
+    UNIT_TEST(Test0)
+    UNIT_TEST(Test1)
+    UNIT_TEST(Test2)
+    UNIT_TEST(Test3)
+    UNIT_TEST(Test4)
+    UNIT_TEST(Test5)
+    UNIT_TEST(Test6)
+    UNIT_TEST(Test7)
+    UNIT_TEST(TestAt)
+    UNIT_TEST(TestAutoRef)
+    UNIT_TEST(TestIterators)
+    //UNIT_TEST(TestEbo)
+    UNIT_TEST_SUITE_END();
+
+private:
+    // Copy-paste of STLPort tests
+    void Test0() {
+        using NPagedVector::TPagedVector;
+        TPagedVector<int, 16> v1; // Empty vector of integers.
+
+        UNIT_ASSERT(v1.empty() == true);
+        UNIT_ASSERT(v1.size() == 0);
+
+        for (size_t i = 0; i < 256; ++i) {
+            v1.resize(i + 1);
+            UNIT_ASSERT_VALUES_EQUAL(v1.size(), i + 1);
+        }
+
+        for (size_t i = 256; i-- > 0;) {
+            v1.resize(i);
+            UNIT_ASSERT_VALUES_EQUAL(v1.size(), i);
+        }
+    }
+
+    void Test1() {
+        using NPagedVector::TPagedVector;
+        TPagedVector<int, 3> v1; // Empty vector of integers.
+
+        UNIT_ASSERT(v1.empty() == true);
+        UNIT_ASSERT(v1.size() == 0);
+
+        // UNIT_ASSERT(v1.max_size() == INT_MAX / sizeof(int));
+        // cout << "max_size = " << v1.max_size() << endl;
+        v1.push_back(42); // Add an integer to the vector.
+
+        UNIT_ASSERT(v1.size() == 1);
+
+        UNIT_ASSERT(v1[0] == 42);
+
+        {
+            TPagedVector<TPagedVector<int, 3>, 3> vect;
+            vect.resize(10);
+            UNIT_ASSERT(vect.size() == 10);
+            TPagedVector<TPagedVector<int, 3>, 3>::iterator it(vect.begin()), end(vect.end());
+            for (; it != end; ++it) {
+                UNIT_ASSERT((*it).empty());
+                UNIT_ASSERT((*it).size() == 0);
+                UNIT_ASSERT((*it).begin() == (*it).end());
+            }
+        }
+    }
+
+    void Test2() {
+        using NPagedVector::TPagedVector;
+        TPagedVector<double, 3> v1; // Empty vector of doubles.
+        v1.push_back(32.1);
+        v1.push_back(40.5);
+        v1.push_back(45.5);
+        v1.push_back(33.4);
+        TPagedVector<double, 3> v2; // Another empty vector of doubles.
+        v2.push_back(3.56);
+
+        UNIT_ASSERT(v1.size() == 4);
+        UNIT_ASSERT(v1[0] == 32.1);
+        UNIT_ASSERT(v1[1] == 40.5);
+        UNIT_ASSERT(v1[2] == 45.5);
+        UNIT_ASSERT(v1[3] == 33.4);
+
+        UNIT_ASSERT(v2.size() == 1);
+        UNIT_ASSERT(v2[0] == 3.56);
+        v1.swap(v2); // Swap the vector's contents.
+
+        UNIT_ASSERT(v1.size() == 1);
+        UNIT_ASSERT(v1[0] == 3.56);
+
+        UNIT_ASSERT(v2.size() == 4);
+        UNIT_ASSERT(v2[0] == 32.1);
+        UNIT_ASSERT(v2[1] == 40.5);
+        UNIT_ASSERT(v2[2] == 45.5);
+        UNIT_ASSERT(v2[3] == 33.4);
+
+        v2 = v1; // Assign one vector to another.
+
+        UNIT_ASSERT(v2.size() == 1);
+        UNIT_ASSERT(v2[0] == 3.56);
+
+        v2.pop_back();
+        UNIT_ASSERT(v2.size() == 0);
+        UNIT_ASSERT(v2.empty());
+    }
+
+    void Test3() {
+        using NPagedVector::TPagedVector;
+        TPagedVector<char, 1> v1;
+
+        v1.push_back('h');
+        v1.push_back('i');
+
+        UNIT_ASSERT(v1.size() == 2);
+        UNIT_ASSERT(v1[0] == 'h');
+        UNIT_ASSERT(v1[1] == 'i');
+
+        TPagedVector<char, 1> v2;
+        v2.resize(v1.size());
+
+        for (size_t i = 0; i < v1.size(); ++i)
+            v2[i] = v1[i];
+
+        v2[1] = 'o'; // Replace second character.
+
+        UNIT_ASSERT(v2.size() == 2);
+        UNIT_ASSERT(v2[0] == 'h');
+        UNIT_ASSERT(v2[1] == 'o');
+
+        UNIT_ASSERT((v1 == v2) == false);
+
+        UNIT_ASSERT((v1 < v2) == true);
+    }
+
+    void Test4() {
+        using NPagedVector::TPagedVector;
+        TPagedVector<int, 3> v;
+        v.resize(4);
+
+        v[0] = 1;
+        v[1] = 4;
+        v[2] = 9;
+        v[3] = 16;
+
+        UNIT_ASSERT(v.front() == 1);
+        UNIT_ASSERT(v.back() == 16);
+
+        v.push_back(25);
+
+        UNIT_ASSERT(v.back() == 25);
+        UNIT_ASSERT(v.size() == 5);
+
+        v.pop_back();
+
+        UNIT_ASSERT(v.back() == 16);
+        UNIT_ASSERT(v.size() == 4);
+    }
+
+    void Test5() {
+        int array[] = {1, 4, 9, 16};
+
+        typedef NPagedVector::TPagedVector<int, 3> TVectorType;
+        TVectorType v(array, array + 4);
+
+        UNIT_ASSERT(v.size() == 4);
+
+        UNIT_ASSERT(v[0] == 1);
+        UNIT_ASSERT(v[1] == 4);
+        UNIT_ASSERT(v[2] == 9);
+        UNIT_ASSERT(v[3] == 16);
+    }
+
+    void Test6() {
+        int array[] = {1, 4, 9, 16, 25, 36};
+
+        typedef NPagedVector::TPagedVector<int, 3> TVectorType;
+        TVectorType v(array, array + 6);
+        TVectorType::iterator vit;
+
+        UNIT_ASSERT_VALUES_EQUAL(v.size(), 6u);
+        UNIT_ASSERT(v[0] == 1);
+        UNIT_ASSERT(v[1] == 4);
+        UNIT_ASSERT(v[2] == 9);
+        UNIT_ASSERT(v[3] == 16);
+        UNIT_ASSERT(v[4] == 25);
+        UNIT_ASSERT(v[5] == 36);
+
+        vit = v.erase(v.begin()); // Erase first element.
+        UNIT_ASSERT(*vit == 4);
+
+        UNIT_ASSERT(v.size() == 5);
+        UNIT_ASSERT(v[0] == 4);
+        UNIT_ASSERT(v[1] == 9);
+        UNIT_ASSERT(v[2] == 16);
+        UNIT_ASSERT(v[3] == 25);
+        UNIT_ASSERT(v[4] == 36);
+
+        vit = v.erase(v.end() - 1); // Erase last element.
+        UNIT_ASSERT(vit == v.end());
+
+        UNIT_ASSERT(v.size() == 4);
+        UNIT_ASSERT(v[0] == 4);
+        UNIT_ASSERT(v[1] == 9);
+        UNIT_ASSERT(v[2] == 16);
+        UNIT_ASSERT(v[3] == 25);
+
+        v.erase(v.begin() + 1, v.end() - 1); // Erase all but first and last.
+
+        UNIT_ASSERT(v.size() == 2);
+        UNIT_ASSERT(v[0] == 4);
+        UNIT_ASSERT(v[1] == 25);
+    }
+
+    void Test7() {
+        int array1[] = {1, 4, 25};
+        int array2[] = {9, 16};
+
+        typedef NPagedVector::TPagedVector<int, 3> TVectorType;
+
+        TVectorType v(array1, array1 + 3);
+        TVectorType::iterator vit;
+        vit = v.insert(v.begin(), 0); // Insert before first element.
+        UNIT_ASSERT_VALUES_EQUAL(*vit, 0);
+
+        vit = v.insert(v.end(), 36); // Insert after last element.
+        UNIT_ASSERT(*vit == 36);
+
+        UNIT_ASSERT(v.size() == 5);
+        UNIT_ASSERT(v[0] == 0);
+        UNIT_ASSERT(v[1] == 1);
+        UNIT_ASSERT(v[2] == 4);
+        UNIT_ASSERT(v[3] == 25);
+        UNIT_ASSERT(v[4] == 36);
+
+        // Insert contents of array2 before fourth element.
+        v.insert(v.begin() + 3, array2, array2 + 2);
+
+        UNIT_ASSERT(v.size() == 7);
+
+        UNIT_ASSERT(v[0] == 0);
+        UNIT_ASSERT(v[1] == 1);
+        UNIT_ASSERT(v[2] == 4);
+        UNIT_ASSERT(v[3] == 9);
+        UNIT_ASSERT(v[4] == 16);
+        UNIT_ASSERT(v[5] == 25);
+        UNIT_ASSERT(v[6] == 36);
+
+        v.clear();
+        UNIT_ASSERT(v.empty());
+    }
+
+    void TestAt() {
+        using NPagedVector::TPagedVector;
+        TPagedVector<int, 3> v;
+        TPagedVector<int, 3> const& cv = v;
+
+        v.push_back(10);
+        UNIT_ASSERT(v.at(0) == 10);
+        v.at(0) = 20;
+        UNIT_ASSERT(cv.at(0) == 20);
+
+        for (;;) {
+            try {
+                v.at(1) = 20;
+                UNIT_ASSERT(false);
+            } catch (std::out_of_range const&) {
+                return;
+            } catch (...) {
+                UNIT_ASSERT(false);
+            }
+        }
+    }
+
+    void TestAutoRef() {
+        using NPagedVector::TPagedVector;
+        typedef TPagedVector<int, 3> TVec;
+        TVec ref;
+        for (int i = 0; i < 5; ++i) {
+            ref.push_back(i);
+        }
+
+        TPagedVector<TVec, 3> v_v_int;
+        v_v_int.push_back(ref);
+        v_v_int.push_back(v_v_int[0]);
+        v_v_int.push_back(ref);
+        v_v_int.push_back(v_v_int[0]);
+        v_v_int.push_back(v_v_int[0]);
+        v_v_int.push_back(ref);
+
+        TPagedVector<TVec, 3>::iterator vvit(v_v_int.begin()), vvitEnd(v_v_int.end());
+        for (; vvit != vvitEnd; ++vvit) {
+            UNIT_ASSERT(*vvit == ref);
+        }
+    }
+
+    struct Point {
+        int x, y;
+    };
+
+    struct PointEx: public Point {
+        PointEx()
+            : builtFromBase(false)
+        {
+        }
+        PointEx(const Point&)
+            : builtFromBase(true)
+        {
+        }
+
+        bool builtFromBase;
+    };
+
+    void TestIterators() {
+        using NPagedVector::TPagedVector;
+        TPagedVector<int, 3> vint;
+        vint.resize(10);
+        TPagedVector<int, 3> const& crvint = vint;
+
+        UNIT_ASSERT(vint.begin() == vint.begin());
+        UNIT_ASSERT(crvint.begin() == vint.begin());
+        UNIT_ASSERT(vint.begin() == crvint.begin());
+        UNIT_ASSERT(crvint.begin() == crvint.begin());
+
+        UNIT_ASSERT(vint.begin() != vint.end());
+        UNIT_ASSERT(crvint.begin() != vint.end());
+        UNIT_ASSERT(vint.begin() != crvint.end());
+        UNIT_ASSERT(crvint.begin() != crvint.end());
+
+        UNIT_ASSERT(vint.rbegin() == vint.rbegin());
+        // Not Standard:
+        //UNIT_ASSERT(vint.rbegin() == crvint.rbegin());
+        //UNIT_ASSERT(crvint.rbegin() == vint.rbegin());
+        UNIT_ASSERT(crvint.rbegin() == crvint.rbegin());
+
+        UNIT_ASSERT(vint.rbegin() != vint.rend());
+        // Not Standard:
+        //UNIT_ASSERT(vint.rbegin() != crvint.rend());
+        //UNIT_ASSERT(crvint.rbegin() != vint.rend());
+        UNIT_ASSERT(crvint.rbegin() != crvint.rend());
+    }
+
+    /* This test check a potential issue with empty base class
+         * optimization. Some compilers (VC6) do not implement it
+         * correctly resulting ina wrong behavior. */
+    void TestEbo() {
+        using NPagedVector::TPagedVector;
+        // We use heap memory as test failure can corrupt vector internal
+        // representation making executable crash on vector destructor invocation.
+        // We prefer a simple memory leak, internal corruption should be reveal
+        // by size or capacity checks.
+        typedef TPagedVector<int, 3> V;
+        V* pv1 = new V;
+
+        pv1->resize(1);
+        pv1->at(0) = 1;
+
+        V* pv2 = new V;
+
+        pv2->resize(10);
+        for (int i = 0; i < 10; ++i)
+            pv2->at(i) = 2;
+
+        pv1->swap(*pv2);
+
+        UNIT_ASSERT(pv1->size() == 10);
+        UNIT_ASSERT((*pv1)[5] == 2);
+
+        UNIT_ASSERT(pv2->size() == 1);
+        UNIT_ASSERT((*pv2)[0] == 1);
+
+        delete pv2;
+        delete pv1;
+    }
+};
+
+UNIT_TEST_SUITE_REGISTRATION(TPagedVectorTest);
diff --git a/library/cpp/containers/paged_vector/ut/ya.make b/library/cpp/containers/paged_vector/ut/ya.make
new file mode 100644
index 0000000000..74cfe5fb4a
--- /dev/null
+++ b/library/cpp/containers/paged_vector/ut/ya.make
@@ -0,0 +1,13 @@
+UNITTEST()
+
+OWNER(velavokr)
+
+PEERDIR(
+    library/cpp/containers/paged_vector
+)
+
+SRCS(
+    paged_vector_ut.cpp
+)
+
+END()
diff --git a/library/cpp/containers/paged_vector/ya.make b/library/cpp/containers/paged_vector/ya.make
new file mode 100644
index 0000000000..e14548bc2c
--- /dev/null
+++ b/library/cpp/containers/paged_vector/ya.make
@@ -0,0 +1,9 @@
+LIBRARY()
+
+OWNER(velavokr)
+
+SRCS(
+    paged_vector.cpp
+)
+
+END()