hana/detail/has_duplicates.hpp

0001 /*!
0002 @file
0003 Defines `boost::hana::detail::has_duplicates`.
0004
0005 Copyright Louis Dionne 2013-2022
0006 Distributed under the Boost Software License, Version 1.0.
0007 (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
0008  */
0009
0010 #ifndef BOOST_HANA_DETAIL_HAS_DUPLICATES_HPP
0011 #define BOOST_HANA_DETAIL_HAS_DUPLICATES_HPP
0012
0013 #include <boost/hana/config.hpp>
0014 #include <boost/hana/detail/fast_and.hpp>
0015 #include <boost/hana/equal.hpp>
0016
0017 #include <cstddef>
0018 #include <utility>
0019
0020
0021 namespace boost { namespace hana { namespace detail {
0022     template <typename T, typename ...U>
0023     constexpr std::size_t pack_count() {
0024         std::size_t c = 0;
0025         std::size_t expand[] = {0, // avoid empty array
0026             (decltype(hana::equal(std::declval<T>(), std::declval<U>()))::value
0027                 ? ++c
0028                 : c)...
0029         };
0030         (void)expand;
0031
0032         return c;
0033     }
0034
0035     //! @ingroup group-details
0036     //! Returns whether any of the `T`s are duplicate w.r.t. `hana::equal`.
0037     //!
0038     //! In particular, this does not check whether all of the `T`s are unique
0039     //! as _types_, but rather whether they are unique when compared as
0040     //! `hana::equal(std::declval<T>(), std::declval<U>())`. This assumes
0041     //! the comparison to return an `IntegralConstant` that can be explicitly
0042     //! converted to `bool`.
0043     //!
0044     //! @note
0045     //! Since this utility is mostly used in assertions to check that there
0046     //! are no duplicates in a sequence, we expect it to return `false` most
0047     //! of the time (otherwise we will assert). Hence, this implementation is
0048     //! biased towards the fact that we __will__ have to compare every pair of
0049     //! elements in most cases, and it does not try to be lazy.
0050     //!
0051     //! @todo
0052     //! This implementation is O(n^2). We could do it in O(n), but that would
0053     //! require a more elaborate setup including storage with O(1) lookup
0054     //! (which could be based on a compile-time hash). If we implement such
0055     //! storage for associative sequences, we could use it to optimize this.
0056     template <typename ...T>
0057     struct has_duplicates {
0058         static constexpr bool value =
0059             sizeof...(T) > 0 &&
0060             !detail::fast_and<(detail::pack_count<T, T...>() == 1)...>::value
0061         ;
0062     };
0063 } }} // end namespace boost::hana
0064
0065 #endif // !BOOST_HANA_DETAIL_HAS_DUPLICATES_HPP