Return to Revisions

Consider a drastic change of interface - instead of sorting elements in-place, it might be better to return a histogram object with vector-like access:

histogram sorted(const std::input_range& auto nums);

We could implement the histogram as

#include <iterator>
#include <numeric>
#include <ranges>

// Special case histogram class that counts values that are 0, 1 or 2.
class histogram_012
{
    std::array<std::size_t,3> count{{ 0, 0, 0 }};

public:
    struct const_iterator
    {
        using difference_type = std::ptrdiff_t;
        using value_type = int;
        using pointer = int*;
        using reference = int&;
        using iterator_category = std::input_iterator_tag;

        const histogram_012 *p;
        std::size_t pos;

        constexpr auto operator<=>(const const_iterator& other) const = default;

        const_iterator& operator++()
        {
            ++pos; return *this;
        }

        auto operator*() const
        {
            // This is just for exposition; it's not efficient
            auto n = pos;
            int  i = 0;
            for (auto c: p->count) {
                if (n < c) { return i; }
                n -= c;
                ++i;
            }
            // out-of-range (undefined)
            return 0;
        }
    };

    template<std::ranges::input_range C>
    requires std::is_same_v<int, std::ranges::range_value_t<C>>
    explicit constexpr histogram_012(C const& nums)
    {
        std::size_t total = 0;
        for (int n: nums) {
            count[0] += (n == 0);
            count[1] += (n == 1);
            ++total;
        }
        count[2] = total - count[0] - count[1];
    }

    // Minimal container interface - this needs completing
    constexpr auto size() const { return std::accumulate(count.begin(), count.end(), std::size_t{}); }
    constexpr const_iterator begin() const { return {this, 0}; }
    constexpr const_iterator end() const { return {this, size()}; }
};

and sorted() as

constexpr auto sorted(auto const& nums) { return histogram_012{nums}; }

Simple demo:

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
int main()
{
    std::vector<int> values = {0,2,1,2,1};
    auto const sorted_values = sorted(values);
    std::copy(sorted_values.begin(), sorted_values.end(),
              std::ostream_iterator<int>(std::cout, ", "));
    std::cout << '\n';
}

Credit to Peter Cordes for suggesting this approach, in comments to other answers.

An exercise for the interested reader is to create a generalised version that histograms a fixed set of values of a given type, i.e.

template<std::totally_ordered T, T... values> class histogram