/*
- * 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
// 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(
+ 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);
}
// 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(
+ 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);
}