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 13namespace 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> bool contains(const K&) const; 115// template <typename K> pair<iterator, iterator> equal_range(K&); 116// template <typename K> iterator lower_bound(const K&); 117// template <typename K> const_iterator lower_bound(const K&) const; 118// template <typename K> iterator upper_bound(const K&); 119// template <typename K> const_iterator upper_bound(const K&) const; 120// 121// General functions: 122// void swap(flat_set&&); 123// 124// Non-member operators: 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// bool operator<=(const flat_set&, const flat_set); 131// 132template <class Key, class Compare = std::less<>> 133using flat_set = typename ::base::internal::flat_tree< 134 Key, 135 Key, 136 ::base::internal::GetKeyFromValueIdentity<Key>, 137 Compare>; 138 139} // namespace base 140 141#endif // BASE_CONTAINERS_FLAT_SET_H_