/*
- * Copyright 2017 Facebook, Inc.
+ * Copyright 2011-present Facebook, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
#pragma once
#include <algorithm>
+#include <cassert>
#include <initializer_list>
#include <iterator>
#include <stdexcept>
#include <boost/operators.hpp>
#include <folly/Traits.h>
+#include <folly/Utility.h>
#include <folly/portability/BitsFunctexcept.h>
namespace folly {
cont.end());
}
}
+
+template <typename Container, typename Compare>
+Container&& as_sorted(Container&& container, Compare const& comp) {
+ using namespace std;
+ std::sort(begin(container), end(container), comp);
+ return static_cast<Container&&>(container);
+}
} // 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; }
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())
+ : sorted_vector_set(
+ presorted,
+ detail::as_sorted(std::move(container), comp),
+ comp) {}
+
+ // Construct a sorted_vector_set by stealing the storage of a prefilled
+ // container. The container must be sorted, as presorted_t hints. Supports
+ // bulk construction of sorted_vector_set with zero allocations, not counting
+ // those performed by the caller. (The iterator range constructor performs at
+ // least one allocation).
+ //
+ // Note that `sorted_vector_set(presorted_t, const Container& container)` is
+ // not provided, since the purpose of this constructor is to avoid an extra
+ // copy.
+ sorted_vector_set(
+ presorted_t,
+ Container&& container,
const Compare& comp = Compare())
: m_(comp, container.get_allocator()) {
- std::sort(container.begin(), container.end(), value_comp());
+ assert(std::is_sorted(container.begin(), container.end(), value_comp()));
m_.cont_.swap(container);
}
: Compare(c)
, cont_(alloc)
{}
- ContainerT cont_;
+ Container cont_;
} m_;
template <typename Self>
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; }
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())
+ : sorted_vector_map(
+ presorted,
+ detail::as_sorted(std::move(container), value_compare(comp)),
+ comp) {}
+
+ // Construct a sorted_vector_map by stealing the storage of a prefilled
+ // container. The container must be sorted, as presorted_t hints. S supports
+ // bulk construction of sorted_vector_map with zero allocations, not counting
+ // those performed by the caller. (The iterator range constructor performs at
+ // least one allocation).
+ //
+ // Note that `sorted_vector_map(presorted_t, const Container& container)` is
+ // not provided, since the purpose of this constructor is to avoid an extra
+ // copy.
+ sorted_vector_map(
+ presorted_t,
+ Container&& container,
const Compare& comp = Compare())
: m_(value_compare(comp), container.get_allocator()) {
- std::sort(container.begin(), container.end(), value_comp());
+ assert(std::is_sorted(container.begin(), container.end(), value_comp()));
m_.cont_.swap(container);
}
: value_compare(c)
, cont_(alloc)
{}
- ContainerT cont_;
+ Container cont_;
} m_;
template <typename Self>
projects / folly.git / blobdiff