1 // Copyright 2020 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef UTIL_FLAT_MAP_H_ 6 #define UTIL_FLAT_MAP_H_ 7 8 #include <initializer_list> 9 #include <map> 10 #include <utility> 11 #include <vector> 12 13 #include "absl/types/optional.h" 14 #include "util/osp_logging.h" 15 16 namespace openscreen { 17 18 // For small numbers of elements, a vector is much more efficient than a 19 // map or unordered_map due to not needing hashing. FlatMap allows for 20 // using map-like syntax but is backed by a std::vector, combining all the 21 // performance of a vector with the convenience of a map. 22 // 23 // NOTE: this class allows usage of const char* as Key or Value types, but 24 // it is generally recommended that you use std::string, or absl::string_view 25 // for literals. string_view is similarly efficient to a raw char* pointer, 26 // but gives sizing and equality operators, among other features. 27 template <class Key, class Value> 28 class FlatMap final : public std::vector<std::pair<Key, Value>> { 29 public: FlatMap(std::initializer_list<std::pair<Key,Value>> init_list)30 FlatMap(std::initializer_list<std::pair<Key, Value>> init_list) 31 : std::vector<std::pair<Key, Value>>(init_list) {} 32 FlatMap() = default; 33 FlatMap(const FlatMap&) = default; 34 FlatMap(FlatMap&&) noexcept = default; 35 FlatMap& operator=(const FlatMap&) = default; 36 FlatMap& operator=(FlatMap&&) = default; 37 ~FlatMap() = default; 38 39 // Accessors that wrap std::find_if, and return an iterator to the key value 40 // pair. find(const Key & key)41 decltype(auto) find(const Key& key) { 42 return std::find_if( 43 this->begin(), this->end(), 44 [key](const std::pair<Key, Value>& pair) { return key == pair.first; }); 45 } 46 find(const Key & key)47 decltype(auto) find(const Key& key) const { 48 return const_cast<FlatMap<Key, Value>*>(this)->find(key); 49 } 50 51 // Remove an entry from the map. Returns an iterator pointing to the new 52 // location of the element that followed the last element erased by the 53 // function call. This is the container end if the operation erased the last 54 // element in the sequence. erase_key(const Key & key)55 decltype(auto) erase_key(const Key& key) { 56 auto it = find(key); 57 // This will otherwise segfault on platforms, as it is undefined behavior. 58 OSP_CHECK(it != this->end()) << "failed to erase: element not found"; 59 return static_cast<std::vector<std::pair<Key, Value>>*>(this)->erase(it); 60 } 61 }; 62 63 } // namespace openscreen 64 65 #endif // UTIL_FLAT_MAP_H_ 66