projected_set.hpp

Go to the documentation of this file.

#pragma once
 
/// @file userver/utils/projected_set.hpp
/// @brief @copybrief utils::ProjectedUnorderedSet
 
#include <functional>
#include <set>
#include <type_traits>
#include <unordered_set>
 
USERVER_NAMESPACE_BEGIN
 
namespace utils {
 
namespace impl::projected_set {
 
template <typename Raw, auto Projection>
using ProjectionResult = std::decay_t<std::invoke_result_t<decltype(Projection), const Raw&>>;
 
template <typename Raw, auto Projection, typename ResultHash>
using DefaultedResultHash =
    std::conditional_t<std::is_void_v<ResultHash>, std::hash<ProjectionResult<Raw, Projection>>, ResultHash>;
 
template <typename Raw, auto Projection, typename ResultHash>
struct Hash : public DefaultedResultHash<Raw, Projection, ResultHash> {
    using is_transparent [[maybe_unused]] = void;
    using Base = DefaultedResultHash<Raw, Projection, ResultHash>;
 
    auto operator()(const Raw& value) const noexcept { return Base::operator()(std::invoke(Projection, value)); }
 
    using Base::operator();
};
 
template <typename Raw, auto Projection, typename ResultCompare>
struct Compare : public ResultCompare {
    using is_transparent [[maybe_unused]] = void;
 
    auto operator()(const Raw& lhs, const Raw& rhs) const noexcept {
        return ResultCompare::operator()(std::invoke(Projection, lhs), std::invoke(Projection, rhs));
    }
 
    template <typename T>
    auto operator()(const Raw& lhs, const T& rhs) const noexcept {
        return ResultCompare::operator()(std::invoke(Projection, lhs), rhs);
    }
 
    template <typename T>
    auto operator()(const T& lhs, const Raw& rhs) const noexcept {
        return ResultCompare::operator()(lhs, std::invoke(Projection, rhs));
    }
 
    template <typename T, typename U>
    auto operator()(const T& lhs, const U& rhs) const noexcept {
        return ResultCompare::operator()(lhs, rhs);
    }
};
 
template <typename Set, typename Value>
void DoInsert(Set& set, Value&& value) {
    const auto [iter, success] = set.insert(std::forward<Value>(value));
    if (!success) {
        using SetValue = std::decay_t<decltype(*iter)>;
        // 'const_cast' is safe here, because the new key compares equal to the
        // old one and should have the same ordering (or hash) as the old one.
        // NOLINTNEXTLINE(cppcoreguidelines-pro-type-const-cast)
        const_cast<SetValue&>(*iter) = std::forward<Value>(value);
    }
}
 
}  // namespace impl::projected_set
 
/// @ingroup userver_universal userver_containers
/// @brief A `std::unordered_set` that compares its elements (of type @a Value)
/// based on their @a Projection. It allows to create, essentially, an
/// equivalent of `std::unordered_map` where keys are stored inside values.
///
/// Usage example:
/// @snippet utils/projected_set_test.cpp  user
/// @snippet utils/projected_set_test.cpp  usage
template <
    typename Value,
    auto Projection,
    typename Hash = void,
    typename Equal = std::equal_to<>,
    typename Allocator = std::allocator<Value>>
using ProjectedUnorderedSet = std::unordered_set<
    Value,
    impl::projected_set::Hash<Value, Projection, Hash>,
    impl::projected_set::Compare<Value, Projection, Equal>,
    Allocator>;
 
/// @ingroup userver_universal userver_containers
/// @brief Same as ProjectedUnorderedSet, but for `std::set`.
template <typename Value, auto Projection, typename Compare = std::less<>, typename Allocator = std::allocator<Value>>
using ProjectedSet = std::set<Value, impl::projected_set::Compare<Value, Projection, Compare>, Allocator>;
 
/// @brief An equivalent of `std::unordered_map::insert_or_assign` for
/// utils::ProjectedUnorderedSet and utils::ProjectedSet.
template <typename Container, typename Value>
void ProjectedInsertOrAssign(Container& set, Value&& value) {
    impl::projected_set::DoInsert(set, std::forward<Value>(value));
}
 
namespace impl::projected_set {
 
// Comparing Projected*Set results in only Projections being compared, which
// breaks value semantics. Unfortunately, if we define them as aliases of
// std::*set, we can't have operator== compare full values. The least bad
// decision in this case is to prohibit the comparison.
template <
    typename V1,
    const auto& P1,
    typename H1,
    typename E1,
    typename A1,
    typename V2,
    const auto& P2,
    typename H2,
    typename E2,
    typename A2>
void operator==(
    const ProjectedUnorderedSet<V1, P1, H1, E1, A1>& lhs,
    const ProjectedUnorderedSet<V2, P2, H2, E2, A2>& rhs
) = delete;
 
template <
    typename V1,
    const auto& P1,
    typename H1,
    typename E1,
    typename A1,
    typename V2,
    const auto& P2,
    typename H2,
    typename E2,
    typename A2>
void operator!=(
    const ProjectedUnorderedSet<V1, P1, H1, E1, A1>& lhs,
    const ProjectedUnorderedSet<V2, P2, H2, E2, A2>& rhs
) = delete;
 
template <typename V1, const auto& P1, typename C1, typename A1, typename V2, const auto& P2, typename C2, typename A2>
void operator==(const ProjectedSet<V1, P1, C1, A1>& lhs, const ProjectedSet<V2, P2, C2, A2>& rhs) = delete;
 
template <typename V1, const auto& P1, typename C1, typename A1, typename V2, const auto& P2, typename C2, typename A2>
void operator!=(const ProjectedSet<V1, P1, C1, A1>& lhs, const ProjectedSet<V2, P2, C2, A2>& rhs) = delete;
 
}  // namespace impl::projected_set
 
}  // namespace utils
 
USERVER_NAMESPACE_END