Niebloids

Overview

The C++20 ranges library rewrites the standard algorithms — std::ranges::sort, std::ranges::find, std::ranges::transform, and the rest — not as function templates but as callable objects of uniquely-named struct types. The design was championed by Eric Niebler (hence the informal name) and resolves two persistent problems with the classic <algorithm> API.

Problem 1: Unintended ADL. Classic std::sort is a function template. Function templates participate in ADL, which means a sort in a user namespace can be found accidentally, or explicit using std::sort can trigger lookup collisions that produce hard-to-diagnose overload ambiguity. Niebloids, being function objects rather than functions, are never found by ADL — the call site always resolves to exactly the object named.

Problem 2: Implicit swap coupling. std::sort (C++98) uses ADL swap to move elements. If a type provides a namespace-scoped swap, it gets picked up silently. std::ranges::sort, as a niebloid, uses std::ranges::iter_swap instead — a customization point object with explicit, priority-ordered lookup. This makes the coupling visible and deliberate rather than implicit.

The standard mandates in [algorithm.requirements] that std::ranges algorithm names have the semantics of niebloids: they are not function templates, they do not participate in ADL, and they cannot be found by unqualified or argument-dependent lookup even if a using-declaration brings them into scope.

Niebloids vs. Customization Point Objects

A related but distinct pattern is the customization point object (CPO): std::ranges::begin, std::ranges::end, std::ranges::swap. CPOs are also inline constexpr function objects, but their job is to provide a customizable hook — user types opt in by providing specific overloads the CPO will find. Niebloids are the opposite: non-customizable algorithm implementations that intentionally block user-namespace interference.

Syntax

The canonical implementation skeleton for a niebloid:

// C++20
namespace std::ranges {

    struct sort_fn {
        template<
            std::random_access_iterator I,
            std::sentinel_for<I> S,            // heterogeneous sentinel — C++20
            class Comp = ranges::less,
            class Proj = std::identity         // projection parameter — C++20
        >
        requires std::sortable<I, Comp, Proj>
        constexpr I
        operator()(I first, S last,
                   Comp comp = {}, Proj proj = {}) const;

        template<
            ranges::random_access_range R,
            class Comp = ranges::less,
            class Proj = std::identity
        >
        requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
        constexpr ranges::borrowed_iterator_t<R>
        operator()(R&& r, Comp comp = {}, Proj proj = {}) const;
    };

    inline constexpr sort_fn sort{};  // the niebloid — not a function
}

Key elements:

• inline constexpr object — not a function, not a function template. Taking its address is ill-formed.
• Templated operator() const — template arguments are deduced from call-site types; the struct itself is not a template.
• requires constraints — C++20 concepts replace SFINAE. Failed constraints produce readable diagnostics.
• Projection parameter — Proj transforms each element before the comparator sees it, a capability absent from the classic API.

Examples

Basic usage and projection syntax

#include <algorithm>
#include <vector>
#include <string>
// C++20

struct Employee {
    std::string name;
    double salary;
};

int main() {
    std::vector<int> nums{5, 3, 1, 4, 2};

    std::ranges::sort(nums);                          // ascending
    std::ranges::sort(nums, std::ranges::greater{});  // descending

    std::vector<Employee> staff{
        {"Alice", 95000}, {"Bob", 72000}, {"Carol", 110000}
    };

    // C++17 style — comparator must unpack both sides
    std::sort(staff.begin(), staff.end(),
        [](const Employee& a, const Employee& b){ return a.salary < b.salary; });

    // C++20 — projection cleanly separates "how to extract" from "how to compare"
    std::ranges::sort(staff, {}, &Employee::salary);

    // multi-key sort: primary by salary desc, secondary by name asc
    std::ranges::sort(staff, std::ranges::greater{}, &Employee::salary);
}

Heterogeneous sentinels

Niebloids accept a sentinel type distinct from the iterator type — classic std::find requires both to be the same:

// C++20
const char* raw = "find the comma, please";

