intermediate changes

ref:cde9a383711a11544ce7e107a78147fb96cc4029

27 files changed, 1861 insertions, 0 deletions

diff --git a/library/cpp/iterator/README.md b/library/cpp/iterator/README.md
new file mode 100644
index 0000000000..cd92a284c9
--- /dev/null
+++ b/library/cpp/iterator/README.md
@@ -0,0 +1,100 @@
+# Functools library
+
+Эта библиотека предоставляет функции `Enumerate`, `Zip`, `Map`, `Filter`, `Concatenate` и `CartesianProduct`.
+
+`Enumerate`, `Zip`, `Map`, `Filter` повторяют логику одноименных функций из python.
+
+Важный момент:
+ * Итераторы данных view почти во всех случаях (кроме Map, там зависит от маппера) возвращают `std::tuple` **по значению** (при этом шаблонные параметры всегда, когда это уместно, ссылки). 
+   <br> Так что нет никакого смысла делать `for (const auto& [i, x] : Enumerate(c))`. 
+   <br> Лучше всегда `for (auto [i, x] : Enumerate(c))` (`x` в этом случае будет ссылкой и работать с ним можно как со ссылкой) или `for (const auto [i, x] : Enumerate(c))`.
+
+Предоставляемые гарантии:
+ * Работа для всех контейнеров, для которых работает range-based for (для `Enumerate`, `Zip`, `Concatenate`, `CartesianProduct`).
+   Для `Map` и `Filter` есть требование на то, что первый и последний итераторы контейнера имеют один тип
+ * В том числе работает для обычных массивов (`int a[] = {1, 2, 3}; Enumerate(a)`).
+ * Поддержка rvalue для контейнеров, предикатов и функций-мапперов (`Filter([](auto x){...}, TVector{1, 2, 3})`).
+   В этом случае объекты сохраняются внутри view.
+ * Проброс элементов контейнеров по неконстантной ссылке
+ * `TView::iterator` - можно полагаться, что этот тип есть и корректен
+ * `TIterator::iterator_category` - можно полагаться, что этот тип есть и определен.
+
+
+На что гарантий нет:
+ * Любые изменения контейнеров, меняющие размер или инвалидирующие их итераторы, инвалидируют созданные view
+ * Не принимает списки инициализации (`Enumerate({1, 2, 3})`), так как неизвестен желаемый тип контейнера.
+ * В классах реализации оставлены публичные члены вида `.Field_`, чтобы не загромождать реализацию
+   Тем не менее эти поля не гарантированы, могут стать приватными или исчезнуть
+ * Для всех итераторов определены вложенные типы: `value_type`, `pointer`, `reference`.
+   Тем не менее не рекомендуется их использовать в связи с их неоднозначностью.
+   `value_type` может быть как обычным типом, так и ссылкой. Может быть `std::tuple<T1, T2>`,
+   а может `std::tuple<T1&, const T2&>`.
+   Если возникает необходимость в этих типах, то возможно, стоит упростить код и вообще не использовать эти view.
+   Если очень хочется можно использовать `delctype(*container.begin())`.
+
+
+Производительность:
+ * Бенчмарки времени компиляции и скорости выполнения, а так же сравнение с range-v3 и другими существующими реализациями
+   доступны в [репозитории где ведется разработка](https://github.com/yuri-pechatnov/cpp_functools/tree/master "functools").
+
+
+
+Q: Оверхед?
+A: По выполнению: на Enumerate, Zip, Map - нулевой. Где-то x1.5 на Filter, и x3 на Concatenate и CartesianProduct. Но если в теле цикла происходит хоть что-то существенное, то это пренебрежимо мало.
+   По компиляции: сложно рассчитать как оно скажется в реальном большом проекте, но приблизительно не более x1.5 на один цикл.
+
+Q: А зачем свой велосипед?
+A: ((https://pechatnov.at.yandex-team.ru/67 Ответ в этом посте)).
+
+Q: А почему вот здесь плохо написано, надо же по-другому?
+A: Код несколько раз переписывался и согласовывался ((https://st.yandex-team.ru/IGNIETFERRO-973 более полугода)). А допиливать его внутреннюю реализацию после коммита никто не мешает и дальше.
+
+
+Сигнатуры и эквиваленты:
+
+
+```cpp
+//! In all comments variables ending with '_'
+//! are considered as invisible for {...} block.
+
+//! Usage: for (auto [i, x] : Enumerate(container)) {...}
+//! Equivalent: { std::size_t i_ = 0; for (auto& x : container) { const std::size_t i = i_; {...}; ++i_; }}
+template <typename TContainerOrRef>
+auto Enumerate(TContainerOrRef&& container);
+
+//! Usage: for (auto x : Map(mapperFunc, container)) {...}
+//! Equivalent: for (auto iter_ = std::begin(container); iter_ != std::end(container); ++iter_) {
+//!                 auto x = mapperFunc(*iter_); {...}; }
+template <typename TMapper, typename TContainerOrRef>
+auto Map(TMapper&& mapper, TContainerOrRef&& container);
+
+//! Usage: for (auto x : Filter(predicate, container)) {...}
+//! Equivalent: for (auto x : container) { if (predicate(x)) {...}}
+template <typename TPredicate, typename TContainerOrRef>
+auto Filter(TPredicate&& predicate, TContainerOrRef&& container);
+
+//! Usage: for (auto [ai, bi] : Zip(a, b)) {...}
+//! Equivalent: { auto ia_ = std::begin(a); auto ib_ = std::begin(b);
+//!               for (; ia_ != std::end(a) && ib_ != std::end(b); ++ia_, ++ib_) {
+//!                   auto&& ai = *ia_; auto&& bi = *ib_; {...}
+//!               }}
+template <typename... TContainers>
+auto Zip(TContainers&&... containers);
+
+//! Usage: for (auto x : Reversed(container)) {...}
+//! Equivalent: for (auto iter_ = std::rbegin(container); iter_ != std::rend(container); ++iter_) {
+//!                 auto x = *iter_; {...}}
+template <typename TContainerOrRef>
+auto Reversed(TContainerOrRef&& container);
+
+//! Usage: for (auto x : Concatenate(a, b)) {...}
+//! Equivalent: { for (auto x : a) {...} for (auto x : b) {...} }
+//! (if there is no static variables in {...})
+template <typename TFirstContainer, typename... TContainers>
+auto Concatenate(TFirstContainer&& container, TContainers&&... containers);
+
+//! Usage: for (auto [ai, bi] : CartesianProduct(a, b)) {...}
+//! Equivalent: for (auto& ai : a) { for (auto& bi : b) {...} }
+template <typename... TContainers>
+auto CartesianProduct(TContainers&&... containers);
+```
diff --git a/library/cpp/iterator/cartesian_product.cpp b/library/cpp/iterator/cartesian_product.cpp
new file mode 100644
index 0000000000..c3ebfdcc33
--- /dev/null
+++ b/library/cpp/iterator/cartesian_product.cpp
@@ -0,0 +1 @@
+#include "cartesian_product.h"
diff --git a/library/cpp/iterator/cartesian_product.h b/library/cpp/iterator/cartesian_product.h
new file mode 100644
index 0000000000..3ef70339a2
--- /dev/null
+++ b/library/cpp/iterator/cartesian_product.h
@@ -0,0 +1,115 @@
+#pragma once
+
+#include <util/generic/store_policy.h>
+
+#include <tuple>
+
+
+namespace NPrivate {
+
+    template <typename... TContainers>
+    struct TCartesianMultiplier {
+        template <std::size_t... I>
+        struct TCartesianMultiplierWithIndex {
+        private:
+            using THolders = std::tuple<TAutoEmbedOrPtrPolicy<TContainers>...>;
+            using TValue = std::tuple<decltype(*std::begin(std::declval<TContainers&>()))...>;
+            using TIteratorState = std::tuple<int, decltype(std::begin(std::declval<TContainers&>()))...>;
+            using TSentinelState = std::tuple<int, decltype(std::end(std::declval<TContainers&>()))...>;
+
+            struct TIterator;
+            struct TSentinelCandidate {
+                TSentinelState Iterators_;
+                THolders* HoldersPtr_;
+            };
+            using TSentinel = std::conditional_t<std::is_same_v<TIteratorState, TSentinelState>,
+                                                 TIterator, TSentinelCandidate>;
+
+            struct TIterator {
+            private:
+                //! Return value is true when iteration is not finished
+                template <std::size_t position = sizeof...(TContainers)>
+                void IncrementIteratorsTuple() {
+                    auto& currentIterator = std::get<position>(Iterators_);
+                    ++currentIterator;
+
+                    if (currentIterator != std::end(*std::get<position - 1>(*HoldersPtr_).Ptr())) {
+                        return;
+                    } else {
+                        currentIterator = std::begin(*std::get<position - 1>(*HoldersPtr_).Ptr());
+                        if constexpr (position != 1) {
+                            IncrementIteratorsTuple<position - 1>();
+                        } else {
+                            std::get<0>(Iterators_) = 1;
+                        }
+                    }
+                }
+            public:
+                using difference_type = std::ptrdiff_t;
+                using value_type = TValue;
+                using pointer = TValue*;
+                using reference = TValue&;
+                using iterator_category = std::input_iterator_tag;
+
+                TValue operator*() {
+                    return {*std::get<I + 1>(Iterators_)...};
+                }
+                TValue operator*() const {
+                    return {*std::get<I + 1>(Iterators_)...};
+                }
+                void operator++() {
+                    IncrementIteratorsTuple();
+                }
+                bool operator!=(const TSentinel& other) const {
+                    // not finished iterator VS sentinel (most frequent case)
+                    if (std::get<0>(Iterators_) != std::get<0>(other.Iterators_)) {
+                        return true;
+                    }
+                    // do not compare sentinels and finished iterators
+                    if (std::get<0>(other.Iterators_)) {
+                        return false;
+                    }
+                    // compare not finished iterators
+                    return ((std::get<I + 1>(Iterators_) != std::get<I + 1>(other.Iterators_)) || ...);
+                }
+                bool operator==(const TSentinel& other) const {
+                    return !(*this != other);
+                }
+
+                TIteratorState Iterators_;
+                THolders* HoldersPtr_;
+            };
+        public:
+            using iterator = TIterator;
+            using const_iterator = TIterator;
+            using value_type = typename TIterator::value_type;
+            using reference = typename TIterator::reference;
+            using const_reference = typename TIterator::reference;
+
+            TIterator begin() const {
+                bool isEmpty = !((std::begin(*std::get<I>(Holders_).Ptr()) != std::end(*std::get<I>(Holders_).Ptr())) && ...);
+                return {TIteratorState{int(isEmpty), std::begin(*std::get<I>(Holders_).Ptr())...}, &Holders_};
+            }
+
+            TSentinel end() const {
+                return {TSentinelState{1, std::end(*std::get<I>(Holders_).Ptr())...}, &Holders_};
+            }
+
+            mutable THolders Holders_;
+        };
+
+        template <std::size_t... I>
+        static auto CartesianMultiply(TContainers&&... containers, std::index_sequence<I...>) {
+            return TCartesianMultiplierWithIndex<I...>{{std::forward<TContainers>(containers)...}};
+        }
+    };
+
+}
+
+//! Usage: for (auto [ai, bi] : CartesianProduct(a, b)) {...}
+//! Equivalent: for (auto& ai : a) { for (auto& bi : b) {...} }
+template <typename... TContainers>
+auto CartesianProduct(TContainers&&... containers) {
+    return NPrivate::TCartesianMultiplier<TContainers...>::CartesianMultiply(
+        std::forward<TContainers>(containers)..., std::make_index_sequence<sizeof...(TContainers)>{});
+}
diff --git a/library/cpp/iterator/concatenate.cpp b/library/cpp/iterator/concatenate.cpp
new file mode 100644
index 0000000000..4ca8e2e82d
--- /dev/null
+++ b/library/cpp/iterator/concatenate.cpp
@@ -0,0 +1 @@
+#include "concatenate.h"
diff --git a/library/cpp/iterator/concatenate.h b/library/cpp/iterator/concatenate.h
new file mode 100644
index 0000000000..64d2cd451a
--- /dev/null
+++ b/library/cpp/iterator/concatenate.h
@@ -0,0 +1,136 @@
+#pragma once
+
+#include <util/generic/store_policy.h>
+
+#include <iterator>
+#include <tuple>
+
+
+namespace NPrivate {
+
+    template <typename TValue_, typename... TContainers>
+    struct TConcatenator {
+        template <std::size_t... I>
+        struct TConcatenatorWithIndex {
+        private:
+            using THolders = std::tuple<TAutoEmbedOrPtrPolicy<TContainers>...>;
+            using TValue = TValue_;
+            using TIteratorState = std::tuple<decltype(std::begin(std::declval<TContainers&>()))...>;
+            using TSentinelState = std::tuple<decltype(std::end(std::declval<TContainers&>()))...>;
+
+            struct TIterator;
+            struct TSentinelCandidate {
+                TSentinelState Iterators_;
+                std::size_t Position_;
+                THolders* HoldersPtr_;
+            };
+            using TSentinel = std::conditional_t<std::is_same_v<TIteratorState, TSentinelState>,
+                                                 TIterator, TSentinelCandidate>;
+
+            struct TIterator {
+            private:
+                friend struct TConcatenatorWithIndex<I...>;
+
+                // important, that it is a static function, compiler better optimizes such code
+                template <std::size_t index = 0, typename TMaybeConstIteratorState>
+                static TValue GetCurrentValue(std::size_t position, TMaybeConstIteratorState& iterators) {
+                    if constexpr (index >= sizeof...(TContainers)) {
+                        // never happened when use of iterator is correct
+                        return *std::get<0>(iterators);
+                    } else {
+                        if (position == index) {
+                            return *std::get<index>(iterators);
+                        } else {
+                            return GetCurrentValue<index + 1>(position, iterators);
+                        }
+                    }
+                }
+
+                template <bool needIncrement, std::size_t index = 0>
+                void MaybeIncrementIteratorAndSkipExhaustedContainers() {
+                    if constexpr (index >= sizeof...(TContainers)) {
+                        return;
+                    } else {
+                        if (Position_ == index) {
+                            if constexpr (needIncrement) {
+                                ++std::get<index>(Iterators_);
+                            }
+                            if (!(std::get<index>(Iterators_) != std::end(*std::get<index>(*HoldersPtr_).Ptr()))) {
+                                ++Position_;
+                                MaybeIncrementIteratorAndSkipExhaustedContainers<false, index + 1>();
+                            }
+                        } else {
+                            MaybeIncrementIteratorAndSkipExhaustedContainers<needIncrement, index + 1>();
+                        }
+                    }
+                }
+            public:
+                using difference_type = std::ptrdiff_t;
+                using value_type = TValue;
+                using pointer = std::remove_reference_t<TValue>*;
+                using reference = std::remove_reference_t<TValue>&;
+                using iterator_category = std::input_iterator_tag;
+
+                TValue operator*() {
+                    return GetCurrentValue(Position_, Iterators_);
+                }
+                TValue operator*() const {
+                    return GetCurrentValue(Position_, Iterators_);
+                }
+                TIterator& operator++() {
+                    MaybeIncrementIteratorAndSkipExhaustedContainers<true>();
+                    return *this;
+                }
+                bool operator!=(const TSentinel& other) const {
+                    // give compiler an opportunity to optimize sentinel case (-70% of time)
+                    if (other.Position_ == sizeof...(TContainers)) {
+                        return Position_ < sizeof...(TContainers);
+                    } else {
+                        return (Position_ != other.Position_ ||
+                                ((std::get<I>(Iterators_) != std::get<I>(other.Iterators_)) || ...));
+                    }
+                }
+                bool operator==(const TSentinel& other) const {
+                    return !(*this != other);
+                }
+
+                TIteratorState Iterators_;
+                std::size_t Position_;
+                THolders* HoldersPtr_;
+            };
+        public:
+            using iterator = TIterator;
+            using const_iterator = TIterator;
+            using value_type = typename TIterator::value_type;
+            using reference = typename TIterator::reference;
+            using const_reference = typename TIterator::reference;
+
+            TIterator begin() const {
+                TIterator iterator{TIteratorState{std::begin(*std::get<I>(Holders_).Ptr())...}, 0, &Holders_};
+                iterator.template MaybeIncrementIteratorAndSkipExhaustedContainers<false>();
+                return iterator;
+            }
+
+            TSentinel end() const {
+                return {TSentinelState{std::end(*std::get<I>(Holders_).Ptr())...}, sizeof...(TContainers), &Holders_};
+            }
+
+            mutable THolders Holders_;
+        };
+
+        template <std::size_t... I>
+        static auto Concatenate(TContainers&&... containers, std::index_sequence<I...>) {
+            return TConcatenatorWithIndex<I...>{{std::forward<TContainers>(containers)...}};
+        }
+    };
+
+}
+
+
+//! Usage: for (auto x : Concatenate(a, b)) {...}
+template <typename TFirstContainer, typename... TContainers>
+auto Concatenate(TFirstContainer&& container, TContainers&&... containers) {
+    return NPrivate::TConcatenator<decltype(*std::begin(container)), TFirstContainer, TContainers...>::Concatenate(
+        std::forward<TFirstContainer>(container), std::forward<TContainers>(containers)...,
+        std::make_index_sequence<sizeof...(TContainers) + 1>{});
+}
diff --git a/library/cpp/iterator/enumerate.cpp b/library/cpp/iterator/enumerate.cpp
new file mode 100644
index 0000000000..b195f0b31d
--- /dev/null
+++ b/library/cpp/iterator/enumerate.cpp
@@ -0,0 +1 @@
+#include "enumerate.h"
diff --git a/library/cpp/iterator/enumerate.h b/library/cpp/iterator/enumerate.h
new file mode 100644
index 0000000000..2c83fb41bf
--- /dev/null
+++ b/library/cpp/iterator/enumerate.h
@@ -0,0 +1,82 @@
+#pragma once
+
+#include <util/generic/store_policy.h>
+
+#include <limits>
+#include <tuple>
+
+
+namespace NPrivate {
+
+    template <typename TContainer>
+    struct TEnumerator {
+    private:
+        using TStorage = TAutoEmbedOrPtrPolicy<TContainer>;
+        using TValue = std::tuple<const std::size_t, decltype(*std::begin(std::declval<TContainer&>()))>;
+        using TIteratorState = decltype(std::begin(std::declval<TContainer&>()));
+        using TSentinelState = decltype(std::end(std::declval<TContainer&>()));
+
+        static constexpr bool TrivialSentinel = std::is_same_v<TIteratorState, TSentinelState>;
+
+        struct TIterator;
+        struct TSentinelCandidate {
+            TSentinelState Iterator_;
+        };
+        using TSentinel = std::conditional_t<TrivialSentinel, TIterator, TSentinelCandidate>;
+
+        struct TIterator {
+            using difference_type = std::ptrdiff_t;
+            using value_type = TValue;
+            using pointer = TValue*;
+            using reference = TValue&;
+            using iterator_category = std::input_iterator_tag;
+
+            TValue operator*() {
+                return {Index_, *Iterator_};
+            }
+            TValue operator*() const {
+                return {Index_, *Iterator_};
+            }
+            void operator++() {
+                ++Index_;
+                ++Iterator_;
+            }
+            bool operator!=(const TSentinel& other) const {
+                return Iterator_ != other.Iterator_;
+            }
+            bool operator==(const TSentinel& other) const {
+                return Iterator_ == other.Iterator_;
+            }
+
+            std::size_t Index_;
+            TIteratorState Iterator_;
+        };
+    public:
+        using iterator = TIterator;
+        using const_iterator = TIterator;
+        using value_type = typename TIterator::value_type;
+        using reference = typename TIterator::reference;
+        using const_reference = typename TIterator::reference;
+
+        TIterator begin() const {
+            return {0, std::begin(*Storage_.Ptr())};
+        }
+
+        TSentinel end() const {
+            if constexpr (TrivialSentinel) {
+                return TIterator{std::numeric_limits<std::size_t>::max(), std::end(*Storage_.Ptr())};
+            } else {
+                return TSentinel{std::end(*Storage_.Ptr())};
+            }
+        }
+
+        mutable TStorage Storage_;
+    };
+
+}
+
+//! Usage: for (auto [i, x] : Enumerate(container)) {...}
+template <typename TContainerOrRef>
+auto Enumerate(TContainerOrRef&& container) {
+    return NPrivate::TEnumerator<TContainerOrRef>{std::forward<TContainerOrRef>(container)};
+}
diff --git a/library/cpp/iterator/filtering.cpp b/library/cpp/iterator/filtering.cpp
new file mode 100644
index 0000000000..8e1542f61b
--- /dev/null
+++ b/library/cpp/iterator/filtering.cpp
@@ -0,0 +1 @@
+#include "filtering.h"
diff --git a/library/cpp/iterator/filtering.h b/library/cpp/iterator/filtering.h
new file mode 100644
index 0000000000..c28e3bc6c4
--- /dev/null
+++ b/library/cpp/iterator/filtering.h
@@ -0,0 +1,102 @@
+#pragma once
+
+#include <util/generic/iterator_range.h>
+#include <util/generic/store_policy.h>
+#include <iterator>
+
+
+template <class TIterator, class TCondition>
+class TFilteringIterator {
+public:
+    using TSelf = TFilteringIterator<TIterator, TCondition>;
+
+    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;
+    using iterator_category = std::forward_iterator_tag;
+
+    TFilteringIterator(TIterator it, TIterator last, const TCondition& condition)
+        : Iter(it)
+        , Last(last)
+        , Condition(condition)
+    {
+        Grep();
+    }
+
+    TSelf& operator++() {
+        ++Iter;
+        Grep();
+        return *this;
+    }
+
+    decltype(auto) operator*() const {
+        return *Iter;
+    }
+
+    pointer operator->() const {
+        return &*Iter;
+    }
+
+    bool operator==(const TSelf& other) const {
+        return Iter == other.Iter;
+    }
+    bool operator!=(const TSelf& other) const {
+        return Iter != other.Iter;
+    }
+
+private:
+    void Grep() {
+        while (Iter != Last && !Condition(*Iter)) {
+            ++Iter;
+        }
+    }
+    TIterator Iter;
+    TIterator Last;
+    TCondition Condition;
+};
+
+
+template <class TContainer, class TCondition>
+class TFilteringRange {
+    using TContainerStorage = TAutoEmbedOrPtrPolicy<TContainer>;
+    using TConditionStorage = TAutoEmbedOrPtrPolicy<TCondition>;
+    using TRawIterator = decltype(std::begin(std::declval<TContainer&>()));
+    using TConditionWrapper = std::reference_wrapper<std::remove_reference_t<TCondition>>;
+public:
+    //TODO: make TIterator typedef private
+    using TIterator = TFilteringIterator<TRawIterator, TConditionWrapper>;
+
+    using iterator = TIterator;
+    using const_iterator = TIterator;
+    using value_type = typename TIterator::value_type;
+    using reference = typename TIterator::reference;
+
+    TFilteringRange(TContainer&& container, TCondition&& predicate)
+        : Container(std::forward<TContainer>(container))
+        , Condition(std::forward<TCondition>(predicate))
+    {}
+
+    TIterator begin() const {
+        return {std::begin(*Container.Ptr()), std::end(*Container.Ptr()), {*Condition.Ptr()}};
+    }
+
+    TIterator end() const {
+        return {std::end(*Container.Ptr()), std::end(*Container.Ptr()), {*Condition.Ptr()}};
+    }
+
+private:
+    mutable TContainerStorage Container;
+    mutable TConditionStorage Condition;
+};
+
+
+template <class TIterator, class TCondition>
+auto MakeFilteringRange(TIterator begin, TIterator end, const TCondition& condition) {
+    return MakeIteratorRange(TFilteringIterator<TIterator, TCondition>(begin, end, condition), TFilteringIterator<TIterator, TCondition>(end, end, condition));
+}
+
+template <class TContainer, class TCondition>
+auto MakeFilteringRange(TContainer&& container, TCondition&& condition) {
+    return TFilteringRange<TContainer, TCondition>(std::forward<TContainer>(container), std::forward<TCondition>(condition));
+}
diff --git a/library/cpp/iterator/functools.cpp b/library/cpp/iterator/functools.cpp
new file mode 100644
index 0000000000..da2d0757ce
--- /dev/null
+++ b/library/cpp/iterator/functools.cpp
@@ -0,0 +1 @@
+#include "functools.h"
diff --git a/library/cpp/iterator/functools.h b/library/cpp/iterator/functools.h
new file mode 100644
index 0000000000..57a0d66373
--- /dev/null
+++ b/library/cpp/iterator/functools.h
@@ -0,0 +1,57 @@
+#pragma once
+
+#include "cartesian_product.h"
+#include "concatenate.h"
+#include "enumerate.h"
+#include "filtering.h"
+#include "mapped.h"
+#include "zip.h"
+
+#include <util/generic/adaptor.h>
+#include <util/generic/xrange.h>
+
+#include <tuple>
+#include <algorithm>
+
+
+namespace NFuncTools {
+    using ::Enumerate;
+    using ::Reversed;
+    using ::Zip;
+    using ::Concatenate;
+    using ::CartesianProduct;
+
+    template <typename TValue>
+    auto Range(TValue from, TValue to, TValue step) {
+        return xrange(from, to, step);
+    }
+
+    template <typename TValue>
+    auto Range(TValue from, TValue to) {
+        return xrange(from, to);
+    }
+
+    template <typename TValue>
+    auto Range(TValue to) {
+        return xrange(to);
+    }
+
+    //! Usage: for (i32 x : Map([](i32 x) { return x * x; }, a)) {...}
+    template <typename TMapper, typename TContainerOrRef>
+    auto Map(TMapper&& mapper, TContainerOrRef&& container) {
+        return ::MakeMappedRange(std::forward<TContainerOrRef>(container), std::forward<TMapper>(mapper));
+    }
+
+    //! Usage: for (auto i : Map<int>(floats)) {...}
+    template <typename TMapResult, typename TContainerOrRef>
+    auto Map(TContainerOrRef&& container) {
+        return Map([](const auto& x) { return TMapResult(x); }, std::forward<TContainerOrRef>(container));
+    }
+
+    //! Usage: for (i32 x : Filter(predicate, container)) {...}
+    template <typename TPredicate, typename TContainerOrRef>
+    auto Filter(TPredicate&& predicate, TContainerOrRef&& container) {
+        return ::MakeFilteringRange(std::forward<TContainerOrRef>(container), std::forward<TPredicate>(predicate));
+    }
+
+}
diff --git a/library/cpp/iterator/iterate_keys.cpp b/library/cpp/iterator/iterate_keys.cpp
new file mode 100644
index 0000000000..6556d39af7
--- /dev/null
+++ b/library/cpp/iterator/iterate_keys.cpp
@@ -0,0 +1 @@
+#include "iterate_keys.h"
diff --git a/library/cpp/iterator/iterate_keys.h b/library/cpp/iterator/iterate_keys.h
new file mode 100644
index 0000000000..75362a6bd6
--- /dev/null
+++ b/library/cpp/iterator/iterate_keys.h
@@ -0,0 +1,13 @@
+#pragma once
+
+#include "mapped.h"
+
+template<typename TMapping>
+auto IterateKeys(TMapping&& map) {
+    return ::MakeMappedRange(
+        std::forward<TMapping>(map),
+        [](const auto& x) -> decltype((x.first)) {
+            return x.first;
+        }
+    );
+}
diff --git a/library/cpp/iterator/iterate_values.cpp b/library/cpp/iterator/iterate_values.cpp
new file mode 100644
index 0000000000..5607e58ecb
--- /dev/null
+++ b/library/cpp/iterator/iterate_values.cpp
@@ -0,0 +1 @@
+#include "iterate_values.h"
diff --git a/library/cpp/iterator/iterate_values.h b/library/cpp/iterator/iterate_values.h
new file mode 100644
index 0000000000..ac6f2f04ce
--- /dev/null
+++ b/library/cpp/iterator/iterate_values.h
@@ -0,0 +1,13 @@
+#pragma once
+
+#include "mapped.h"
+
+template<typename TMapping>
+auto IterateValues(TMapping&& map) {
+    return ::MakeMappedRange(
+        std::forward<TMapping>(map),
+        [](auto& x) -> decltype((x.second)) {
+            return x.second;
+        }
+    );
+}
diff --git a/library/cpp/iterator/mapped.cpp b/library/cpp/iterator/mapped.cpp
new file mode 100644
index 0000000000..047f38c58f
--- /dev/null
+++ b/library/cpp/iterator/mapped.cpp
@@ -0,0 +1 @@
+#include "mapped.h"
diff --git a/library/cpp/iterator/mapped.h b/library/cpp/iterator/mapped.h
new file mode 100644
index 0000000000..6c5e763184
--- /dev/null
+++ b/library/cpp/iterator/mapped.h
@@ -0,0 +1,193 @@
+#pragma once
+
+#include <util/generic/iterator_range.h>
+#include <util/generic/store_policy.h>
+
+#include <iterator>
+
+
+namespace NIteratorPrivate {
+    template <class TIterator>
+    constexpr bool HasRandomAccess() {
+        return std::is_same_v<typename std::iterator_traits<TIterator>::iterator_category,
+                              std::random_access_iterator_tag>;
+    }
+};
+
+
+template <class TIterator, class TMapper>
+class TMappedIterator {
+protected:
+    using TSelf = TMappedIterator<TIterator, TMapper>;
+    using TSrcPointerType = typename std::iterator_traits<TIterator>::reference;
+    using TValue = typename std::invoke_result_t<TMapper, TSrcPointerType>;
+public:
+    using difference_type = std::ptrdiff_t;
+    using value_type = TValue;
+    using reference = TValue&;
+    using pointer = std::remove_reference_t<TValue>*;
+    using iterator_category = std::conditional_t<NIteratorPrivate::HasRandomAccess<TIterator>(),
+        std::random_access_iterator_tag, std::input_iterator_tag>;
+
+    TMappedIterator(TIterator it, TMapper mapper)
+        : Iter(it)
+        , Mapper(std::move(mapper))
+    {
+    }
+
+    TSelf& operator++() {
+        ++Iter;
+        return *this;
+    }
+    TSelf& operator--() {
+        --Iter;
+        return *this;
+    }
+    TValue operator*() {
+        return Mapper((*Iter));
+    }
+    TValue operator*() const {
+        return Mapper((*Iter));
+    }
+
+    pointer operator->() const {
+        return &(Mapper((*Iter)));
+    }
+
+    TValue operator[](difference_type n) const {
+        return Mapper(*(Iter + n));
+    }
+    TSelf& operator+=(difference_type n) {
+        Iter += n;
+        return *this;
+    }
+    TSelf& operator-=(difference_type n) {
+        Iter -= n;
+        return *this;
+    }
+    TSelf operator+(difference_type n) const {
+        return TSelf(Iter + n, Mapper);
+    }
+    TSelf operator-(difference_type n) const {
+        return TSelf(Iter - n, Mapper);
+    }
+    difference_type operator-(const TSelf& other) const {
+        return Iter - other.Iter;
+    }
+    bool operator==(const TSelf& other) const {
+        return Iter == other.Iter;
+    }
+    bool operator!=(const TSelf& other) const {
+        return Iter != other.Iter;
+    }
+    bool operator>(const TSelf& other) const {
+        return Iter > other.Iter;
+    }
+    bool operator<(const TSelf& other) const {
+        return Iter < other.Iter;
+    }
+
+private:
+    TIterator Iter;
+    TMapper Mapper;
+};
+
+
+template <class TContainer, class TMapper>
+class TInputMappedRange {
+protected:
+    using TContainerStorage = TAutoEmbedOrPtrPolicy<TContainer>;
+    using TMapperStorage = TAutoEmbedOrPtrPolicy<TMapper>;
+    using TMapperWrapper = std::reference_wrapper<std::remove_reference_t<TMapper>>;
+    using TInternalIterator = decltype(std::begin(std::declval<TContainer&>()));
+    using TIterator = TMappedIterator<TInternalIterator, TMapperWrapper>;
+public:
+    using iterator = TIterator;
+    using const_iterator = TIterator;
+    using value_type = typename TIterator::value_type;
+    using reference = typename TIterator::reference;
+    using const_reference = typename TIterator::reference;
+
+    TInputMappedRange(TContainer&& container, TMapper&& mapper)
+        : Container(std::forward<TContainer>(container))
+        , Mapper(std::forward<TMapper>(mapper))
+    {
+    }
+
+    TIterator begin() const {
+        return {std::begin(*Container.Ptr()), {*Mapper.Ptr()}};
+    }
+
+    TIterator end() const {
+        return {std::end(*Container.Ptr()), {*Mapper.Ptr()}};
+    }
+
+    bool empty() const {
+        return std::begin(*Container.Ptr()) == std::end(*Container.Ptr());
+    }
+
+protected:
+    mutable TContainerStorage Container;
+    mutable TMapperStorage Mapper;
+};
+
+
+template <class TContainer, class TMapper>
+class TRandomAccessMappedRange : public TInputMappedRange<TContainer, TMapper> {
+    using TBase = TInputMappedRange<TContainer, TMapper>;
+    using TInternalIterator = typename TBase::TInternalIterator;
+    using TIterator = typename TBase::TIterator;
+public:
+    using iterator = typename TBase::iterator;
+    using const_iterator = typename TBase::const_iterator;
+    using value_type = typename TBase::value_type;
+    using reference = typename TBase::reference;
+    using const_reference = typename TBase::const_reference;
+
+    using difference_type = typename std::iterator_traits<iterator>::difference_type;
+    using size_type = std::size_t;
+
+    TRandomAccessMappedRange(TContainer&& container, TMapper&& mapper)
+        : TBase(std::forward<TContainer>(container), std::forward<TMapper>(mapper))
+    {
+    }
+
+    using TBase::begin;
+    using TBase::end;
+    using TBase::empty;
+
+    size_type size() const {
+        return std::end(*this->Container.Ptr()) - std::begin(*this->Container.Ptr());
+    }
+
+    const_reference operator[](size_t at) const {
+        Y_ASSERT(at < this->size());
+
+        return *(this->begin() + at);
+    }
+
+    reference operator[](size_t at) {
+        Y_ASSERT(at < this->size());
+
+        return *(this->begin() + at);
+    }
+};
+
+template <class TIterator, class TMapper>
+TMappedIterator<TIterator, TMapper> MakeMappedIterator(TIterator iter, TMapper mapper) {
+    return {iter, mapper};
+}
+
+template <class TIterator, class TMapper>
+auto MakeMappedRange(TIterator begin, TIterator end, TMapper mapper) {
+    return MakeIteratorRange(MakeMappedIterator(begin, mapper), MakeMappedIterator(end, mapper));
+}
+
+template <class TContainer, class TMapper>
+auto MakeMappedRange(TContainer&& container, TMapper&& mapper) {
+    if constexpr (NIteratorPrivate::HasRandomAccess<decltype(std::begin(container))>()) {
+        return TRandomAccessMappedRange<TContainer, TMapper>(std::forward<TContainer>(container), std::forward<TMapper>(mapper));
+    } else {
+        return TInputMappedRange<TContainer, TMapper>(std::forward<TContainer>(container), std::forward<TMapper>(mapper));
+    }
+}
diff --git a/library/cpp/iterator/ut/filtering_ut.cpp b/library/cpp/iterator/ut/filtering_ut.cpp
new file mode 100644
index 0000000000..60c2044698
--- /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 0000000000..2dee9a55c8
--- /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 0000000000..49eb866b6e
--- /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 0000000000..ed099e560d
--- /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 0000000000..440cd37945
--- /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 0000000000..601e5663b9
--- /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 0000000000..68d496515c
--- /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);
+}
+
diff --git a/library/cpp/iterator/ya.make b/library/cpp/iterator/ya.make
new file mode 100644
index 0000000000..1ba1ffb411
--- /dev/null
+++ b/library/cpp/iterator/ya.make
@@ -0,0 +1,19 @@
+OWNER(g:util)
+
+LIBRARY()
+
+SRCS(
+    cartesian_product.cpp
+    concatenate.cpp
+    enumerate.cpp
+    iterate_keys.cpp
+    iterate_values.cpp
+    filtering.cpp
+    functools.cpp
+    mapped.cpp
+    zip.cpp
+)
+
+END()
+
+RECURSE_FOR_TESTS(ut)
diff --git a/library/cpp/iterator/zip.cpp b/library/cpp/iterator/zip.cpp
new file mode 100644
index 0000000000..36338ea527
--- /dev/null
+++ b/library/cpp/iterator/zip.cpp
@@ -0,0 +1 @@
+#include "zip.h"
diff --git a/library/cpp/iterator/zip.h b/library/cpp/iterator/zip.h
new file mode 100644
index 0000000000..ac12ed35fe
--- /dev/null
+++ b/library/cpp/iterator/zip.h
@@ -0,0 +1,128 @@
+#pragma once
+
+#include <util/generic/store_policy.h>
+
+#include <algorithm>
+#include <tuple>
+
+
+namespace NPrivate {
+
+    template <typename TContainer, typename TIteratorCategory = typename std::iterator_traits<decltype(std::begin(std::declval<TContainer>()))>::iterator_category>
+    static constexpr bool HasRandomAccessIterator(int32_t) {
+        return std::is_same_v<TIteratorCategory, std::random_access_iterator_tag>;
+    }
+
+    template <typename TContainer>
+    static constexpr bool HasRandomAccessIterator(uint32_t) {
+        return false;
+    }
+
+    template <typename... TContainers>
+    struct TZipper {
+        template <std::size_t... I>
+        struct TZipperWithIndex {
+        private:
+            using THolders = std::tuple<TAutoEmbedOrPtrPolicy<TContainers>...>;
+            using TValue = std::tuple<decltype(*std::begin(std::declval<TContainers&>()))...>;
+            using TIteratorState = std::tuple<decltype(std::begin(std::declval<TContainers&>()))...>;
+            using TSentinelState = std::tuple<decltype(std::end(std::declval<TContainers&>()))...>;
+
+            static constexpr bool TrivialSentinel = std::is_same_v<TIteratorState, TSentinelState>;
+
+            struct TIterator;
+            struct TSentinelCandidate {
+                TSentinelState Iterators_;
+            };
+            using TSentinel = std::conditional_t<TrivialSentinel, TIterator, TSentinelCandidate>;
+
+#ifndef _MSC_VER
+            // windows compiler crashes here
+            static constexpr bool LimitByFirstContainer = TrivialSentinel &&
+                ((HasRandomAccessIterator<TContainers>(0)) && ...);
+#else
+            static constexpr bool LimitByFirstContainer = false;
+#endif
+
+            struct TIterator {
+                using difference_type = std::ptrdiff_t;
+                using value_type = TValue;
+                using pointer = TValue*;
+                using reference = TValue&;
+                using const_reference = const TValue&;
+                using iterator_category = std::input_iterator_tag;
+
+                TValue operator*() {
+                    return {*std::get<I>(Iterators_)...};
+                }
+                TValue operator*() const {
+                    return {*std::get<I>(Iterators_)...};
+                }
+
+                TIterator& operator++() {
+                    (++std::get<I>(Iterators_), ...);
+                    return *this;
+                }
+
+                TIterator operator++(int) {
+                    return TIterator{TIteratorState{std::get<I>(Iterators_)++...}};
+                }
+
+                bool operator!=(const TSentinel& other) const {
+                    if constexpr (LimitByFirstContainer) {
+                        return std::get<0>(Iterators_) != std::get<0>(other.Iterators_);
+                    } else {
+                        // yes, for all correct iterators but end() it is a correct way to compare
+                        return ((std::get<I>(Iterators_) != std::get<I>(other.Iterators_)) && ...);
+                    }
+                }
+                bool operator==(const TSentinel& other) const {
+                    return !(*this != other);
+                }
+
+                TIteratorState Iterators_;
+            };
+        public:
+            using iterator = TIterator;
+            using const_iterator = TIterator;
+            using value_type = typename TIterator::value_type;
+            using reference = typename TIterator::reference;
+            using const_reference = typename TIterator::const_reference;
+
+            TIterator begin() const {
+                return {TIteratorState{std::begin(*std::get<I>(Holders_).Ptr())...}};
+            }
+
+            TSentinel end() const {
+                if constexpr (LimitByFirstContainer) {
+                    auto endOfFirst = std::begin(*std::get<0>(Holders_).Ptr()) + std::min({
+                        std::end(*std::get<I>(Holders_).Ptr()) - std::begin(*std::get<I>(Holders_).Ptr())...});
+                    TIterator iter{TSentinelState{std::end(*std::get<I>(Holders_).Ptr())...}};
+                    std::get<0>(iter.Iterators_) = endOfFirst;
+                    return iter;
+                } else {
+                    return {TSentinelState{std::end(*std::get<I>(Holders_).Ptr())...}};
+                }
+            }
+
+            mutable THolders Holders_;
+        };
+
+        template <std::size_t... I>
+        static auto Zip(TContainers&&... containers, std::index_sequence<I...>) {
+            return TZipperWithIndex<I...>{{std::forward<TContainers>(containers)...}};
+        }
+    };
+
+}
+
+
+//! Acts as pythonic zip, BUT result length is equal to shortest length of input containers
+//! Usage: for (auto [ai, bi, ci] : Zip(a, b, c)) {...}
+template <typename... TContainers>
+auto Zip(TContainers&&... containers) {
+    return ::NPrivate::TZipper<TContainers...>::Zip(
+        std::forward<TContainers>(containers)...,
+        std::make_index_sequence<sizeof...(TContainers)>{}
+    );
+}