3 Defines `boost::hana::detail::has_duplicates`.
5 @copyright Louis Dionne 2013-2016
6 Distributed under the Boost Software License, Version 1.0.
7 (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
10 #ifndef BOOST_HANA_DETAIL_HAS_DUPLICATES_HPP
11 #define BOOST_HANA_DETAIL_HAS_DUPLICATES_HPP
13 #include <boost/hana/config.hpp>
14 #include <boost/hana/detail/fast_and.hpp>
15 #include <boost/hana/equal.hpp>
21 BOOST_HANA_NAMESPACE_BEGIN namespace detail {
22 template <typename T, typename ...U>
23 constexpr std::size_t pack_count() {
25 std::size_t expand[] = {0, // avoid empty array
26 (decltype(hana::equal(std::declval<T>(), std::declval<U>()))::value
35 //! @ingroup group-details
36 //! Returns whether any of the `T`s are duplicate w.r.t. `hana::equal`.
38 //! In particular, this does not check whether all of the `T`s are unique
39 //! as _types_, but rather whether they are unique when compared as
40 //! `hana::equal(std::declval<T>(), std::declval<U>())`. This assumes
41 //! the comparison to return an `IntegralConstant` that can be explicitly
42 //! converted to `bool`.
45 //! Since this utility is mostly used in assertions to check that there
46 //! are no duplicates in a sequence, we expect it to return `false` most
47 //! of the time (otherwise we will assert). Hence, this implementation is
48 //! biased towards the fact that we __will__ have to compare every pair of
49 //! elements in most cases, and it does not try to be lazy.
52 //! This implementation is O(n^2). We could do it in O(n), but that would
53 //! require a more elaborate setup including storage with O(1) lookup
54 //! (which could be based on a compile-time hash). If we implement such
55 //! storage for associative sequences, we could use it to optimize this.
56 template <typename ...T>
57 struct has_duplicates {
58 static constexpr bool value =
60 !detail::fast_and<(detail::pack_count<T, T...>() == 1)...>::value
63 } BOOST_HANA_NAMESPACE_END
65 #endif // !BOOST_HANA_DETAIL_HAS_DUPLICATES_HPP