struct comma_sentinel {
    friend bool operator==(const char* p, comma_sentinel) {
        return *p == ',' || *p == '\0';
    }
};

auto it = std::ranges::find(raw, comma_sentinel{}, 'i');
// works with heterogeneous I / S — ill-formed with std::find

Writing your own niebloid

When building a library algorithm that must interoperate cleanly with ranges code, replicate the pattern rather than writing a function template:

// C++20
namespace mylib {

    struct adjacent_transform_fn {
        template<
            std::forward_iterator I,
            std::sentinel_for<I> S,
            std::weakly_incrementable O,
            std::copy_constructible BinaryOp
        >
        requires std::indirectly_writable<
                     O, std::indirect_result_t<BinaryOp&, I, I>>
        constexpr O
        operator()(I first, S last, O out, BinaryOp op) const {
            if (first == last) return out;
            auto prev = first;
            while (++first != last) {
                *out++ = op(*prev, *first);
                prev = first;
            }
            return out;
        }

        template<std::ranges::forward_range R,
                 std::weakly_incrementable O,
                 std::copy_constructible BinaryOp>
        constexpr O
        operator()(R&& r, O out, BinaryOp op) const {
            return (*this)(std::ranges::begin(r), std::ranges::end(r),
                           std::move(out), std::move(op));
        }
    };

    inline constexpr adjacent_transform_fn adjacent_transform{};
}

// Call site — fully qualified, no ADL, no surprises
std::vector<int> src{1, 2, 3, 4, 5};
std::vector<int> dst;
mylib::adjacent_transform(src, std::back_inserter(dst), std::plus{});
// dst == {3, 5, 7, 9}

Best Practices

Always qualify the namespace at the call site. Write std::ranges::sort rather than using namespace std::ranges; sort(...). The entire purpose of the design is deterministic, non-ADL lookup — don't undermine it with a using directive.

Prefer projections over comparator lambdas. std::ranges::sort(v, {}, &T::key) outclasses a two-argument lambda in readability and composes cleanly when you need to chain transformations through std::views.

Prefer range overloads. std::ranges::sort(v) over std::ranges::sort(v.begin(), v.end()). The range overload handles sentinel extraction, supports borrowed_range tracking, and is less to type.

Implement library algorithms as niebloids, not function templates. Function templates are found by ADL and can be shadowed or create ambiguity with user-namespace names. A function object in your namespace is always fully qualified at the call site.

Common Pitfalls

Taking the address of a ranges algorithm. std::ranges::sort is an object, not a function. Storing it in a function<> or a function pointer fails:

// ill-formed — C++20
auto* p = &std::ranges::sort;     // error: not a function

// correct — wrap in a lambda
auto sorter = [](auto&& r){ std::ranges::sort(r); };
std::function<void(std::vector<int>&)> f = sorter; // fine

Assuming ADL extends niebloids. Unlike classic algorithms where using std::sort; sort(v.begin(), v.end()) can be overridden by a user-namespace sort found via ADL, a using-declaration for a niebloid does not open the door to ADL extension. If you need a customization hook, you need a CPO, not a niebloid.

Mixing std::sort and std::ranges::sort swap semantics. std::sort uses ADL swap; std::ranges::sort uses std::ranges::iter_swap. If your type customizes swap in its namespace but does not also satisfy std::swappable via the ranges mechanism, the two algorithms may behave differently. Test with both or commit to one API.

Misreading sentinel mismatch errors. Because niebloids accept sentinel_for<I> S, a type mismatch at the second argument produces a concept-constraint failure rather than a direct type error. The message will mention std::sentinel_for — look for the iterator type deduced from the first argument and verify the second argument models sentinel_for that type.

Implementing a Custom CPO

A customization point object (CPO) is a function object that dispatches in priority order: member function first, then ADL free function, then a default fallback. This is the pattern used by std::ranges::begin, std::ranges::swap, and every extensible hook in the ranges library.

