container/internal/raw_hash_map.h

0001 // Copyright 2018 The Abseil Authors.
0002 //
0003 // Licensed under the Apache License, Version 2.0 (the "License");
0004 // you may not use this file except in compliance with the License.
0005 // You may obtain a copy of the License at
0006 //
0007 //      https://www.apache.org/licenses/LICENSE-2.0
0008 //
0009 // Unless required by applicable law or agreed to in writing, software
0010 // distributed under the License is distributed on an "AS IS" BASIS,
0011 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0012 // See the License for the specific language governing permissions and
0013 // limitations under the License.
0014
0015 #ifndef ABSL_CONTAINER_INTERNAL_RAW_HASH_MAP_H_
0016 #define ABSL_CONTAINER_INTERNAL_RAW_HASH_MAP_H_
0017
0018 #include <tuple>
0019 #include <type_traits>
0020 #include <utility>
0021
0022 #include "absl/base/attributes.h"
0023 #include "absl/base/config.h"
0024 #include "absl/base/internal/throw_delegate.h"
0025 #include "absl/container/internal/container_memory.h"
0026 #include "absl/container/internal/raw_hash_set.h"  // IWYU pragma: export
0027
0028 namespace absl {
0029 ABSL_NAMESPACE_BEGIN
0030 namespace container_internal {
0031
0032 template <class Policy, class Hash, class Eq, class Alloc>
0033 class raw_hash_map : public raw_hash_set<Policy, Hash, Eq, Alloc> {
0034   // P is Policy. It's passed as a template argument to support maps that have
0035   // incomplete types as values, as in unordered_map<K, IncompleteType>.
0036   // MappedReference<> may be a non-reference type.
0037   template <class P>
0038   using MappedReference = decltype(P::value(
0039       std::addressof(std::declval<typename raw_hash_map::reference>())));
0040
0041   // MappedConstReference<> may be a non-reference type.
0042   template <class P>
0043   using MappedConstReference = decltype(P::value(
0044       std::addressof(std::declval<typename raw_hash_map::const_reference>())));
0045
0046   using KeyArgImpl =
0047       KeyArg<IsTransparent<Eq>::value && IsTransparent<Hash>::value>;
0048
0049  public:
0050   using key_type = typename Policy::key_type;
0051   using mapped_type = typename Policy::mapped_type;
0052   template <class K>
0053   using key_arg = typename KeyArgImpl::template type<K, key_type>;
0054
0055   static_assert(!std::is_reference<key_type>::value, "");
0056
0057   // TODO(b/187807849): Evaluate whether to support reference mapped_type and
0058   // remove this assertion if/when it is supported.
0059   static_assert(!std::is_reference<mapped_type>::value, "");
0060
0061   using iterator = typename raw_hash_map::raw_hash_set::iterator;
0062   using const_iterator = typename raw_hash_map::raw_hash_set::const_iterator;
0063
0064   raw_hash_map() {}
0065   using raw_hash_map::raw_hash_set::raw_hash_set;
0066
0067   // The last two template parameters ensure that both arguments are rvalues
0068   // (lvalue arguments are handled by the overloads below). This is necessary
0069   // for supporting bitfield arguments.
0070   //
0071   //   union { int n : 1; };
0072   //   flat_hash_map<int, int> m;
0073   //   m.insert_or_assign(n, n);
0074   template <class K = key_type, class V = mapped_type, K* = nullptr,
0075             V* = nullptr>
0076   std::pair<iterator, bool> insert_or_assign(key_arg<K>&& k, V&& v)
0077       ABSL_ATTRIBUTE_LIFETIME_BOUND {
0078     return insert_or_assign_impl(std::forward<K>(k), std::forward<V>(v));
0079   }
0080
0081   template <class K = key_type, class V = mapped_type, K* = nullptr>
0082   std::pair<iterator, bool> insert_or_assign(key_arg<K>&& k, const V& v)
0083       ABSL_ATTRIBUTE_LIFETIME_BOUND {
0084     return insert_or_assign_impl(std::forward<K>(k), v);
0085   }
0086
0087   template <class K = key_type, class V = mapped_type, V* = nullptr>
0088   std::pair<iterator, bool> insert_or_assign(const key_arg<K>& k, V&& v)
0089       ABSL_ATTRIBUTE_LIFETIME_BOUND {
0090     return insert_or_assign_impl(k, std::forward<V>(v));
0091   }
0092
0093   template <class K = key_type, class V = mapped_type>
0094   std::pair<iterator, bool> insert_or_assign(const key_arg<K>& k, const V& v)
0095       ABSL_ATTRIBUTE_LIFETIME_BOUND {
0096     return insert_or_assign_impl(k, v);
0097   }
0098
0099   template <class K = key_type, class V = mapped_type, K* = nullptr,
0100             V* = nullptr>
0101   iterator insert_or_assign(const_iterator, key_arg<K>&& k,
0102                             V&& v) ABSL_ATTRIBUTE_LIFETIME_BOUND {
0103     return insert_or_assign(std::forward<K>(k), std::forward<V>(v)).first;
0104   }
0105
0106   template <class K = key_type, class V = mapped_type, K* = nullptr>
0107   iterator insert_or_assign(const_iterator, key_arg<K>&& k,
0108                             const V& v) ABSL_ATTRIBUTE_LIFETIME_BOUND {
0109     return insert_or_assign(std::forward<K>(k), v).first;
0110   }
0111
0112   template <class K = key_type, class V = mapped_type, V* = nullptr>
0113   iterator insert_or_assign(const_iterator, const key_arg<K>& k,
0114                             V&& v) ABSL_ATTRIBUTE_LIFETIME_BOUND {
0115     return insert_or_assign(k, std::forward<V>(v)).first;
0116   }
0117
0118   template <class K = key_type, class V = mapped_type>
0119   iterator insert_or_assign(const_iterator, const key_arg<K>& k,
0120                             const V& v) ABSL_ATTRIBUTE_LIFETIME_BOUND {
0121     return insert_or_assign(k, v).first;
0122   }
0123
0124   // All `try_emplace()` overloads make the same guarantees regarding rvalue
0125   // arguments as `std::unordered_map::try_emplace()`, namely that these
0126   // functions will not move from rvalue arguments if insertions do not happen.
0127   template <class K = key_type, class... Args,
0128             typename std::enable_if<
0129                 !std::is_convertible<K, const_iterator>::value, int>::type = 0,
0130             K* = nullptr>
0131   std::pair<iterator, bool> try_emplace(key_arg<K>&& k, Args&&... args)
0132       ABSL_ATTRIBUTE_LIFETIME_BOUND {
0133     return try_emplace_impl(std::forward<K>(k), std::forward<Args>(args)...);
0134   }
0135
0136   template <class K = key_type, class... Args,
0137             typename std::enable_if<
0138                 !std::is_convertible<K, const_iterator>::value, int>::type = 0>
0139   std::pair<iterator, bool> try_emplace(const key_arg<K>& k, Args&&... args)
0140       ABSL_ATTRIBUTE_LIFETIME_BOUND {
0141     return try_emplace_impl(k, std::forward<Args>(args)...);
0142   }
0143
0144   template <class K = key_type, class... Args, K* = nullptr>
0145   iterator try_emplace(const_iterator, key_arg<K>&& k,
0146                        Args&&... args) ABSL_ATTRIBUTE_LIFETIME_BOUND {
0147     return try_emplace(std::forward<K>(k), std::forward<Args>(args)...).first;
0148   }
0149
0150   template <class K = key_type, class... Args>
0151   iterator try_emplace(const_iterator, const key_arg<K>& k,
0152                        Args&&... args) ABSL_ATTRIBUTE_LIFETIME_BOUND {
0153     return try_emplace(k, std::forward<Args>(args)...).first;
0154   }
0155
0156   template <class K = key_type, class P = Policy>
0157   MappedReference<P> at(const key_arg<K>& key) ABSL_ATTRIBUTE_LIFETIME_BOUND {
0158     auto it = this->find(key);
0159     if (it == this->end()) {
0160       base_internal::ThrowStdOutOfRange(
0161           "absl::container_internal::raw_hash_map<>::at");
0162     }
0163     return Policy::value(&*it);
0164   }
0165
0166   template <class K = key_type, class P = Policy>
0167   MappedConstReference<P> at(const key_arg<K>& key) const
0168       ABSL_ATTRIBUTE_LIFETIME_BOUND {
0169     auto it = this->find(key);
0170     if (it == this->end()) {
0171       base_internal::ThrowStdOutOfRange(
0172           "absl::container_internal::raw_hash_map<>::at");
0173     }
0174     return Policy::value(&*it);
0175   }
0176
0177   template <class K = key_type, class P = Policy, K* = nullptr>
0178   MappedReference<P> operator[](key_arg<K>&& key)
0179       ABSL_ATTRIBUTE_LIFETIME_BOUND {
0180     // It is safe to use unchecked_deref here because try_emplace
0181     // will always return an iterator pointing to a valid item in the table,
0182     // since it inserts if nothing is found for the given key.
0183     return Policy::value(
0184         &this->unchecked_deref(try_emplace(std::forward<K>(key)).first));
0185   }
0186
0187   template <class K = key_type, class P = Policy>
0188   MappedReference<P> operator[](const key_arg<K>& key)
0189       ABSL_ATTRIBUTE_LIFETIME_BOUND {
0190     // It is safe to use unchecked_deref here because try_emplace
0191     // will always return an iterator pointing to a valid item in the table,
0192     // since it inserts if nothing is found for the given key.
0193     return Policy::value(&this->unchecked_deref(try_emplace(key).first));
0194   }
0195
0196  private:
0197   template <class K, class V>
0198   std::pair<iterator, bool> insert_or_assign_impl(K&& k, V&& v)
0199       ABSL_ATTRIBUTE_LIFETIME_BOUND {
0200     auto res = this->find_or_prepare_insert(k);
0201     if (res.second) {
0202       this->emplace_at(res.first, std::forward<K>(k), std::forward<V>(v));
0203     } else {
0204       Policy::value(&*res.first) = std::forward<V>(v);
0205     }
0206     return res;
0207   }
0208
0209   template <class K = key_type, class... Args>
0210   std::pair<iterator, bool> try_emplace_impl(K&& k, Args&&... args)
0211       ABSL_ATTRIBUTE_LIFETIME_BOUND {
0212     auto res = this->find_or_prepare_insert(k);
0213     if (res.second) {
0214       this->emplace_at(res.first, std::piecewise_construct,
0215                        std::forward_as_tuple(std::forward<K>(k)),
0216                        std::forward_as_tuple(std::forward<Args>(args)...));
0217     }
0218     return res;
0219   }
0220 };
0221
0222 }  // namespace container_internal
0223 ABSL_NAMESPACE_END
0224 }  // namespace absl
0225
0226 #endif  // ABSL_CONTAINER_INTERNAL_RAW_HASH_MAP_H_