• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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