// C++20 — a reusable "serialize" CPO
namespace mylib {

    // Helper: detect member .serialize(out)
    template<typename T, typename Out>
    concept has_member_serialize = requires(const T& v, Out& out) {
        v.serialize(out);
    };

    // Helper: detect free serialize(v, out) findable by ADL
    namespace _adl_serialize {
        void serialize() = delete; // poison pill — blocks std::serialize if it existed
        template<typename T, typename Out>
        concept has_adl_serialize = requires(const T& v, Out& out) {
            serialize(v, out);  // unqualified: ADL fires here
        };
    }

    struct serialize_fn {
        // Priority 1: member function
        template<typename T, typename Out>
        requires has_member_serialize<T, Out>
        constexpr void operator()(const T& v, Out& out) const {
            v.serialize(out);
        }

        // Priority 2: ADL free function (only when no member)
        template<typename T, typename Out>
        requires (!has_member_serialize<T, Out> &&
                  _adl_serialize::has_adl_serialize<T, Out>)
        constexpr void operator()(const T& v, Out& out) const {
            using namespace _adl_serialize;
            serialize(v, out);  // ADL finds user's overload
        }

        // Priority 3: default implementation
        template<typename T, typename Out>
        requires (!has_member_serialize<T, Out> &&
                  !_adl_serialize::has_adl_serialize<T, Out>)
        constexpr void operator()(const T& v, Out& out) const {
            // fallback: write a placeholder tag
            out << "[unserializable]";
        }
    };

    inline constexpr serialize_fn serialize{};

} // namespace mylib

User types opt in by adding either a member or a free function in their own namespace — the CPO finds the right one automatically:

// Option A: member function (highest priority)
struct Point {
    int x, y;
    void serialize(std::ostream& out) const { out << x << ' ' << y; }
};

// Option B: free function via ADL (no member needed)
namespace geom {
    struct Circle { double r; };
    void serialize(const Circle& c, std::ostream& out) { out << "Circle(" << c.r << ')'; }
}

// Both work through the same CPO:
mylib::serialize(Point{1, 2}, std::cout);        // calls Point::serialize
mylib::serialize(geom::Circle{3.0}, std::cout);  // found via ADL
mylib::serialize(42, std::cout);                 // fallback: [unserializable]

The key properties: callers always write mylib::serialize(...) — one name, deterministic lookup, no Two-Step incantation required.

The Poison Pill Trick

Without a poison pill, the ADL step inside a CPO can accidentally find a standard library function of the same name and pick it up as a "customization" for a type.

What goes wrong without a poison pill:

// Hypothetical CPO without poison pill — DANGEROUS
namespace mylib {
    namespace _detail {
        // No poison pill here!
        template<typename T>
        concept has_adl_swap = requires(T& a, T& b) {
            swap(a, b);  // unqualified lookup
        };
    }
}
// Problem: for std::vector<int>, ADL finds std::swap — the unconstrained
// C++14 version — which trivially satisfies has_adl_swap for every type.
// The CPO's "user customized" branch fires for ALL types, not just opted-in ones.

The fix — a = delete poison pill in the lookup namespace:

namespace mylib::_adl_swap {
    // Poison pill: a deleted function template in this namespace.
    // Partial ordering means an exact-match user overload beats it,
    // but std::swap (found via ADL on std types) is blocked because
    // unqualified lookup finds THIS deleted overload first.
    template<typename T>
    void swap(T&, T&) = delete;

    template<typename T>
    concept has_adl_swap = requires(T& a, T& b) {
        swap(a, b);  // now: finds deleted pill OR user's overload; std::swap blocked
    };
}

The poison pill works because:

1. The = deleted overload lives in the same namespace as the unqualified swap call.
2. It is found by ordinary unqualified lookup before ADL runs — so std::swap never enters the candidate set.
3. A user's more-specialized free function swap(MyType&, MyType&) wins over the generic template<typename T> pill by partial ordering, so opted-in types still work.

