1 // Copyright 2017 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 BASE_CONTAINERS_FLAT_SET_H_ 6 #define BASE_CONTAINERS_FLAT_SET_H_ 7 8 #include <functional> 9 10 #include "base/containers/flat_tree.h" 11 #include "base/template_util.h" 12 13 namespace base { 14 15 // flat_set is a container with a std::set-like interface that stores its 16 // contents in a sorted vector. 17 // 18 // Please see //base/containers/README.md for an overview of which container 19 // to select. 20 // 21 // PROS 22 // 23 // - Good memory locality. 24 // - Low overhead, especially for smaller sets. 25 // - Performance is good for more workloads than you might expect (see 26 // overview link above). 27 // - Supports C++14 set interface. 28 // 29 // CONS 30 // 31 // - Inserts and removals are O(n). 32 // 33 // IMPORTANT NOTES 34 // 35 // - Iterators are invalidated across mutations. 36 // - If possible, construct a flat_set in one operation by inserting into 37 // a std::vector and moving that vector into the flat_set constructor. 38 // - For multiple removals use base::EraseIf() which is O(n) rather than 39 // O(n * removed_items). 40 // 41 // QUICK REFERENCE 42 // 43 // Most of the core functionality is inherited from flat_tree. Please see 44 // flat_tree.h for more details for most of these functions. As a quick 45 // reference, the functions available are: 46 // 47 // Constructors (inputs need not be sorted): 48 // flat_set(InputIterator first, InputIterator last, 49 // FlatContainerDupes = KEEP_FIRST_OF_DUPES, 50 // const Compare& compare = Compare()); 51 // flat_set(const flat_set&); 52 // flat_set(flat_set&&); 53 // flat_set(std::vector<Key>, 54 // FlatContainerDupes = KEEP_FIRST_OF_DUPES, 55 // const Compare& compare = Compare()); // Re-use storage. 56 // flat_set(std::initializer_list<value_type> ilist, 57 // FlatContainerDupes = KEEP_FIRST_OF_DUPES, 58 // const Compare& comp = Compare()); 59 // 60 // Assignment functions: 61 // flat_set& operator=(const flat_set&); 62 // flat_set& operator=(flat_set&&); 63 // flat_set& operator=(initializer_list<Key>); 64 // 65 // Memory management functions: 66 // void reserve(size_t); 67 // size_t capacity() const; 68 // void shrink_to_fit(); 69 // 70 // Size management functions: 71 // void clear(); 72 // size_t size() const; 73 // size_t max_size() const; 74 // bool empty() const; 75 // 76 // Iterator functions: 77 // iterator begin(); 78 // const_iterator begin() const; 79 // const_iterator cbegin() const; 80 // iterator end(); 81 // const_iterator end() const; 82 // const_iterator cend() const; 83 // reverse_iterator rbegin(); 84 // const reverse_iterator rbegin() const; 85 // const_reverse_iterator crbegin() const; 86 // reverse_iterator rend(); 87 // const_reverse_iterator rend() const; 88 // const_reverse_iterator crend() const; 89 // 90 // Insert and accessor functions: 91 // pair<iterator, bool> insert(const key_type&); 92 // pair<iterator, bool> insert(key_type&&); 93 // void insert(InputIterator first, InputIterator last, 94 // FlatContainerDupes = KEEP_FIRST_OF_DUPES); 95 // iterator insert(const_iterator hint, const key_type&); 96 // iterator insert(const_iterator hint, key_type&&); 97 // pair<iterator, bool> emplace(Args&&...); 98 // iterator emplace_hint(const_iterator, Args&&...); 99 // 100 // Erase functions: 101 // iterator erase(iterator); 102 // iterator erase(const_iterator); 103 // iterator erase(const_iterator first, const_iterator& last); 104 // template <typename K> size_t erase(const K& key); 105 // 106 // Comparators (see std::set documentation). 107 // key_compare key_comp() const; 108 // value_compare value_comp() const; 109 // 110 // Search functions: 111 // template <typename K> size_t count(const K&) const; 112 // template <typename K> iterator find(const K&); 113 // template <typename K> const_iterator find(const K&) const; 114 // template <typename K> pair<iterator, iterator> equal_range(K&); 115 // template <typename K> iterator lower_bound(const K&); 116 // template <typename K> const_iterator lower_bound(const K&) const; 117 // template <typename K> iterator upper_bound(const K&); 118 // template <typename K> const_iterator upper_bound(const K&) const; 119 // 120 // General functions: 121 // void swap(flat_set&&); 122 // 123 // Non-member operators: 124 // bool operator==(const flat_set&, const flat_set); 125 // bool operator!=(const flat_set&, const flat_set); 126 // bool operator<(const flat_set&, const flat_set); 127 // bool operator>(const flat_set&, const flat_set); 128 // bool operator>=(const flat_set&, const flat_set); 129 // bool operator<=(const flat_set&, const flat_set); 130 // 131 template <class Key, class Compare = std::less<>> 132 using flat_set = typename ::base::internal::flat_tree< 133 Key, 134 Key, 135 ::base::internal::GetKeyFromValueIdentity<Key>, 136 Compare>; 137 138 } // namespace base 139 140 #endif // BASE_CONTAINERS_FLAT_SET_H_ 141