Intermediate changes

commit_hash:5fdfb1b57fedb283f7f984c453a704df0f08ebd4

1 files changed, 118 insertions, 76 deletions

diff --git a/library/cpp/containers/ordered_map/ordered_map.h b/library/cpp/containers/ordered_map/ordered_map.h
index f2d1a47c095..b218c917f57 100644
--- a/library/cpp/containers/ordered_map/ordered_map.h
+++ b/library/cpp/containers/ordered_map/ordered_map.h
@@ -5,25 +5,30 @@
 
 #include <functional>
 #include <utility>
+#include <list>
 
 
 namespace NOrderedMap {
-    template <class TKey, class TValue>
-    class TOrderedMap : protected TVector<std::pair<const TKey, TValue>> {
-        using TVectorBase = TVector<std::pair<const TKey, TValue>>;
+    template <class TKey, class TValue, class BaseToUse = std::list<std::pair<const TKey, TValue>>> //bases: deque or list
+    class TOrderedMap : protected BaseToUse {
+        using TBase = BaseToUse;
 
     public:
-        using typename TVectorBase::const_iterator;
-        using typename TVectorBase::iterator;
-        using typename TVectorBase::reference;
-        using typename TVectorBase::value_type;
-        using TVectorBase::size;
-        using TVectorBase::empty;
-        using TVectorBase::front;
-        using TVectorBase::back;
-        using TVectorBase::begin;
-        using TVectorBase::end;
-        using TVectorBase::operator bool;
+        using typename TBase::const_iterator;
+        using typename TBase::iterator;
+        using typename TBase::reference;
+        using typename TBase::value_type;
+        using TBase::size;
+        using TBase::empty;
+        using TBase::front;
+        using TBase::back;
+        using TBase::begin;
+        using TBase::end;
+        using TBase::rbegin;
+        using TBase::rend;
+        operator bool() const {
+            return empty();
+        }
 
         TOrderedMap() = default;
 
@@ -32,7 +37,7 @@ namespace NOrderedMap {
                 emplace_back(item.first, item.second);
             }
         }
-        TOrderedMap(TOrderedMap&& other) noexcept : TVectorBase(std::move(other)), Map_(std::move(other.Map_)) {
+        TOrderedMap(TOrderedMap&& other) noexcept : TBase(std::move(other)), Map_(std::move(other.Map_)) {
             other.Map_.clear();
         }
         TOrderedMap& operator=(const TOrderedMap& other) {
@@ -46,7 +51,7 @@ namespace NOrderedMap {
         }
         TOrderedMap& operator=(TOrderedMap&& other) noexcept {
             if (this != &other) {
-                TVectorBase::operator=(std::move(other));
+                TBase::operator=(std::move(other));
                 Map_ = std::move(other.Map_);
                 other.Map_.clear();
             }
@@ -55,46 +60,32 @@ namespace NOrderedMap {
 
         template <class TheKey>
         TValue& operator[](const TheKey& key) {
-            auto [mapIt, inserted] = Map_.try_emplace(key, TVectorBase::size());
-            if (inserted) {
-                TVectorBase::emplace_back(key, TValue{});
-            }
-            return TVectorBase::at(mapIt->second).second;
-        }
-
-        template <class TheKey>
-        const TValue& at(const TheKey& key) const {
-            return TVectorBase::at(Map_.at(key)).second;
-        }
-
-        template <class TheKey>
-        TValue& at(const TheKey& key) {
-            return TVectorBase::at(Map_.at(key)).second;
+            return try_emplace_back(key, TValue{}).second;
         }
 
         template <class TheKey>
         const_iterator find(const TheKey& key) const {
-            auto mapIt = Map_.find(key);
+            auto mapIt = Map_.find(&key);
             if (mapIt == Map_.end()) {
                 return end();
             } else {
-                return begin() + mapIt->second;
+                return mapIt->second;
             }
         }
 
         template <class TheKey>
         iterator find(const TheKey& key) {
-            auto mapIt = Map_.find(key);
+            auto mapIt = Map_.find(&key);
             if (mapIt == Map_.end()) {
                 return end();
             } else {
-                return begin() + mapIt->second;
+                return mapIt->second;
             }
         }
 
         template <class TheKey>
         bool contains(const TheKey& key) const {
-            return Map_.contains(key);
+            return Map_.contains(&key);
         }
 
         void push_back(const value_type& x) {
@@ -107,72 +98,123 @@ namespace NOrderedMap {
 
         template <class... TArgs>
         reference emplace_back(TArgs&&... args) {
-            auto pos = size();
-            auto& value = TVectorBase::emplace_back(std::forward<TArgs>(args)...);
-            auto [mapIt, ok] = Map_.try_emplace(value.first, pos);
-            if (ok) {
-                return value;
+            auto& value = TBase::emplace_back(std::forward<TArgs>(args)...);
+            auto [mapIt, ok] = Map_.try_emplace(&value.first, --TBase::end());
+            if (!ok) {
+                iterator forDeleteFromList = mapIt->second;
+                //TODO: it is possible to skip double-lookup if be possible to mutate key by iterator, or steal previous value by insert
+                Map_.erase(mapIt);
+                TBase::erase(forDeleteFromList);
+                bool isOk = Map_.try_emplace(&value.first, --TBase::end()).second;
+                Y_ASSERT(isOk);
             }
-            TVectorBase::pop_back();
-            return TVectorBase::at(mapIt->second);
+            return value;
         }
 
-                template <class TheKey>
-        size_t erase(const TheKey& key) {
-            auto it = find(key);
-            if (it == end()) {
-                return 0;
+        template <class... TArgs>
+        reference try_emplace_back(TArgs&&... args) {
+            auto& value = TBase::emplace_back(std::forward<TArgs>(args)...);
+            auto [mapIt, ok] = Map_.try_emplace(&value.first, --TBase::end());
+            if (!ok) {
+                TBase::pop_back();
+                return *mapIt->second;
             }
-            erase(it);
-            return 1;
+            return value;
         }
-        void erase(iterator it) {
-            if (it == end()) {
-                return;
-            }
-            Map_.clear();
-            TVector<std::pair<const TKey, TValue>> tmp;
-            for (auto iter = begin(); iter != end(); ++iter) {
-                if (iter != it) {
-                    Map_[iter->first] = tmp.size();
-                    tmp.emplace_back(std::move(*iter));
+
+        reference at(size_t i) {
+            Y_ENSURE(i < size());
+            using category = typename std::iterator_traits<iterator>::iterator_category;
+            if constexpr (std::is_same_v<category, std::random_access_iterator_tag>) {
+                return (TBase::begin() + i)->second;
+            } else {
+                auto iter = TBase::begin();
+                for(size_t j = 0; j < i && iter != TBase::end(); ++j) {
+                    ++iter;
                 }
+                return iter->second;
             }
-            TVectorBase::operator=(std::move(tmp));
+        }
+
+        template <class TheKey>
+        const TValue& at(const TheKey& key) const {
+            return Map_.at(&key)->second;
+        }
+
+        template <class TheKey>
+        TValue& at(const TheKey& key) {
+            return Map_.at(&key)->second;
+        }
+
+        template <class TheKey>
+        auto erase(const TheKey& key) {
+            auto mapIt = Map_.find(&key);
+            if (mapIt == Map_.end()) {
+                return end();
+            }
+            auto forDelete = mapIt->second;
+            Map_.erase(mapIt);
+            auto res = TBase::erase(forDelete);
+            return res;
+        }
+
+        iterator erase(iterator it) {
+            if (it == end()) {
+                return end();
+            }
+            Map_.erase(&it->first);
+            return TBase::erase(it);
         }
 
         void Sort() {
-            TVector<std::pair<TKey, TValue>> tmp(begin(), end());
-            TVectorBase::clear();
+            TVector<std::pair<TKey, TValue>> tmp(Reserve(size()));
+            for(auto& x : *this) {
+                tmp.emplace_back(std::move(x));
+            }
+            clear();
             std::ranges::sort(tmp, {}, &std::pair<TKey, TValue>::first);
-            for (auto&& [k, v] : std::move(tmp)) {
-                Map_[k] = size();
-                TVectorBase::emplace_back(std::move(k), std::move(v));
+            for (auto&& x : std::move(tmp)) {
+                emplace_back(std::move(x));
             }
         }
 
         template <class TheKey>
         const TValue* FindPtr(const TheKey& key) const {
-            auto mapIt = Map_.find(key);
-            return mapIt != Map_.end()
-                ? &TVectorBase::at(mapIt->second).second
-                : nullptr;
+            auto mapIt = Map_.find(&key);
+            return mapIt == Map_.end()
+                ? nullptr
+                : &mapIt->second->second;
         }
 
         template <class TheKey>
         TValue* FindPtr(const TheKey& key) {
-            auto mapIt = Map_.find(key);
-            return mapIt != Map_.end()
-                ? &TVectorBase::at(mapIt->second).second
-                : nullptr;
+            auto mapIt = Map_.find(&key);
+            return mapIt == Map_.end()
+                ? nullptr
+                : &mapIt->second->second;
         }
 
         void clear() noexcept {
-            TVectorBase::clear();
+            TBase::clear();
             Map_.clear();
         }
 
     private:
-        THashMap<TKey, size_t> Map_{};
+        struct THashOperationsForPtr : public THash<TKey>, public TEqualTo<TKey> {
+            using THashBase = THash<TKey>;
+            using TEqualBase = TEqualTo<TKey>;
+            template<class TKeyTransparency>
+            inline size_t operator()(const TKeyTransparency* ptr) const noexcept {
+                Y_DEBUG_ABORT_UNLESS(ptr);
+                return this->THashBase::operator()(*ptr);
+            }
+            template<class TKeyTransparencyA, class TKeyTransparencyB>
+            inline bool operator()(const TKeyTransparencyA* a, const TKeyTransparencyB* b) const noexcept {
+                Y_DEBUG_ABORT_UNLESS(a);
+                Y_DEBUG_ABORT_UNLESS(b);
+                return this->TEqualBase::operator()(*a, *b);
+            }
+        };
+        THashMap<const TKey*, typename TBase::iterator, THashOperationsForPtr, THashOperationsForPtr> Map_{};
     };
 }