In the standard library, std::ranges::swap uses exactly this technique: a template<class T> void swap(T&&, T&&) = delete; inside the implementation namespace blocks the unconstrained std::swap from polluting the constraint check.

tag_invoke (P1895)

tag_invoke is a proposed (but not yet standardized) alternative CPO mechanism used by stdexec (the reference implementation of C++26 std::execution) and several other modern libraries. Instead of encoding dispatch priority inside each CPO's operator(), it unifies all customization through a single free function named tag_invoke.

The core pattern:

// P1895 tag_invoke pattern (library provides this once)
namespace std {
    struct tag_invoke_fn {
        template<typename Tag, typename... Args>
        constexpr auto operator()(Tag tag, Args&&... args) const
            noexcept(noexcept(tag_invoke(tag, std::forward<Args>(args)...)))
            -> decltype(tag_invoke(tag, std::forward<Args>(args)...))
        {
            return tag_invoke(tag, std::forward<Args>(args)...);
        }
    };
    inline constexpr tag_invoke_fn tag_invoke{};
}

// Library author defines a CPO tag type
struct serialize_t {
    template<typename T, typename Out>
    auto operator()(T&& v, Out& out) const {
        return std::tag_invoke(*this, std::forward<T>(v), out);
    }
};
inline constexpr serialize_t serialize{};

// User customizes by writing a free tag_invoke overload in their namespace
namespace geom {
    struct Circle { double r; };

    // First argument is the tag — this is how dispatch is keyed
    void tag_invoke(serialize_t, const Circle& c, std::ostream& out) {
        out << "Circle(" << c.r << ')';
    }
}

Niebloid/ADL-CPO vs. tag_invoke — comparison:

tag_invoke solves the "global name pollution" problem: because all customizations go through the single name tag_invoke, libraries never compete for names like serialize or swap in the global namespace. The tag type itself is the discriminator.

std::ranges CPOs vs. std Algorithms

The std::ranges versions of algorithms are niebloids (ADL-suppressed), while the std versions are function templates (ADL-enabled). This matters when iterators have std as an associated namespace:

std::sort is a function template: using namespace std; sort(v.begin(), v.end()) can accidentally dispatch to a user-namespace sort found via ADL if the iterator type is from that namespace. std::ranges::sort is an object — ADL never fires, and using namespace std::ranges; sort(v) always calls the ranges version.

When to Use Niebloids and CPOs in Your Own Library

Use a CPO (customizable, ADL-dispatching function object) when:

• Your library provides an extensibility hook — callers need to specialize behavior for their types.
• Examples: serialization, hashing, formatting, comparison, resource acquisition.
• The correct pattern is member-first, then ADL free function, then default (as shown above).

Use a niebloid (non-customizable, ADL-suppressing function object) when:

• You are providing an algorithm — the implementation is fixed, and you want to suppress ADL interference.
• You want using namespace mylib; algo(...) to behave identically to mylib::algo(...).
• Your library ships alongside other libraries that may define identically-named algorithms.

Use virtual dispatch instead when:

• Runtime polymorphism is needed — the concrete type is not known at compile time.
• The overhead of a vtable call is acceptable (or negligible) compared to the work done.

Use concepts constraints alone when:

• You want to restrict what types can call an operation, but not redirect to user-provided implementations.
• No customization is needed — the algorithm is closed and correct for any type satisfying the concept.

Use tag_invoke when:

• You are building a library ecosystem where many independent CPOs must coexist without name collisions (e.g., an execution framework like stdexec).
• You want all customizations to be greppable from one central overload set.

See Also

• std::ranges — all std::ranges::* algorithm names in <algorithm> are niebloids since C++20
• std::identity — the default projection (C++20, <functional>)
• std::ranges::less, std::ranges::greater — comparison objects used as default comparators in ranges algorithms; also niebloid-adjacent in design
• Customization point objects: std::ranges::begin, std::ranges::end, std::ranges::swap — the customizable counterpart to niebloids