#include <vector>
#include <boost/operators.hpp>
+
+#include <folly/Traits.h>
#include <folly/portability/BitsFunctexcept.h>
namespace folly {
namespace detail {
- // This wrapper goes around a GrowthPolicy and provides iterator
- // preservation semantics, but only if the growth policy is not the
- // default (i.e. nothing).
- template <class Policy>
- struct growth_policy_wrapper : private Policy {
- template <class Container, class Iterator>
- Iterator increase_capacity(Container& c, Iterator desired_insertion)
- {
- typedef typename Container::difference_type diff_t;
- diff_t d = desired_insertion - c.begin();
- Policy::increase_capacity(c);
- return c.begin() + d;
- }
- };
- template <>
- struct growth_policy_wrapper<void> {
- template <class Container, class Iterator>
- Iterator increase_capacity(Container&, Iterator it) {
- return it;
- }
- };
+template <typename, typename Compare, typename Key, typename T>
+struct sorted_vector_enable_if_is_transparent {};
- /*
- * This helper returns the distance between two iterators if it is
- * possible to figure it out without messing up the range
- * (i.e. unless they are InputIterators). Otherwise this returns
- * -1.
- */
- template <class Iterator>
- int distance_if_multipass(Iterator first, Iterator last) {
- typedef typename std::iterator_traits<Iterator>::iterator_category categ;
- if (std::is_same<categ, std::input_iterator_tag>::value) {
- return -1;
- }
- return std::distance(first, last);
+template <typename Compare, typename Key, typename T>
+struct sorted_vector_enable_if_is_transparent<
+ void_t<typename Compare::is_transparent>,
+ Compare,
+ Key,
+ T> {
+ using type = T;
+};
+
+// This wrapper goes around a GrowthPolicy and provides iterator
+// preservation semantics, but only if the growth policy is not the
+// default (i.e. nothing).
+template <class Policy>
+struct growth_policy_wrapper : private Policy {
+ template <class Container, class Iterator>
+ Iterator increase_capacity(Container& c, Iterator desired_insertion) {
+ typedef typename Container::difference_type diff_t;
+ diff_t d = desired_insertion - c.begin();
+ Policy::increase_capacity(c);
+ return c.begin() + d;
+ }
+};
+template <>
+struct growth_policy_wrapper<void> {
+ template <class Container, class Iterator>
+ Iterator increase_capacity(Container&, Iterator it) {
+ return it;
}
+};
- template <class OurContainer, class Vector, class GrowthPolicy>
- typename OurContainer::iterator
- insert_with_hint(OurContainer& sorted,
- Vector& cont,
- typename OurContainer::iterator hint,
- typename OurContainer::value_type&& value,
- GrowthPolicy& po)
- {
- const typename OurContainer::value_compare& cmp(sorted.value_comp());
- if (hint == cont.end() || cmp(value, *hint)) {
- if (hint == cont.begin() || cmp(*(hint - 1), value)) {
- hint = po.increase_capacity(cont, hint);
- return cont.insert(hint, std::move(value));
- } else {
- return sorted.insert(std::move(value)).first;
- }
- }
+/*
+ * This helper returns the distance between two iterators if it is
+ * possible to figure it out without messing up the range
+ * (i.e. unless they are InputIterators). Otherwise this returns
+ * -1.
+ */
+template <class Iterator>
+int distance_if_multipass(Iterator first, Iterator last) {
+ typedef typename std::iterator_traits<Iterator>::iterator_category categ;
+ if (std::is_same<categ, std::input_iterator_tag>::value) {
+ return -1;
+ }
+ return std::distance(first, last);
+}
- if (cmp(*hint, value)) {
- if (hint + 1 == cont.end() || cmp(value, *(hint + 1))) {
- hint = po.increase_capacity(cont, hint + 1);
- return cont.insert(hint, std::move(value));
- } else {
- return sorted.insert(std::move(value)).first;
- }
+template <class OurContainer, class Vector, class GrowthPolicy>
+typename OurContainer::iterator insert_with_hint(
+ OurContainer& sorted,
+ Vector& cont,
+ typename OurContainer::iterator hint,
+ typename OurContainer::value_type&& value,
+ GrowthPolicy& po) {
+ const typename OurContainer::value_compare& cmp(sorted.value_comp());
+ if (hint == cont.end() || cmp(value, *hint)) {
+ if (hint == cont.begin() || cmp(*(hint - 1), value)) {
+ hint = po.increase_capacity(cont, hint);
+ return cont.insert(hint, std::move(value));
+ } else {
+ return sorted.insert(std::move(value)).first;
}
-
- // Value and *hint did not compare, so they are equal keys.
- return hint;
}
- template <class OurContainer, class Vector, class InputIterator>
- void bulk_insert(
- OurContainer& sorted,
- Vector& cont,
- InputIterator first,
- InputIterator last) {
- // prevent deref of middle where middle == cont.end()
- if (first == last) {
- return;
+ if (cmp(*hint, value)) {
+ if (hint + 1 == cont.end() || cmp(value, *(hint + 1))) {
+ hint = po.increase_capacity(cont, hint + 1);
+ return cont.insert(hint, std::move(value));
+ } else {
+ return sorted.insert(std::move(value)).first;
}
+ }
- auto const& cmp(sorted.value_comp());
-
- int const d = distance_if_multipass(first, last);
- if (d != -1) {
- cont.reserve(cont.size() + d);
- }
- auto const prev_size = cont.size();
+ // Value and *hint did not compare, so they are equal keys.
+ return hint;
+}
- std::copy(first, last, std::back_inserter(cont));
- auto const middle = cont.begin() + prev_size;
- if (!std::is_sorted(middle, cont.end(), cmp)) {
- std::sort(middle, cont.end(), cmp);
- }
- if (middle != cont.begin() && !cmp(*(middle - 1), *middle)) {
- std::inplace_merge(cont.begin(), middle, cont.end(), cmp);
- cont.erase(
- std::unique(
- cont.begin(),
- cont.end(),
- [&](typename OurContainer::value_type const& a,
- typename OurContainer::value_type const& b) {
- return !cmp(a, b) && !cmp(b, a);
- }),
- cont.end());
- }
+template <class OurContainer, class Vector, class InputIterator>
+void bulk_insert(
+ OurContainer& sorted,
+ Vector& cont,
+ InputIterator first,
+ InputIterator last) {
+ // prevent deref of middle where middle == cont.end()
+ if (first == last) {
+ return;
+ }
+
+ auto const& cmp(sorted.value_comp());
+
+ int const d = distance_if_multipass(first, last);
+ if (d != -1) {
+ cont.reserve(cont.size() + d);
+ }
+ auto const prev_size = cont.size();
+
+ std::copy(first, last, std::back_inserter(cont));
+ auto const middle = cont.begin() + prev_size;
+ if (!std::is_sorted(middle, cont.end(), cmp)) {
+ std::sort(middle, cont.end(), cmp);
+ }
+ if (middle != cont.begin() && !cmp(*(middle - 1), *middle)) {
+ std::inplace_merge(cont.begin(), middle, cont.end(), cmp);
+ cont.erase(
+ std::unique(
+ cont.begin(),
+ cont.end(),
+ [&](typename OurContainer::value_type const& a,
+ typename OurContainer::value_type const& b) {
+ return !cmp(a, b) && !cmp(b, a);
+ }),
+ cont.end());
}
}
+} // namespace detail
//////////////////////////////////////////////////////////////////////
/**
* A sorted_vector_set is a container similar to std::set<>, but
- * implemented as as a sorted array with std::vector<>.
+ * implemented as a sorted array with std::vector<>.
*
* @param class T Data type to store
* @param class Compare Comparison function that imposes a
class T,
class Compare = std::less<T>,
class Allocator = std::allocator<T>,
- class GrowthPolicy = void>
+ class GrowthPolicy = void,
+ class Container = std::vector<T, Allocator>>
class sorted_vector_set
- : boost::totally_ordered1<
- sorted_vector_set<T,Compare,Allocator,GrowthPolicy>
- , detail::growth_policy_wrapper<GrowthPolicy> >
-{
- typedef std::vector<T,Allocator> ContainerT;
-
+ : boost::totally_ordered1<
+ sorted_vector_set<T, Compare, Allocator, GrowthPolicy>,
+ detail::growth_policy_wrapper<GrowthPolicy>> {
detail::growth_policy_wrapper<GrowthPolicy>&
get_growth_policy() { return *this; }
+ template <typename K, typename V, typename C = Compare>
+ using if_is_transparent =
+ _t<detail::sorted_vector_enable_if_is_transparent<void, C, K, V>>;
+
public:
typedef T value_type;
typedef T key_type;
typedef Compare key_compare;
typedef Compare value_compare;
- typedef typename ContainerT::pointer pointer;
- typedef typename ContainerT::reference reference;
- typedef typename ContainerT::const_reference const_reference;
+ typedef typename Container::pointer pointer;
+ typedef typename Container::reference reference;
+ typedef typename Container::const_reference const_reference;
/*
* XXX: Our normal iterator ought to also be a constant iterator
* (cf. Defect Report 103 for std::set), but this is a bit more of a
* pain.
*/
- typedef typename ContainerT::iterator iterator;
- typedef typename ContainerT::const_iterator const_iterator;
- typedef typename ContainerT::difference_type difference_type;
- typedef typename ContainerT::size_type size_type;
- typedef typename ContainerT::reverse_iterator reverse_iterator;
- typedef typename ContainerT::const_reverse_iterator const_reverse_iterator;
+ typedef typename Container::iterator iterator;
+ typedef typename Container::const_iterator const_iterator;
+ typedef typename Container::difference_type difference_type;
+ typedef typename Container::size_type size_type;
+ typedef typename Container::reverse_iterator reverse_iterator;
+ typedef typename Container::const_reverse_iterator const_reverse_iterator;
explicit sorted_vector_set(const Compare& comp = Compare(),
const Allocator& alloc = Allocator())
// those performed by the caller. (The iterator range constructor performs at
// least one allocation).
//
- // Note that `sorted_vector_set(const ContainerT& container)` is not provided,
+ // Note that `sorted_vector_set(const Container& container)` is not provided,
// since the purpose of this constructor is to avoid an unnecessary copy.
explicit sorted_vector_set(
- ContainerT&& container,
+ Container&& container,
const Compare& comp = Compare())
: m_(comp, container.get_allocator()) {
std::sort(container.begin(), container.end(), value_comp());
}
iterator find(const key_type& key) {
- iterator it = lower_bound(key);
- if (it == end() || !key_comp()(key, *it)) {
- return it;
- }
- return end();
+ return find(*this, key);
}
const_iterator find(const key_type& key) const {
- const_iterator it = lower_bound(key);
- if (it == end() || !key_comp()(key, *it)) {
- return it;
- }
- return end();
+ return find(*this, key);
+ }
+
+ template <typename K>
+ if_is_transparent<K, iterator> find(const K& key) {
+ return find(*this, key);
+ }
+
+ template <typename K>
+ if_is_transparent<K, const_iterator> find(const K& key) const {
+ return find(*this, key);
}
size_type count(const key_type& key) const {
return find(key) == end() ? 0 : 1;
}
+ template <typename K>
+ if_is_transparent<K, size_type> count(const K& key) const {
+ return find(key) == end() ? 0 : 1;
+ }
+
iterator lower_bound(const key_type& key) {
return std::lower_bound(begin(), end(), key, key_comp());
}
return std::lower_bound(begin(), end(), key, key_comp());
}
+ template <typename K>
+ if_is_transparent<K, iterator> lower_bound(const K& key) {
+ return std::lower_bound(begin(), end(), key, key_comp());
+ }
+
+ template <typename K>
+ if_is_transparent<K, const_iterator> lower_bound(const K& key) const {
+ return std::lower_bound(begin(), end(), key, key_comp());
+ }
+
iterator upper_bound(const key_type& key) {
return std::upper_bound(begin(), end(), key, key_comp());
}
return std::upper_bound(begin(), end(), key, key_comp());
}
- std::pair<iterator,iterator> equal_range(const key_type& key) {
+ template <typename K>
+ if_is_transparent<K, iterator> upper_bound(const K& key) {
+ return std::upper_bound(begin(), end(), key, key_comp());
+ }
+
+ template <typename K>
+ if_is_transparent<K, const_iterator> upper_bound(const K& key) const {
+ return std::upper_bound(begin(), end(), key, key_comp());
+ }
+
+ std::pair<iterator, iterator> equal_range(const key_type& key) {
return std::equal_range(begin(), end(), key, key_comp());
}
- std::pair<const_iterator,const_iterator>
- equal_range(const key_type& key) const {
+ std::pair<const_iterator, const_iterator> equal_range(
+ const key_type& key) const {
+ return std::equal_range(begin(), end(), key, key_comp());
+ }
+
+ template <typename K>
+ if_is_transparent<K, std::pair<iterator, iterator>> equal_range(
+ const K& key) {
+ return std::equal_range(begin(), end(), key, key_comp());
+ }
+
+ template <typename K>
+ if_is_transparent<K, std::pair<const_iterator, const_iterator>> equal_range(
+ const K& key) const {
return std::equal_range(begin(), end(), key, key_comp());
}
: Compare(c)
, cont_(alloc)
{}
- ContainerT cont_;
+ Container cont_;
} m_;
+
+ template <typename Self>
+ using self_iterator_t = _t<
+ std::conditional<std::is_const<Self>::value, const_iterator, iterator>>;
+
+ template <typename Self, typename K>
+ static self_iterator_t<Self> find(Self& self, K const& key) {
+ auto end = self.end();
+ auto it = self.lower_bound(key);
+ if (it == end || !self.key_comp()(key, *it)) {
+ return it;
+ }
+ return end;
+ }
};
// Swap function that can be found using ADL.
class Value,
class Compare = std::less<Key>,
class Allocator = std::allocator<std::pair<Key, Value>>,
- class GrowthPolicy = void>
+ class GrowthPolicy = void,
+ class Container = std::vector<std::pair<Key, Value>, Allocator>>
class sorted_vector_map
- : boost::totally_ordered1<
- sorted_vector_map<Key,Value,Compare,Allocator,GrowthPolicy>
- , detail::growth_policy_wrapper<GrowthPolicy> >
-{
- typedef std::vector<std::pair<Key,Value>,Allocator> ContainerT;
-
+ : boost::totally_ordered1<
+ sorted_vector_map<Key, Value, Compare, Allocator, GrowthPolicy>,
+ detail::growth_policy_wrapper<GrowthPolicy>> {
detail::growth_policy_wrapper<GrowthPolicy>&
get_growth_policy() { return *this; }
+ template <typename K, typename V, typename C = Compare>
+ using if_is_transparent =
+ _t<detail::sorted_vector_enable_if_is_transparent<void, C, K, V>>;
+
public:
typedef Key key_type;
typedef Value mapped_type;
explicit value_compare(const Compare& c) : Compare(c) {}
};
- typedef typename ContainerT::pointer pointer;
- typedef typename ContainerT::reference reference;
- typedef typename ContainerT::const_reference const_reference;
- typedef typename ContainerT::iterator iterator;
- typedef typename ContainerT::const_iterator const_iterator;
- typedef typename ContainerT::difference_type difference_type;
- typedef typename ContainerT::size_type size_type;
- typedef typename ContainerT::reverse_iterator reverse_iterator;
- typedef typename ContainerT::const_reverse_iterator const_reverse_iterator;
+ typedef typename Container::pointer pointer;
+ typedef typename Container::reference reference;
+ typedef typename Container::const_reference const_reference;
+ typedef typename Container::iterator iterator;
+ typedef typename Container::const_iterator const_iterator;
+ typedef typename Container::difference_type difference_type;
+ typedef typename Container::size_type size_type;
+ typedef typename Container::reverse_iterator reverse_iterator;
+ typedef typename Container::const_reverse_iterator const_reverse_iterator;
explicit sorted_vector_map(const Compare& comp = Compare(),
const Allocator& alloc = Allocator())
// those performed by the caller. (The iterator range constructor performs at
// least one allocation).
//
- // Note that `sorted_vector_map(const ContainerT& container)` is not provided,
+ // Note that `sorted_vector_map(const Container& container)` is not provided,
// since the purpose of this constructor is to avoid an unnecessary copy.
explicit sorted_vector_map(
- ContainerT&& container,
+ Container&& container,
const Compare& comp = Compare())
: m_(value_compare(comp), container.get_allocator()) {
std::sort(container.begin(), container.end(), value_comp());
}
iterator find(const key_type& key) {
- iterator it = lower_bound(key);
- if (it == end() || !key_comp()(key, it->first)) {
- return it;
- }
- return end();
+ return find(*this, key);
}
const_iterator find(const key_type& key) const {
- const_iterator it = lower_bound(key);
- if (it == end() || !key_comp()(key, it->first)) {
- return it;
- }
- return end();
+ return find(*this, key);
+ }
+
+ template <typename K>
+ if_is_transparent<K, iterator> find(const K& key) {
+ return find(*this, key);
+ }
+
+ template <typename K>
+ if_is_transparent<K, const_iterator> find(const K& key) const {
+ return find(*this, key);
}
mapped_type& at(const key_type& key) {
return find(key) == end() ? 0 : 1;
}
+ template <typename K>
+ if_is_transparent<K, size_type> count(const K& key) const {
+ return find(key) == end() ? 0 : 1;
+ }
+
iterator lower_bound(const key_type& key) {
- auto c = key_comp();
- auto f = [&](const value_type& a, const key_type& b) {
- return c(a.first, b);
- };
- return std::lower_bound(begin(), end(), key, f);
+ return lower_bound(*this, key);
}
const_iterator lower_bound(const key_type& key) const {
- auto c = key_comp();
- auto f = [&](const value_type& a, const key_type& b) {
- return c(a.first, b);
- };
- return std::lower_bound(begin(), end(), key, f);
+ return lower_bound(*this, key);
+ }
+
+ template <typename K>
+ if_is_transparent<K, iterator> lower_bound(const K& key) {
+ return lower_bound(*this, key);
+ }
+
+ template <typename K>
+ if_is_transparent<K, const_iterator> lower_bound(const K& key) const {
+ return lower_bound(*this, key);
}
iterator upper_bound(const key_type& key) {
- auto c = key_comp();
- auto f = [&](const key_type& a, const value_type& b) {
- return c(a, b.first);
- };
- return std::upper_bound(begin(), end(), key, f);
+ return upper_bound(*this, key);
}
const_iterator upper_bound(const key_type& key) const {
- auto c = key_comp();
- auto f = [&](const key_type& a, const value_type& b) {
- return c(a, b.first);
- };
- return std::upper_bound(begin(), end(), key, f);
+ return upper_bound(*this, key);
}
- std::pair<iterator,iterator> equal_range(const key_type& key) {
- // Note: std::equal_range can't be passed a functor that takes
- // argument types different from the iterator value_type, so we
- // have to do this.
- iterator low = lower_bound(key);
- auto c = key_comp();
- auto f = [&](const key_type& a, const value_type& b) {
- return c(a, b.first);
- };
- iterator high = std::upper_bound(low, end(), key, f);
- return std::make_pair(low, high);
+ template <typename K>
+ if_is_transparent<K, iterator> upper_bound(const K& key) {
+ return upper_bound(*this, key);
+ }
+
+ template <typename K>
+ if_is_transparent<K, const_iterator> upper_bound(const K& key) const {
+ return upper_bound(*this, key);
+ }
+
+ std::pair<iterator, iterator> equal_range(const key_type& key) {
+ return equal_range(*this, key);
}
- std::pair<const_iterator,const_iterator>
- equal_range(const key_type& key) const {
- return const_cast<sorted_vector_map*>(this)->equal_range(key);
+ std::pair<const_iterator, const_iterator> equal_range(
+ const key_type& key) const {
+ return equal_range(*this, key);
+ }
+
+ template <typename K>
+ if_is_transparent<K, std::pair<iterator, iterator>> equal_range(
+ const K& key) {
+ return equal_range(*this, key);
+ }
+
+ template <typename K>
+ if_is_transparent<K, std::pair<const_iterator, const_iterator>> equal_range(
+ const K& key) const {
+ return equal_range(*this, key);
}
// Nothrow as long as swap() on the Compare type is nothrow.
: value_compare(c)
, cont_(alloc)
{}
- ContainerT cont_;
+ Container cont_;
} m_;
+
+ template <typename Self>
+ using self_iterator_t = _t<
+ std::conditional<std::is_const<Self>::value, const_iterator, iterator>>;
+
+ template <typename Self, typename K>
+ static self_iterator_t<Self> find(Self& self, K const& key) {
+ auto end = self.end();
+ auto it = self.lower_bound(key);
+ if (it == end || !self.key_comp()(key, it->first)) {
+ return it;
+ }
+ return end;
+ }
+
+ template <typename Self, typename K>
+ static self_iterator_t<Self> lower_bound(Self& self, K const& key) {
+ auto f = [c = self.key_comp()](value_type const& a, K const& b) {
+ return c(a.first, b);
+ };
+ return std::lower_bound(self.begin(), self.end(), key, f);
+ }
+
+ template <typename Self, typename K>
+ static self_iterator_t<Self> upper_bound(Self& self, K const& key) {
+ auto f = [c = self.key_comp()](K const& a, value_type const& b) {
+ return c(a, b.first);
+ };
+ return std::upper_bound(self.begin(), self.end(), key, f);
+ }
+
+ template <typename Self, typename K>
+ static std::pair<self_iterator_t<Self>, self_iterator_t<Self>> equal_range(
+ Self& self,
+ K const& key) {
+ // Note: std::equal_range can't be passed a functor that takes
+ // argument types different from the iterator value_type, so we
+ // have to do this.
+ return {lower_bound(self, key), upper_bound(self, key)};
+ }
};
// Swap function that can be found using ADL.
//////////////////////////////////////////////////////////////////////
-}
+} // namespace folly
projects / folly.git / blobdiff