intermediate changes

ref:cde9a383711a11544ce7e107a78147fb96cc4029

7 files changed, 894 insertions, 0 deletions

diff --git a/library/cpp/iterator/ut/filtering_ut.cpp b/library/cpp/iterator/ut/filtering_ut.cpp
new file mode 100644
index 00000000000..60c20446988
--- /dev/null
+++ b/library/cpp/iterator/ut/filtering_ut.cpp
@@ -0,0 +1,41 @@
+#include <library/cpp/iterator/filtering.h>
+
+#include <library/cpp/testing/gtest/gtest.h>
+
+#include <util/generic/vector.h>
+
+using namespace testing;
+
+TEST(Filtering, TFilteringRangeTest) {
+    const TVector<int> x = {1, 2, 3, 4, 5};
+
+    EXPECT_THAT(
+        MakeFilteringRange(
+            x,
+            [](int x) { return x % 2 == 0; }
+        ),
+        ElementsAre(2, 4)
+    );
+}
+
+TEST(Filtering, TEmptyFilteringRangeTest) {
+    TVector<int> x = {1, 2, 3, 4, 5};
+    EXPECT_THAT(
+        MakeFilteringRange(
+            x,
+            [](int x) { return x > 100; }
+        ),
+        ElementsAre()
+    );
+}
+
+TEST(Filtering, TMutableFilteringRangeTest) {
+    TVector<int> x = {1, 2, 3, 4, 5};
+    for (auto& y : MakeFilteringRange(x, [](int x) { return x % 2 == 0; })) {
+        y = 7;
+    }
+    EXPECT_THAT(
+        x,
+        ElementsAre(1, 7, 3, 7, 5)
+    );
+}
diff --git a/library/cpp/iterator/ut/functools_ut.cpp b/library/cpp/iterator/ut/functools_ut.cpp
new file mode 100644
index 00000000000..2dee9a55c85
--- /dev/null
+++ b/library/cpp/iterator/ut/functools_ut.cpp
@@ -0,0 +1,603 @@
+#include <library/cpp/iterator/functools.h>
+
+#include <library/cpp/testing/gtest/gtest.h>
+
+#include <util/generic/vector.h>
+#include <util/generic/xrange.h>
+#include <util/generic/adaptor.h>
+
+#include <set>
+
+// default-win-x86_64-release compiler can't decompose tuple to structure binding (02.03.2019)
+#ifndef _WINDOWS
+#   define FOR_DISPATCH_2(i, j, r) \
+        for (auto [i, j] : r)
+#   define FOR_DISPATCH_3(i, j, k, r) \
+        for (auto [i, j, k] : r)
+#else
+#   define FOR_DISPATCH_2(i, j, r) \
+        for (auto __t_##i##_##j : r) \
+            if (auto& i = std::get<0>(__t_##i##_##j); true) \
+                if (auto& j = std::get<1>(__t_##i##_##j); true)
+#   define FOR_DISPATCH_3(i, j, k, r) \
+        for (auto __t_##i##_##j##_##k : r) \
+            if (auto& i = std::get<0>(__t_##i##_##j##_##k); true) \
+                if (auto& j = std::get<1>(__t_##i##_##j##_##k); true) \
+                    if (auto& k = std::get<2>(__t_##i##_##j##_##k); true)
+#endif
+
+using namespace NFuncTools;
+
+
+    template <typename TContainer>
+    auto ToVector(TContainer&& container) {
+        return std::vector{container.begin(), container.end()};
+    }
+
+    template <typename TContainerObjOrRef>
+    void TestViewCompileability(TContainerObjOrRef&& container) {
+        using TContainer = std::decay_t<TContainerObjOrRef>;
+        using TIterator = typename TContainer::iterator;
+
+        static_assert(std::is_same_v<decltype(container.begin()), TIterator>);
+
+        // iterator_traits must work!
+        using difference_type = typename std::iterator_traits<TIterator>::difference_type;
+        using value_type = typename std::iterator_traits<TIterator>::value_type;
+        using reference = typename std::iterator_traits<TIterator>::reference;
+        using pointer = typename std::iterator_traits<TIterator>::pointer;
+
+        {
+            // operator assignment
+            auto it = container.begin();
+            it = container.end();
+            it = std::move(container.begin());
+            // operator copying
+            auto it2 = it;
+            Y_UNUSED(it2);
+            auto it3 = std::move(it);
+            Y_UNUSED(it3);
+            Y_UNUSED(*it3);
+            EXPECT_TRUE(it3 == it3);
+            EXPECT_FALSE(it3 != it3);
+            // const TIterator
+            const auto it4 = it3;
+            Y_UNUSED(*it4);
+            EXPECT_TRUE(it4 == it4);
+            EXPECT_FALSE(it4 != it4);
+            EXPECT_TRUE(it3 == it4);
+            EXPECT_TRUE(it4 == it3);
+            EXPECT_FALSE(it3 != it4);
+            EXPECT_FALSE(it4 != it3);
+        }
+
+        auto it = container.begin();
+
+        // sanity check for types
+        using TConstReference = const std::remove_reference_t<reference>&;
+        TConstReference ref = *it;
+        Y_UNUSED(ref);
+        (void) static_cast<value_type>(*it);
+        (void) static_cast<difference_type>(1);
+        if constexpr (std::is_reference_v<decltype(*it)>) {
+            pointer ptr = &*it;
+            Y_UNUSED(ptr);
+        }
+
+        // std compatibility
+        ToVector(container);
+
+        // const iterators
+        [](const auto& cont) {
+            auto constBeginIterator = cont.begin();
+            auto constEndIterator = cont.end();
+            static_assert(std::is_same_v<decltype(constBeginIterator), typename TContainer::const_iterator>);
+            Y_UNUSED(constBeginIterator);
+            Y_UNUSED(constEndIterator);
+        }(container);
+    }
+
+    struct TTestSentinel {};
+    struct TTestIterator {
+        int operator*() {
+            return X;
+        }
+        void operator++() {
+            ++X;
+        }
+        bool operator!=(const TTestSentinel&) const {
+            return X < 3;
+        }
+
+        int X;
+    };
+
+    // container with minimal interface
+    auto MakeMinimalisticContainer() {
+        return MakeIteratorRange(TTestIterator{}, TTestSentinel{});
+    }
+
+
+    TEST(FuncTools, CompileRange) {
+        TestViewCompileability(Range(19));
+        TestViewCompileability(Range(10, 19));
+        TestViewCompileability(Range(10, 19, 2));
+    }
+
+
+    TEST(FuncTools, Enumerate) {
+        TVector<size_t> a = {1, 2, 4};
+        TVector<size_t> b;
+        TVector<size_t> c = {1};
+        for (auto& v : {a, b, c}) {
+            size_t j = 0;
+            FOR_DISPATCH_2(i, x, Enumerate(v)) {
+                EXPECT_EQ(v[i], x);
+                EXPECT_EQ(i, j++);
+                EXPECT_LT(i, v.size());
+            }
+            EXPECT_EQ(j, v.size());
+        }
+
+        TVector<size_t> d = {0, 0, 0};
+        FOR_DISPATCH_2(i, x, Enumerate(d)) {
+            x = i;
+        }
+        EXPECT_THAT(
+            d,
+            testing::ElementsAre(0u, 1u, 2u)
+        );
+    }
+
+    TEST(FuncTools, EnumerateTemporary) {
+        TVector<size_t> a = {1, 2, 4};
+        TVector<size_t> b;
+        TVector<size_t> c = {1};
+        for (auto& v : {a, b, c}) {
+            size_t j = 0;
+            FOR_DISPATCH_2(i, x, Enumerate(TVector(v))) {
+                EXPECT_EQ(v[i], x);
+                EXPECT_EQ(i, j++);
+                EXPECT_LT(i, v.size());
+            }
+            EXPECT_EQ(j, v.size());
+        }
+
+        FOR_DISPATCH_2(i, x, Enumerate(TVector<size_t>{1, 2, 3})) {
+            EXPECT_EQ(i + 1, x);
+        }
+    }
+
+    TEST(FuncTools, CompileEnumerate) {
+        auto container = std::vector{1, 2, 3};
+        TestViewCompileability(Enumerate(container));
+        const auto constContainer = std::vector{1, 2, 3};
+        TestViewCompileability(Enumerate(constContainer));
+        const int arrayContainer[] = {1, 2, 3};
+        TestViewCompileability(Enumerate(arrayContainer));
+
+        std::vector<std::pair<int, int>> res;
+        FOR_DISPATCH_2(i, x, Enumerate(MakeMinimalisticContainer())) {
+            res.push_back({i, x});
+        }
+        EXPECT_EQ(res, (std::vector<std::pair<int, int>>{
+            {0, 0}, {1, 1}, {2, 2},
+        }));
+    }
+
+    TEST(FuncTools, Zip) {
+        TVector<std::pair<TVector<size_t>, TVector<size_t>>> ts = {
+            {{1, 2, 3}, {4, 5, 6}},
+            {{1, 2, 3}, {4, 5, 6, 7}},
+            {{1, 2, 3, 4}, {4, 5, 6}},
+            {{1, 2, 3, 4}, {}},
+        };
+
+        FOR_DISPATCH_2(a, b, ts) {
+            size_t k = 0;
+            FOR_DISPATCH_2(i, j, Zip(a, b)) {
+                EXPECT_EQ(++k, i);
+                EXPECT_EQ(i + 3, j);
+            }
+            EXPECT_EQ(k, Min(a.size(), b.size()));
+        }
+    }
+
+    TEST(FuncTools, ZipReference) {
+        TVector a = {0, 1, 2};
+        TVector b = {2, 1, 0, -1};
+        FOR_DISPATCH_2(ai, bi, Zip(a, b)) {
+            ai = bi;
+        }
+        EXPECT_THAT(
+            a,
+            testing::ElementsAre(2u, 1u, 0u)
+        );
+    }
+
+    TEST(FuncTools, Zip3) {
+        TVector<std::tuple<TVector<i32>, TVector<i32>, TVector<i32>>> ts = {
+            {{1, 2, 3}, {4, 5, 6}, {11, 3}},
+            {{1, 2, 3}, {4, 5, 6, 7}, {9, 0}},
+            {{1, 2, 3, 4}, {9}, {4, 5, 6}},
+            {{1, 2, 3, 4}, {1}, {}},
+            {{}, {1}, {1, 2, 3, 4}},
+        };
+
+        FOR_DISPATCH_3(a, b, c, ts) {
+            TVector<std::tuple<i32, i32, i32>> e;
+            for (size_t j = 0; j < a.size() && j < b.size() && j < c.size(); ++j) {
+                e.push_back({a[j], b[j], c[j]});
+            }
+
+            TVector<std::tuple<i32, i32, i32>> f;
+            FOR_DISPATCH_3(ai, bi, ci, Zip(a, b, c)) {
+                f.push_back({ai, bi, ci});
+            }
+
+            EXPECT_EQ(e, f);
+        }
+    }
+
+    TEST(FuncTools, CompileZip) {
+        auto container = std::vector{1, 2, 3};
+        TestViewCompileability(Zip(container));
+        TestViewCompileability(Zip(container, container, container));
+        const auto constContainer = std::vector{1, 2, 3};
+        TestViewCompileability(Zip(constContainer, constContainer));
+        const int arrayContainer[] = {1, 2, 3};
+        TestViewCompileability(Zip(arrayContainer, arrayContainer));
+
+        std::vector<std::pair<int, int>> res;
+        FOR_DISPATCH_2(a, b, Zip(MakeMinimalisticContainer(), container)) {
+            res.push_back({a, b});
+        }
+        EXPECT_EQ(res, (std::vector<std::pair<int, int>>{
+            {0, 1}, {1, 2}, {2, 3},
+        }));
+    }
+
+    TEST(FuncTools, Filter) {
+        TVector<TVector<i32>> ts = {
+            {},
+            {1},
+            {2},
+            {1, 2},
+            {2, 1},
+            {1, 2, 3, 4, 5, 6, 7},
+        };
+
+        auto pred = [](i32 x) -> bool { return x & 1; };
+
+        for (auto& a : ts) {
+            TVector<i32> b;
+            for (i32 x : a) {
+                if (pred(x)) {
+                    b.push_back(x);
+                }
+            }
+
+            TVector<i32> c;
+            for (i32 x : Filter(pred, a)) {
+                c.push_back(x);
+            }
+
+            EXPECT_EQ(b, c);
+        }
+    }
+
+    TEST(FuncTools, CompileFilter) {
+        auto container = std::vector{1, 2, 3};
+        auto isOdd = [](int x) { return bool(x & 1); };
+        TestViewCompileability(Filter(isOdd, container));
+        const int arrayContainer[] = {1, 2, 3};
+        TestViewCompileability(Filter(isOdd, arrayContainer));
+    }
+
+    TEST(FuncTools, Map) {
+        TVector<TVector<i32>> ts = {
+            {},
+            {1},
+            {1, 2},
+            {1, 2, 3, 4, 5, 6, 7},
+        };
+
+        auto f = [](i32 x) { return x * x; };
+
+        for (auto& a : ts) {
+            TVector<i32> b;
+            for (i32 x : a) {
+                b.push_back(f(x));
+            }
+
+            TVector<i32> c;
+            for (i32 x : Map(f, a)) {
+                c.push_back(x);
+            }
+
+            EXPECT_EQ(b, c);
+        }
+
+        TVector floats = {1.4, 4.1, 13.9};
+        TVector ints = {1, 4, 13};
+        TVector<float> roundedFloats = {1, 4, 13};
+        TVector<int> res;
+        TVector<float> resFloat;
+        for (auto i : Map<int>(floats)) {
+            res.push_back(i);
+        }
+        for (auto i : Map<float>(Map<int>(floats))) {
+            resFloat.push_back(i);
+        }
+        EXPECT_EQ(ints, res);
+        EXPECT_EQ(roundedFloats, resFloat);
+    }
+
+    TEST(FuncTools, CompileMap) {
+        auto container = std::vector{1, 2, 3};
+        auto sqr = [](int x) { return x * x; };
+        TestViewCompileability(Map(sqr, container));
+        const int arrayContainer[] = {1, 2, 3};
+        TestViewCompileability(Map(sqr, arrayContainer));
+    }
+
+    TEST(FuncTools, MapRandomAccess) {
+        auto sqr = [](int x) { return x * x; };
+        {
+            auto container = std::vector{1, 2, 3};
+            auto mapped = Map(sqr, container);
+            static_assert(
+                std::is_same_v<decltype(mapped)::iterator::iterator_category, std::random_access_iterator_tag>
+            );
+        }
+        {
+            auto container = std::set<int>{1, 2, 3};
+            auto mapped = Map(sqr, container);
+            static_assert(
+                std::is_same_v<decltype(mapped)::iterator::iterator_category, std::input_iterator_tag>
+            );
+        }
+    }
+
+    TEST(FuncTools, CartesianProduct) {
+        TVector<std::pair<TVector<i32>, TVector<i32>>> ts = {
+            {{1, 2, 3}, {4, 5, 6}},
+            {{1, 2, 3}, {4, 5, 6, 7}},
+            {{1, 2, 3, 4}, {4, 5, 6}},
+            {{1, 2, 3, 4}, {}},
+            {{}, {1, 2, 3, 4}},
+        };
+
+        for (auto [a, b] : ts) {
+            TVector<std::pair<i32, i32>> c;
+            for (auto ai : a) {
+                for (auto bi : b) {
+                    c.push_back({ai, bi});
+                }
+            }
+
+            TVector<std::pair<i32, i32>> d;
+            FOR_DISPATCH_2(ai, bi, CartesianProduct(a, b)) {
+                d.push_back({ai, bi});
+            }
+
+            EXPECT_EQ(c, d);
+        }
+
+        {
+            TVector<TVector<int>> g = {{}, {}};
+            TVector h = {10, 11, 12};
+            FOR_DISPATCH_2(gi, i, CartesianProduct(g, h)) {
+                gi.push_back(i);
+            }
+            EXPECT_EQ(g[0], h);
+            EXPECT_EQ(g[1], h);
+        }
+    }
+
+    TEST(FuncTools, CartesianProduct3) {
+        TVector<std::tuple<TVector<i32>, TVector<i32>, TVector<i32>>> ts = {
+            {{1, 2, 3}, {4, 5, 6}, {11, 3}},
+            {{1, 2, 3}, {4, 5, 6, 7}, {9}},
+            {{1, 2, 3, 4}, {9}, {4, 5, 6}},
+            {{1, 2, 3, 4}, {1}, {}},
+            {{}, {1}, {1, 2, 3, 4}},
+        };
+
+        FOR_DISPATCH_3(a, b, c, ts) {
+            TVector<std::tuple<i32, i32, i32>> e;
+            for (auto ai : a) {
+                for (auto bi : b) {
+                    for (auto ci : c) {
+                        e.push_back({ai, bi, ci});
+                    }
+                }
+            }
+
+            TVector<std::tuple<i32, i32, i32>> f;
+            FOR_DISPATCH_3(ai, bi, ci, CartesianProduct(a, b, c)) {
+                f.push_back({ai, bi, ci});
+            }
+
+            EXPECT_EQ(e, f);
+        }
+    }
+
+    TEST(FuncTools, CompileCartesianProduct) {
+        auto container = std::vector{1, 2, 3};
+        TestViewCompileability(CartesianProduct(container, container));
+        const auto constContainer = std::vector{1, 2, 3};
+        TestViewCompileability(CartesianProduct(constContainer, constContainer));
+        const int arrayContainer[] = {1, 2, 3};
+        TestViewCompileability(CartesianProduct(arrayContainer, arrayContainer));
+
+        std::vector<std::pair<int, int>> res;
+        FOR_DISPATCH_2(a, b, CartesianProduct(MakeMinimalisticContainer(), MakeMinimalisticContainer())) {
+            res.push_back({a, b});
+        }
+        EXPECT_EQ(res, (std::vector<std::pair<int, int>>{
+            {0, 0}, {0, 1}, {0, 2},
+            {1, 0}, {1, 1}, {1, 2},
+            {2, 0}, {2, 1}, {2, 2},
+        }));
+    }
+
+    TEST(FuncTools, Concatenate2) {
+        TVector<std::pair<TVector<i32>, TVector<i32>>> ts = {
+            {{1, 2, 3}, {4, 5, 6}},
+            {{1, 2, 3}, {4, 5, 6, 7}},
+            {{1, 2, 3, 4}, {4, 5, 6}},
+            {{1, 2, 3, 4}, {}},
+            {{}, {1, 2, 3, 4}},
+        };
+
+        for (auto [a, b] : ts) {
+            TVector<i32> c;
+            for (auto ai : a) {
+                c.push_back(ai);
+            }
+            for (auto bi : b) {
+                c.push_back(bi);
+            }
+
+            TVector<i32> d;
+            for (auto x : Concatenate(a, b)) {
+                d.push_back(x);
+            }
+
+            EXPECT_EQ(c, d);
+        }
+
+        {
+            TVector<i32> a = {1, 2, 3, 4};
+            TVector<i32> c;
+            for (auto x : Concatenate(a, TVector<i32>{5, 6})) {
+                c.push_back(x);
+            }
+            EXPECT_EQ(c, (TVector<i32>{1, 2, 3, 4, 5, 6}));
+        }
+    }
+
+    TEST(FuncTools, CompileConcatenate) {
+        auto container = std::vector{1, 2, 3};
+        TestViewCompileability(Concatenate(container, container));
+        const auto constContainer = std::vector{1, 2, 3};
+        TestViewCompileability(Concatenate(constContainer, constContainer));
+        const int arrayContainer[] = {1, 2, 3};
+        TestViewCompileability(Concatenate(arrayContainer, arrayContainer));
+
+        std::vector<int> res;
+        for (auto a : Concatenate(MakeMinimalisticContainer(), MakeMinimalisticContainer())) {
+            res.push_back(a);
+        }
+        EXPECT_EQ(res, (std::vector{0, 1, 2, 0, 1, 2}));
+    }
+
+    TEST(FuncTools, Combo) {
+        FOR_DISPATCH_2(i, j, Enumerate(xrange(10u))) {
+            EXPECT_EQ(i, j);
+        }
+
+        FOR_DISPATCH_2(i, jk, Enumerate(Enumerate(xrange(10u)))) {
+            EXPECT_EQ(i, std::get<0>(jk));
+            EXPECT_EQ(std::get<0>(jk), std::get<1>(jk));
+        }
+
+        TVector<size_t> a = {0, 1, 2};
+        FOR_DISPATCH_2(i, j, Enumerate(Reversed(a))) {
+            EXPECT_EQ(i, 2 - j);
+        }
+
+        FOR_DISPATCH_2(i, j, Enumerate(Map<float>(a))) {
+            EXPECT_EQ(i, (size_t)j);
+        }
+
+        FOR_DISPATCH_2(i, j, Zip(a, Map<float>(a))) {
+            EXPECT_EQ(i, (size_t)j);
+        }
+
+        auto mapper = [](auto&& x) {
+            return std::get<0>(x) + std::get<1>(x);
+        };
+        FOR_DISPATCH_2(i, j, Zip(a, Map(mapper, Zip(a, a)))) {
+            EXPECT_EQ(j, 2 * i);
+        }
+    }
+
+
+    TEST(FuncTools, CopyIterator) {
+        TVector a = {1, 2, 3, 4};
+        TVector b = {4, 5, 6, 7};
+
+        // calls f on 2nd, 3d and 4th positions (numeration from 1st)
+        auto testIterator = [](auto it, auto f) {
+            ++it;
+            auto it2 = it;
+            ++it2;
+            ++it2;
+            auto it3 = it;
+            ++it3;
+            f(*it, *it3, *it2);
+        };
+
+        {
+            auto iterable = Enumerate(a);
+            testIterator(std::begin(iterable),
+                [](auto p2, auto p3, auto p4) {
+                    EXPECT_EQ(std::get<0>(p2), 1u);
+                    EXPECT_EQ(std::get<1>(p2), 2);
+                    EXPECT_EQ(std::get<0>(p3), 2u);
+                    EXPECT_EQ(std::get<1>(p3), 3);
+                    EXPECT_EQ(std::get<0>(p4), 3u);
+                    EXPECT_EQ(std::get<1>(p4), 4);
+                });
+        }
+
+        {
+            auto iterable = Map([](i32 x) { return x*x; }, a);
+            testIterator(std::begin(iterable),
+                [](auto p2, auto p3, auto p4) {
+                    EXPECT_EQ(p2, 4);
+                    EXPECT_EQ(p3, 9);
+                    EXPECT_EQ(p4, 16);
+                });
+        }
+
+        {
+            auto iterable = Zip(a, b);
+            testIterator(std::begin(iterable),
+                [](auto p2, auto p3, auto p4) {
+                    EXPECT_EQ(std::get<0>(p2), 2);
+                    EXPECT_EQ(std::get<1>(p2), 5);
+                    EXPECT_EQ(std::get<0>(p3), 3);
+                    EXPECT_EQ(std::get<1>(p3), 6);
+                    EXPECT_EQ(std::get<0>(p4), 4);
+                    EXPECT_EQ(std::get<1>(p4), 7);
+                });
+        }
+
+        {
+            auto c = {1, 2, 3, 4, 5, 6, 7, 8};
+            auto iterable = Filter([](i32 x) { return !(x & 1); }, c);
+            testIterator(std::begin(iterable),
+                [](auto p2, auto p3, auto p4) {
+                    EXPECT_EQ(p2, 4);
+                    EXPECT_EQ(p3, 6);
+                    EXPECT_EQ(p4, 8);
+                });
+        }
+
+        {
+            auto iterable = CartesianProduct(TVector{0, 1}, TVector{2, 3});
+            // (0, 2), (0, 3), (1, 2), (1, 3)
+            testIterator(std::begin(iterable),
+                [](auto p2, auto p3, auto p4) {
+                    EXPECT_EQ(std::get<0>(p2), 0);
+                    EXPECT_EQ(std::get<1>(p2), 3);
+                    EXPECT_EQ(std::get<0>(p3), 1);
+                    EXPECT_EQ(std::get<1>(p3), 2);
+                    EXPECT_EQ(std::get<0>(p4), 1);
+                    EXPECT_EQ(std::get<1>(p4), 3);
+                });
+        }
+    }
diff --git a/library/cpp/iterator/ut/iterate_keys_ut.cpp b/library/cpp/iterator/ut/iterate_keys_ut.cpp
new file mode 100644
index 00000000000..49eb866b6ec
--- /dev/null
+++ b/library/cpp/iterator/ut/iterate_keys_ut.cpp
@@ -0,0 +1,37 @@
+#include <library/cpp/iterator/iterate_keys.h>
+
+#include <library/cpp/testing/gtest/gtest.h>
+
+#include <map>
+
+using namespace testing;
+
+TEST(IterateKeys, ConstMappingIteration) {
+    const std::map<int, int> squares{
+        {1, 1},
+        {2, 4},
+        {3, 9},
+    };
+    EXPECT_THAT(
+        IterateKeys(squares),
+        ElementsAre(1, 2, 3)
+    );
+}
+
+TEST(IterateKeys, ConstMultiMappingIteration) {
+    const std::multimap<int, int> primesBelow{
+        {2, 2},
+        {5, 3},
+        {5, 5},
+        {11, 7},
+        {11, 11},
+        {23, 13},
+        {23, 17},
+        {23, 23},
+    };
+
+    EXPECT_THAT(
+        IterateKeys(primesBelow),
+        ElementsAre(2, 5, 5, 11, 11, 23, 23, 23)
+    );
+}
diff --git a/library/cpp/iterator/ut/iterate_values_ut.cpp b/library/cpp/iterator/ut/iterate_values_ut.cpp
new file mode 100644
index 00000000000..ed099e560d0
--- /dev/null
+++ b/library/cpp/iterator/ut/iterate_values_ut.cpp
@@ -0,0 +1,106 @@
+#include <library/cpp/iterator/iterate_values.h>
+
+#include <library/cpp/testing/gtest/gtest.h>
+
+#include <util/generic/algorithm.h>
+
+#include <map>
+#include <unordered_map>
+
+using namespace testing;
+
+TEST(IterateValues, ConstMappingIteration) {
+    const std::map<int, int> squares{
+        {1, 1},
+        {2, 4},
+        {3, 9},
+    };
+    EXPECT_THAT(
+        IterateValues(squares),
+        ElementsAre(1, 4, 9)
+    );
+
+    const std::unordered_map<int, int> roots{
+        {49, 7},
+        {36, 6},
+        {25, 5},
+    };
+    EXPECT_THAT(
+        IterateValues(roots),
+        UnorderedElementsAre(5, 6, 7)
+    );
+
+    const std::map<int, std::string> translations{
+        {1, "one"},
+        {2, "two"},
+        {3, "three"},
+    };
+    EXPECT_EQ(
+        Accumulate(IterateValues(translations), std::string{}),
+        "onetwothree"
+    );
+}
+
+TEST(IterateValues, NonConstMappingIteration) {
+    std::map<int, int> squares{
+        {1, 1},
+        {2, 4},
+        {3, 9},
+    };
+    for (auto& value: IterateValues(squares)) {
+        value *= value;
+    }
+    EXPECT_THAT(
+        IterateValues(squares),
+        ElementsAre(1, 16, 81)
+    );
+}
+
+TEST(IterateValues, ConstMultiMappingIteration) {
+    const std::multimap<int, int> primesBelow{
+        {2, 2},
+        {5, 3},
+        {5, 5},
+        {11, 7},
+        {11, 11},
+        {23, 13},
+        {23, 17},
+        {23, 23},
+    };
+
+    EXPECT_THAT(
+        IterateValues(primesBelow),
+        ElementsAre(2, 3, 5, 7, 11, 13, 17, 23)
+    );
+    auto [begin, end] = primesBelow.equal_range(11);
+    EXPECT_EQ(std::distance(begin, end), 2);
+    EXPECT_THAT(
+        IterateValues(std::vector(begin, end)),
+        ElementsAre(7, 11)
+    );
+}
+
+TEST(IterateValues, ConstUnorderedMultiMappingIteration) {
+    const std::unordered_multimap<int, int> primesBelow{
+        {2, 2},
+        {5, 3},
+        {5, 5},
+        {11, 7},
+        {11, 11},
+        {23, 13},
+        {23, 17},
+        {23, 23},
+    };
+
+    EXPECT_THAT(
+        IterateValues(primesBelow),
+        UnorderedElementsAre(2, 3, 5, 7, 11, 13, 17, 23)
+    );
+
+    auto [begin, end] = primesBelow.equal_range(11);
+    EXPECT_EQ(std::distance(begin, end), 2);
+    EXPECT_THAT(
+        IterateValues(std::vector(begin, end)),
+        UnorderedElementsAre(7, 11)
+    );
+}
diff --git a/library/cpp/iterator/ut/mapped_ut.cpp b/library/cpp/iterator/ut/mapped_ut.cpp
new file mode 100644
index 00000000000..440cd37945a
--- /dev/null
+++ b/library/cpp/iterator/ut/mapped_ut.cpp
@@ -0,0 +1,61 @@
+#include <library/cpp/iterator/mapped.h>
+
+#include <library/cpp/testing/gtest/gtest.h>
+
+#include <util/generic/map.h>
+#include <util/generic/vector.h>
+
+using namespace testing;
+
+TEST(TIterator, TMappedIteratorTest) {
+    TVector<int> x = {1, 2, 3, 4, 5};
+    auto it = MakeMappedIterator(x.begin(), [](int x) { return x + 7; });
+
+    EXPECT_EQ(*it, 8);
+    EXPECT_EQ(it[2], 10);
+}
+
+TEST(TIterator, TMappedRangeTest) {
+    TVector<int> x = {1, 2, 3, 4, 5};
+
+    EXPECT_THAT(
+        MakeMappedRange(
+            x,
+            [](int x) { return x + 3; }
+        ),
+        ElementsAre(4, 5, 6, 7, 8)
+    );
+}
+
+//TODO: replace with dedicated IterateKeys / IterateValues methods
+TEST(TIterator, TMutableMappedRangeTest) {
+    TMap<int, int> points = {{1, 2}, {3, 4}};
+
+    EXPECT_THAT(
+        MakeMappedRange(
+            points.begin(), points.end(),
+            [](TMap<int, int>::value_type& kv) -> int& { return kv.second; }
+        ),
+        ElementsAre(2, 4)
+    );
+}
+
+TEST(TIterator, TOwningMappedMethodTest) {
+    auto range = MakeMappedRange(
+        TVector<std::pair<int, int>>{std::make_pair(1, 2), std::make_pair(3, 4)},
+        [](auto& point) -> int& {
+            return point.first;
+        }
+    );
+    EXPECT_EQ(range[0], 1);
+    range[0] += 1;
+    EXPECT_EQ(range[0], 2);
+    (*range.begin()) += 1;
+    EXPECT_EQ(range[0], 3);
+    for (int& y : range) {
+        y += 7;
+    }
+
+    EXPECT_EQ(*range.begin(), 10);
+    EXPECT_EQ(*(range.begin() + 1), 10);
+}
diff --git a/library/cpp/iterator/ut/ya.make b/library/cpp/iterator/ut/ya.make
new file mode 100644
index 00000000000..601e5663b9f
--- /dev/null
+++ b/library/cpp/iterator/ut/ya.make
@@ -0,0 +1,18 @@
+GTEST()
+
+PEERDIR(
+    library/cpp/iterator
+)
+
+OWNER(g:util)
+
+SRCS(
+    filtering_ut.cpp
+    functools_ut.cpp
+    iterate_keys_ut.cpp
+    iterate_values_ut.cpp
+    mapped_ut.cpp
+    zip_ut.cpp
+)
+
+END()
diff --git a/library/cpp/iterator/ut/zip_ut.cpp b/library/cpp/iterator/ut/zip_ut.cpp
new file mode 100644
index 00000000000..68d496515c3
--- /dev/null
+++ b/library/cpp/iterator/ut/zip_ut.cpp
@@ -0,0 +1,28 @@
+#include <library/cpp/iterator/zip.h>
+
+#include <library/cpp/testing/gtest/gtest.h>
+
+#include <util/generic/vector.h>
+
+TEST(TIterator, ZipSimplePostIncrement) {
+    TVector<int> left{1, 2, 3};
+    TVector<int> right{4, 5, 6};
+
+    auto zipped = Zip(left, right);
+    auto cur = zipped.begin();
+    auto last = zipped.end();
+
+    {
+        auto first = *(cur++);
+        EXPECT_EQ(std::get<0>(first), 1);
+        EXPECT_EQ(std::get<1>(first), 4);
+    }
+    {
+        auto second = *(cur++);
+        EXPECT_EQ(std::get<0>(second), 2);
+        EXPECT_EQ(std::get<1>(second), 5);
+    }
+
+    EXPECT_EQ(std::next(cur), last);
+}
+