1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
// Copyright 2020 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#ifndef BASE_CONTAINERS_FIXED_FLAT_MAP_H_
#define BASE_CONTAINERS_FIXED_FLAT_MAP_H_
#include <array>
#include <functional>
#include <utility>
#include "base/check.h"
#include "base/containers/flat_map.h"
#include "base/containers/flat_tree.h"
namespace base {
// fixed_flat_map is a immutable container with a std::map-like interface that
// stores its contents in a sorted std::array.
//
// It is a special case of base::flat_map, and mostly useful as a look-up table.
//
// Please see //base/containers/README.md for an overview of which container
// to select.
//
// QUICK REFERENCE
//
// Most of the core functionality is inherited from flat_tree. Please see
// flat_tree.h for more details for most of these functions. As a quick
// reference, the functions available are:
//
// Constructors (inputs need to be sorted):
// fixed_flat_map(const fixed_flat_map&);
// fixed_flat_map(sorted_unique_t,
// const container_type& items,
// const Compare& compare = Compare());
//
// Size management functions:
// size_t size() const;
// size_t max_size() const;
// bool empty() const;
//
// Iterator functions:
// iterator begin();
// const_iterator begin() const;
// const_iterator cbegin() const;
// iterator end();
// const_iterator end() const;
// const_iterator cend() const;
// reverse_iterator rbegin();
// const reverse_iterator rbegin() const;
// const_reverse_iterator crbegin() const;
// reverse_iterator rend();
// const_reverse_iterator rend() const;
// const_reverse_iterator crend() const;
//
// Insert and accessor functions:
// mapped_type& at(const K&);
// const mapped_type& at(const K&) const;
// Comparators (see std::map documentation).
// key_compare key_comp() const;
// value_compare value_comp() const;
//
// Search functions:
// template <typename K> size_t count(const K&) const;
// template <typename K> iterator find(const K&);
// template <typename K> const_iterator find(const K&) const;
// template <typename K> bool contains(const K&) const;
// template <typename K>
// pair<iterator, iterator> equal_range(const K&);
// template <typename K>
// pair<const_iterator, const_iterator> equal_range(K&) const;
// template <typename K> iterator lower_bound(const K&);
// template <typename K> const_iterator lower_bound(const K&) const;
// template <typename K> iterator upper_bound(const K&);
// template <typename K> const_iterator upper_bound(const K&) const;
//
// Non-member operators:
// bool operator==(const fixed_flat_map&, const fixed_flat_map&);
// bool operator!=(const fixed_flat_map&, const fixed_flat_map&);
// bool operator<(const fixed_flat_map&, const fixed_flat_map&);
// bool operator>(const fixed_flat_map&, const fixed_flat_map&);
// bool operator>=(const fixed_flat_map&, const fixed_flat_map&);
// bool operator<=(const fixed_flat_map&, const fixed_flat_map&);
//
template <class Key, class Mapped, size_t N, class Compare = std::less<>>
using fixed_flat_map = base::
flat_map<Key, Mapped, Compare, std::array<std::pair<const Key, Mapped>, N>>;
// Utility function to simplify constructing a fixed_flat_map from a fixed list
// of keys and values. Requires that the passed in `data` contains unique keys.
//
// Example usage:
// constexpr auto kMap = base::MakeFixedFlatMap<base::StringPiece, int>(
// {{"foo", 1}, {"bar", 2}, {"baz", 3}});
template <class Key, class Mapped, size_t N, class Compare = std::less<>>
constexpr fixed_flat_map<Key, Mapped, N, Compare> MakeFixedFlatMap(
std::pair<Key, Mapped>(&&data)[N],
const Compare& comp = Compare()) {
using FixedFlatMap = fixed_flat_map<Key, Mapped, N, Compare>;
typename FixedFlatMap::value_compare value_comp{comp};
internal::InsertionSort(data, data + N, value_comp);
// CHECK(internal::is_sorted_and_unique(data, value_comp));
// Specify the value_type explicitly to ensure that the returned array has
// immutable keys.
return FixedFlatMap(
sorted_unique, internal::ToArray<typename FixedFlatMap::value_type>(data),
comp);
}
} // namespace base
#endif // BASE_CONTAINERS_FIXED_FLAT_MAP_H_
|
