65 #include <initializer_list> 68 #include <type_traits> 82 template <
typename,
typename Compare,
typename Key,
typename T>
85 template <
typename Compare,
typename Key,
typename T>
87 void_t<typename Compare::is_transparent>,
97 template <
class Policy>
99 template <
class Container,
class Iterator>
101 typedef typename Container::difference_type diff_t;
102 diff_t d = desired_insertion - c.begin();
103 Policy::increase_capacity(c);
104 return c.begin() + d;
109 template <
class Container,
class Iterator>
121 template <
class Iterator>
123 typedef typename std::iterator_traits<Iterator>::iterator_category categ;
127 return std::distance(first, last);
130 template <
class OurContainer,
class Vector,
class GrowthPolicy>
132 OurContainer& sorted,
134 typename OurContainer::iterator hint,
135 typename OurContainer::value_type&&
value,
137 const typename OurContainer::value_compare& cmp(sorted.value_comp());
138 if (hint == cont.end() || cmp(
value, *hint)) {
139 if (hint == cont.begin() || cmp(*(hint - 1),
value)) {
140 hint = po.increase_capacity(cont, hint);
147 if (cmp(*hint,
value)) {
148 if (hint + 1 == cont.end() || cmp(
value, *(hint + 1))) {
149 hint = po.increase_capacity(cont, hint + 1);
160 template <
class OurContainer,
class Vector,
class InputIterator>
162 OurContainer& sorted,
165 InputIterator last) {
171 auto const& cmp(sorted.value_comp());
175 cont.reserve(cont.size() + d);
177 auto const prev_size = cont.size();
179 std::copy(first, last, std::back_inserter(cont));
180 auto const middle = cont.begin() + prev_size;
181 if (!std::is_sorted(middle, cont.end(), cmp)) {
182 std::sort(middle, cont.end(), cmp);
184 if (middle != cont.begin() && !cmp(*(middle - 1), *middle)) {
185 std::inplace_merge(cont.begin(), middle, cont.end(), cmp);
191 [&](
typename OurContainer::value_type
const&
a,
192 typename OurContainer::value_type
const&
b) {
193 return !cmp(a,
b) && !cmp(
b, a);
198 template <
typename Container,
typename Compare>
199 Container&&
as_sorted(Container&& container, Compare
const& comp) {
201 std::sort(
begin(container),
end(container), comp);
202 return static_cast<Container&&
>(container);
224 class Compare = std::less<T>,
225 class Allocator = std::allocator<T>,
226 class GrowthPolicy = void,
227 class Container = std::vector<T, Allocator>>
233 template <
typename K,
typename V,
typename C = Compare>
259 const Compare& comp = Compare(),
260 const Allocator& alloc = Allocator())
263 template <
class InputIterator>
267 const Compare& comp = Compare(),
268 const Allocator& alloc = Allocator())
276 std::initializer_list<value_type>
list,
277 const Compare& comp = Compare(),
278 const Allocator& alloc = Allocator())
280 insert(list.begin(), list.end());
292 Container&& container,
293 const Compare& comp = Compare())
310 Container&& container,
311 const Compare& comp = Compare())
312 : m_(comp, container.get_allocator()) {
313 assert(std::is_sorted(container.begin(), container.end(), value_comp()));
314 m_.cont_.swap(container);
319 insert(ilist.begin(), ilist.end());
331 return m_.cont_.begin();
334 return m_.cont_.end();
337 return m_.cont_.cbegin();
340 return m_.cont_.begin();
343 return m_.cont_.cend();
345 const_iterator
end()
const {
346 return m_.cont_.end();
349 return m_.cont_.rbegin();
352 return m_.cont_.rend();
355 return m_.cont_.rbegin();
357 const_reverse_iterator
rend()
const {
358 return m_.cont_.rend();
362 return m_.cont_.clear();
365 return m_.cont_.size();
368 return m_.cont_.max_size();
371 return m_.cont_.empty();
374 return m_.cont_.reserve(s);
377 m_.cont_.shrink_to_fit();
380 return m_.cont_.capacity();
384 return insert(
std::move(value_type(value)));
388 iterator it = lower_bound(
value);
389 if (it ==
end() || value_comp()(
value, *it)) {
390 it = get_growth_policy().increase_capacity(m_.cont_, it);
391 return std::make_pair(m_.cont_.insert(it,
std::move(
value)),
true);
393 return std::make_pair(it,
false);
397 return insert(hint,
std::move(value_type(value)));
405 template <
class InputIterator>
406 void insert(InputIterator first, InputIterator last) {
410 size_type
erase(
const key_type& key) {
411 iterator it = find(key);
420 return m_.cont_.erase(it);
423 iterator
erase(iterator first, iterator last) {
424 return m_.cont_.erase(first, last);
427 iterator
find(
const key_type& key) {
428 return find(*
this, key);
431 const_iterator
find(
const key_type& key)
const {
432 return find(*
this, key);
435 template <
typename K>
437 return find(*
this, key);
440 template <
typename K>
442 return find(*
this, key);
445 size_type
count(
const key_type& key)
const {
446 return find(key) ==
end() ? 0 : 1;
449 template <
typename K>
451 return find(key) ==
end() ? 0 : 1;
455 return std::lower_bound(
begin(),
end(), key, key_comp());
459 return std::lower_bound(
begin(),
end(), key, key_comp());
462 template <
typename K>
464 return std::lower_bound(
begin(),
end(), key, key_comp());
467 template <
typename K>
469 return std::lower_bound(
begin(),
end(), key, key_comp());
473 return std::upper_bound(
begin(),
end(), key, key_comp());
477 return std::upper_bound(
begin(),
end(), key, key_comp());
480 template <
typename K>
482 return std::upper_bound(
begin(),
end(), key, key_comp());
485 template <
typename K>
487 return std::upper_bound(
begin(),
end(), key, key_comp());
491 return std::equal_range(
begin(),
end(), key, key_comp());
495 const key_type& key)
const {
496 return std::equal_range(
begin(),
end(), key, key_comp());
499 template <
typename K>
502 return std::equal_range(
begin(),
end(), key, key_comp());
505 template <
typename K>
507 const K& key)
const {
508 return std::equal_range(
begin(),
end(), key, key_comp());
521 return other.
m_.
cont_ == m_.cont_;
528 return m_.cont_ < other.
m_.
cont_;
531 return other < *
this;
541 return m_.cont_.data();
557 explicit EBO(
const Compare&
c,
const Allocator& alloc)
558 : Compare(c), cont_(alloc) {}
562 template <
typename Self>
566 template <
typename Self,
typename K>
568 auto end =
self.end();
569 auto it =
self.lower_bound(key);
570 if (it ==
end || !
self.key_comp()(key, *it)) {
578 template <
class T,
class C,
class A,
class G>
605 class Compare = std::less<Key>,
606 class Allocator = std::allocator<std::pair<Key, Value>>,
607 class GrowthPolicy = void,
608 class Container = std::vector<std::pair<Key, Value>, Allocator>>
614 template <
typename K,
typename V,
typename C = Compare>
624 struct value_compare :
private Compare {
626 return Compare::operator()(a.first, b.first);
645 const Compare& comp = Compare(),
646 const Allocator& alloc = Allocator())
647 : m_(value_compare(comp), alloc) {}
649 template <
class InputIterator>
653 const Compare& comp = Compare(),
654 const Allocator& alloc = Allocator())
655 : m_(value_compare(comp), alloc) {
660 std::initializer_list<value_type> list,
661 const Compare& comp = Compare(),
662 const Allocator& alloc = Allocator())
663 : m_(value_compare(comp), alloc) {
664 insert(list.begin(), list.end());
676 Container&& container,
677 const Compare& comp = Compare())
694 Container&& container,
695 const Compare& comp = Compare())
696 : m_(value_compare(comp), container.get_allocator()) {
697 assert(std::is_sorted(container.begin(), container.end(), value_comp()));
698 m_.cont_.swap(container);
703 insert(ilist.begin(), ilist.end());
715 return m_.cont_.begin();
718 return m_.cont_.end();
721 return m_.cont_.cbegin();
724 return m_.cont_.begin();
727 return m_.cont_.cend();
729 const_iterator
end()
const {
730 return m_.cont_.end();
733 return m_.cont_.rbegin();
736 return m_.cont_.rend();
739 return m_.cont_.rbegin();
741 const_reverse_iterator
rend()
const {
742 return m_.cont_.rend();
746 return m_.cont_.clear();
749 return m_.cont_.size();
752 return m_.cont_.max_size();
755 return m_.cont_.empty();
758 return m_.cont_.reserve(s);
761 m_.cont_.shrink_to_fit();
764 return m_.cont_.capacity();
768 return insert(
std::move(value_type(value)));
772 iterator it = lower_bound(
value.first);
773 if (it ==
end() || value_comp()(
value, *it)) {
774 it = get_growth_policy().increase_capacity(m_.cont_, it);
775 return std::make_pair(m_.cont_.insert(it,
std::move(
value)),
true);
777 return std::make_pair(it,
false);
781 return insert(hint,
std::move(value_type(value)));
789 template <
class InputIterator>
790 void insert(InputIterator first, InputIterator last) {
794 size_type
erase(
const key_type& key) {
795 iterator it = find(key);
804 return m_.cont_.erase(it);
807 iterator
erase(iterator first, iterator last) {
808 return m_.cont_.erase(first, last);
811 iterator
find(
const key_type& key) {
812 return find(*
this, key);
815 const_iterator
find(
const key_type& key)
const {
816 return find(*
this, key);
819 template <
typename K>
821 return find(*
this, key);
824 template <
typename K>
826 return find(*
this, key);
829 mapped_type&
at(
const key_type& key) {
830 iterator it = find(key);
834 throw_exception<std::out_of_range>(
"sorted_vector_map::at");
837 const mapped_type&
at(
const key_type& key)
const {
838 const_iterator it = find(key);
842 throw_exception<std::out_of_range>(
"sorted_vector_map::at");
845 size_type
count(
const key_type& key)
const {
846 return find(key) ==
end() ? 0 : 1;
849 template <
typename K>
851 return find(key) ==
end() ? 0 : 1;
855 return lower_bound(*
this, key);
859 return lower_bound(*
this, key);
862 template <
typename K>
864 return lower_bound(*
this, key);
867 template <
typename K>
869 return lower_bound(*
this, key);
873 return upper_bound(*
this, key);
877 return upper_bound(*
this, key);
880 template <
typename K>
882 return upper_bound(*
this, key);
885 template <
typename K>
887 return upper_bound(*
this, key);
891 return equal_range(*
this, key);
895 const key_type& key)
const {
896 return equal_range(*
this, key);
899 template <
typename K>
902 return equal_range(*
this, key);
905 template <
typename K>
907 const K& key)
const {
908 return equal_range(*
this, key);
921 iterator it = lower_bound(key);
922 if (it ==
end() || key_comp()(key, it->first)) {
923 return insert(it, value_type(key, mapped_type()))->second;
929 return m_.cont_ == other.
m_.
cont_;
936 return m_.cont_ < other.
m_.
cont_;
939 return other < *
this;
949 return m_.cont_.data();
955 struct EBO : value_compare {
956 explicit EBO(
const value_compare&
c,
const Allocator& alloc)
957 : value_compare(c), cont_(alloc) {}
961 template <
typename Self>
965 template <
typename Self,
typename K>
967 auto end =
self.end();
968 auto it =
self.lower_bound(key);
969 if (it ==
end || !
self.key_comp()(key, it->first)) {
975 template <
typename Self,
typename K>
977 auto f = [
c =
self.key_comp()](value_type
const&
a, K
const&
b) {
978 return c(a.first,
b);
980 return std::lower_bound(
self.
begin(),
self.
end(), key,
f);
983 template <
typename Self,
typename K>
985 auto f = [
c =
self.key_comp()](K
const&
a, value_type
const&
b) {
986 return c(a,
b.first);
988 return std::upper_bound(
self.
begin(),
self.
end(), key,
f);
991 template <
typename Self,
typename K>
998 return {lower_bound(
self, key), upper_bound(
self, key)};
1003 template <
class K,
class V,
class C,
class A,
class G>
Container::iterator iterator
EBO(const value_compare &c, const Allocator &alloc)
Container::difference_type difference_type
bool operator>(const Expected< Value, Error > &lhs, const Expected< Value, Error > &rhs)
if_is_transparent< K, const_iterator > lower_bound(const K &key) const
Container::reference reference
const_iterator cend() const
iterator insert(iterator hint, const value_type &value)
int distance_if_multipass(Iterator first, Iterator last)
bool operator>=(const sorted_vector_set &other) const
if_is_transparent< K, const_iterator > find(const K &key) const
if_is_transparent< K, size_type > count(const K &key) const
const_reverse_iterator rend() const
sorted_vector_map(presorted_t, Container &&container, const Compare &comp=Compare())
Container::const_reverse_iterator const_reverse_iterator
Container::const_reference const_reference
bool operator!=(const sorted_vector_map &other) const
bool operator()(const value_type &a, const value_type &b) const
detail::growth_policy_wrapper< GrowthPolicy > & get_growth_policy()
sorted_vector_set & operator=(std::initializer_list< value_type > ilist)
sorted_vector_set(presorted_t, Container &&container, const Compare &comp=Compare())
size_type erase(const key_type &key)
iterator erase(iterator first, iterator last)
_t< std::conditional< std::is_const< Self >::value, const_iterator, iterator >> self_iterator_t
bool operator<(const sorted_vector_set &other) const
if_is_transparent< K, size_type > count(const K &key) const
if_is_transparent< K, const_iterator > upper_bound(const K &key) const
Container::const_iterator const_iterator
Container::const_iterator const_iterator
if_is_transparent< K, std::pair< iterator, iterator > > equal_range(const K &key)
std::pair< iterator, iterator > equal_range(const key_type &key)
Container::size_type size_type
iterator lower_bound(const key_type &key)
static self_iterator_t< Self > upper_bound(Self &self, K const &key)
std::pair< iterator, iterator > equal_range(const key_type &key)
std::pair< const_iterator, const_iterator > equal_range(const key_type &key) const
mapped_type & at(const key_type &key)
reverse_iterator rbegin()
size_type count(const key_type &key) const
Container::pointer pointer
size_type erase(const key_type &key)
const_reverse_iterator rbegin() const
value_compare value_comp() const
void swap(sorted_vector_map< K, V, C, A, G > &a, sorted_vector_map< K, V, C, A, G > &b)
const mapped_type & at(const key_type &key) const
std::pair< const_iterator, const_iterator > equal_range(const key_type &key) const
size_type capacity() const
if_is_transparent< K, const_iterator > find(const K &key) const
const_iterator lower_bound(const key_type &key) const
if_is_transparent< K, std::pair< const_iterator, const_iterator > > equal_range(const K &key) const
iterator insert(iterator hint, value_type &&value)
constexpr detail::Map< Move > move
const_iterator find(const key_type &key) const
internal::KeyMatcher< M > Key(M inner_matcher)
static self_iterator_t< Self > find(Self &self, K const &key)
bool operator==(const sorted_vector_map &other) const
sorted_vector_set(const Compare &comp=Compare(), const Allocator &alloc=Allocator())
auto begin(TestAdlIterable &instance)
Iterator increase_capacity(Container &c, Iterator desired_insertion)
iterator insert(iterator hint, const value_type &value)
sorted_vector_map(const Compare &comp=Compare(), const Allocator &alloc=Allocator())
Container::iterator iterator
—— Concurrent Priority Queue Implementation ——
std::pair< iterator, bool > insert(const value_type &value)
Container::reverse_iterator reverse_iterator
std::pair< iterator, bool > insert(value_type &&value)
requires E e noexcept(noexcept(s.error(std::move(e))))
bool operator<(const sorted_vector_map &other) const
OurContainer::iterator insert_with_hint(OurContainer &sorted, Vector &cont, typename OurContainer::iterator hint, typename OurContainer::value_type &&value, GrowthPolicy &po)
sorted_vector_map(std::initializer_list< value_type > list, const Compare &comp=Compare(), const Allocator &alloc=Allocator())
bool operator>=(const sorted_vector_map &other) const
size_type max_size() const
static self_iterator_t< Self > lower_bound(Self &self, K const &key)
const value_type * data() const noexcept
bool operator>(const sorted_vector_set &other) const
sorted_vector_set(Container &&container, const Compare &comp=Compare())
Container::pointer pointer
sorted_vector_map(InputIterator first, InputIterator last, const Compare &comp=Compare(), const Allocator &alloc=Allocator())
void reserve(size_type s)
iterator find(const key_type &key)
folly::sorted_vector_set::EBO m_
void insert(InputIterator first, InputIterator last)
value_compare value_comp() const
constexpr std::decay< T >::type copy(T &&value) noexcept(noexcept(typename std::decay< T >::type(std::forward< T >(value))))
const_iterator cbegin() const
bool operator<=(const sorted_vector_set &other) const
iterator lower_bound(const key_type &key)
const_reverse_iterator rbegin() const
iterator erase(iterator it)
const_iterator end() const
const_iterator begin() const
const_iterator cend() const
bool Value(const T &value, M matcher)
auto end(TestAdlIterable &instance)
if_is_transparent< K, iterator > lower_bound(const K &key)
std::pair< iterator, bool > insert(const value_type &value)
if_is_transparent< K, iterator > find(const K &key)
Encoder::MutableCompressedList list
Container::size_type size_type
sorted_vector_map & operator=(std::initializer_list< value_type > ilist)
void insert(InputIterator first, InputIterator last)
type_t< void, Ts... > void_t
sorted_vector_map(Container &&container, const Compare &comp=Compare())
const_iterator upper_bound(const key_type &key) const
Container::difference_type difference_type
const_reverse_iterator rend() const
sorted_vector_set(std::initializer_list< value_type > list, const Compare &comp=Compare(), const Allocator &alloc=Allocator())
if_is_transparent< K, iterator > upper_bound(const K &key)
const_iterator cbegin() const
if_is_transparent< K, iterator > upper_bound(const K &key)
static const char *const value
if_is_transparent< K, iterator > lower_bound(const K &key)
bool operator==(const sorted_vector_set &other) const
bool operator>(const sorted_vector_map &other) const
const_iterator find(const key_type &key) const
size_type capacity() const
Container::reference reference
const_iterator begin() const
Iterator increase_capacity(Container &, Iterator it)
iterator insert(iterator hint, value_type &&value)
key_compare key_comp() const
void swap(exception_wrapper &a, exception_wrapper &b) noexcept
reverse_iterator rbegin()
if_is_transparent< K, std::pair< iterator, iterator > > equal_range(const K &key)
bool operator==(const Unexpected< Error > &lhs, const Unexpected< Error > &rhs)
iterator upper_bound(const key_type &key)
_t< detail::sorted_vector_enable_if_is_transparent< void, C, K, V >> if_is_transparent
constexpr presorted_t presorted
const_iterator end() const
const_iterator lower_bound(const key_type &key) const
size_type count(const key_type &key) const
Container::reverse_iterator reverse_iterator
Container::value_type value_type
value_compare(const Compare &c)
iterator upper_bound(const key_type &key)
if_is_transparent< K, std::pair< const_iterator, const_iterator > > equal_range(const K &key) const
mapped_type & operator[](const key_type &key)
void swap(sorted_vector_map &o)
iterator erase(iterator first, iterator last)
Container::const_reverse_iterator const_reverse_iterator
uint64_t value(const typename LockFreeRingBuffer< T, Atom >::Cursor &rbcursor)
_t< std::conditional< std::is_const< Self >::value, const_iterator, iterator >> self_iterator_t
static self_iterator_t< Self > find(Self &self, K const &key)
Container && as_sorted(Container &&container, Compare const &comp)
EBO(const Compare &c, const Allocator &alloc)
size_type max_size() const
if_is_transparent< K, const_iterator > upper_bound(const K &key) const
bool operator!=(const sorted_vector_set &other) const
folly::sorted_vector_map::EBO m_
detail::growth_policy_wrapper< GrowthPolicy > & get_growth_policy()
iterator find(const key_type &key)
sorted_vector_set(InputIterator first, InputIterator last, const Compare &comp=Compare(), const Allocator &alloc=Allocator())
bool operator<=(const sorted_vector_map &other) const
iterator erase(iterator it)
std::pair< iterator, bool > insert(value_type &&value)
if_is_transparent< K, const_iterator > lower_bound(const K &key) const
void bulk_insert(OurContainer &sorted, Vector &cont, InputIterator first, InputIterator last)
const_iterator upper_bound(const key_type &key) const
const value_type * data() const noexcept
Container::const_reference const_reference
void reserve(size_type s)
void swap(sorted_vector_set &o)
std::enable_if< IsLessThanComparable< Value >::value, bool >::type operator<(const Expected< Value, Error > &lhs, const Expected< Value, Error > &rhs)
key_compare key_comp() const
constexpr detail::First first
static std::pair< self_iterator_t< Self >, self_iterator_t< Self > > equal_range(Self &self, K const &key)
_t< detail::sorted_vector_enable_if_is_transparent< void, C, K, V >> if_is_transparent
if_is_transparent< K, iterator > find(const K &key)