C++ library to compile-time merge sets to a single array

Question

I built this small library to create a compile-time assembled array from several hard-coded sequences (of unequal length) of a type T:

mergeable_set.hpp

#pragma once

template <typename T>
class mergeable {
public:
    template <T... Ts>
    struct set {
        static constexpr T values[] {Ts...};

        constexpr const auto& operator[](const int i) const noexcept { return values[i]; }
        constexpr auto size() const noexcept { return sizeof...(Ts); }

        class iterator {
        public:
            constexpr explicit iterator(set& _ref, const int i = 0) : ref{_ref}, index{i} {}
            constexpr iterator& operator++() noexcept { ++index; return *this; }
            constexpr bool      operator!=(const iterator& other) const noexcept { return index != other.index; }
            constexpr auto&     operator* () noexcept { return ref[index]; }
        private:
            set& ref;
            int index;
        };
        class citerator {
        public:
            constexpr citerator(const set& _ref, const int i) : ref{_ref}, index{i} {}
            constexpr citerator&  operator++() noexcept { ++index; return *this; }
            constexpr bool        operator!=(const citerator& other) const noexcept { return index != other.index; }
            constexpr const auto& operator* () const noexcept { return ref[index]; }
        private:
            const set& ref;
            int index;
        };
        constexpr iterator begin() noexcept { return iterator{*this, 0}; }
        constexpr citerator begin() const noexcept { return citerator{*this, 0}; }
        constexpr iterator end()   noexcept { return iterator{*this, sizeof...(Ts)}; }
        constexpr citerator end()   const noexcept { return citerator{*this, sizeof...(Ts)}; }
    };

private:
    template <typename, typename...> struct concat{};
    template<T... A, T... B>
    struct concat<set<A...>, set<B...>> {
        using type = set<A..., B...>;
    };
    template<T... A>
    struct concat<set<A...>> {
        using type = set<A...>;
    };

    template <typename...> struct _combine {};
    template <typename A, typename B, typename... C>
    struct _combine<A, B, C...> {
        using type = typename concat<A, typename _combine<B, C...>::type>::type;
    };
    template <typename A, typename B>
    struct _combine<A, B> {
        using type = typename concat<A, B>::type;
    };
    template <typename A>
    struct _combine<A> {
        using type = typename concat<A>::type;
    };

public:
    template <typename...U>
    using combine = typename _combine<U...>::type;
};

Usable like this:

#include "mergeable_set.hpp"

int main() {
    mergeable<int>::set<1, 2, 3> a;
    mergeable<int>::set<4, 5, 6> b;
    mergeable<int>::set<1, 2, 3> c;
    mergeable<int>::set<4, 5, 6> d;
    mergeable<int>::combine<decltype(a),
                            decltype(b),
                            decltype(c),
                            decltype(d)> z;

    int temp = 0;

    for (auto e : z) {
        temp += e;
    }

    volatile int l = temp;
}

With z behaving like a plain array (const int z[12]). Interestingly this exposes some strange behaviour in GCC. When compiling x86 code any array over 7 elements generates SIMD bulk add instructions. While this sounds great, disabling SSE actually compiles out all instructions, straight up to the final result. The latter is obviously preferable. Did I just hit a logic bug in GCC here?

A live example of this effect: https://godbolt.org/g/4LAJXV Remove -mno-sse to see the difference.

I'd love to hear what can be improved to make this into a more general purpose library.

Answer 1

The name is very misdirecting. This code seems to represent sequences rather than sets. For example, if we combine sets each containing just a single value, we'd expect the result to contain just that value, too. But this program (which requires corrected iterators - see below) demonstrates otherwise:

#include <iostream>
#include <string>

int main()
{
    using a = mergeable<char>::set<'a', 'a', 'a'>;
    static constexpr mergeable<char>::combine<a, a, a> aaa;
    std::cout << std::string{aaa.begin(), aaa.end()} << '\n';
}

Its output is aaaaaaaaa, rather than the a we would expect with actual sets.

---

The iterators don't work in many standard contexts (such as constructing a string from a pair of iterators). This is because we haven't provided the standard traits typenames:

    class const_iterator {
    public:
        using iterator_category = std::bidirectional_iterator_tag;
        using difference_type = std::ptrdiff_t;
        using value_type = T;
        using pointer = const value_type*;
        using reference = const value_type&;
        constexpr const_iterator(const set& _ref, const std::size_t i = 0) : ref{_ref}, index{i} {}
        constexpr bool operator!=(const const_iterator& other) const noexcept { return index != other.index; }
        constexpr const_iterator& operator++() noexcept { ++index; return *this; }
        constexpr const_iterator& operator--() noexcept { --index; return *this; }
        constexpr const auto& operator* () const noexcept { return ref[index]; }
    private:
        const set& ref;
        std::size_t index;
    };
    struct iterator {
    public:
        using iterator_category = std::bidirectional_iterator_tag;
        using difference_type = std::ptrdiff_t;
        using value_type = T;
        using pointer = value_type*;
        using reference = value_type&;
        constexpr explicit iterator(set& _ref, const std::size_t i = 0) : ref{_ref}, index{i} {}
        constexpr bool operator!=(const iterator& other) const noexcept { return index != other.index; }
        constexpr iterator& operator++() noexcept { ++index; return *this; }
        constexpr iterator& operator--() noexcept { --index; return *this; }
        constexpr auto& operator* () noexcept { return ref[index]; }
        constexpr operator const_iterator() const noexcept { return {ref, index}; }
    private:
        set& ref;
        std::size_t index;
    };

(I changed the const iterator to the conventional name that algorithms expect, and the index type to a more conventional unsigned type; I also added the implicit conversion from iterator to const iterator).

We're also missing const and reverse versions of the begin/end functions:

    constexpr iterator begin() noexcept { return {*this}; }
    constexpr const_iterator begin() const noexcept { return {*this}; }
    constexpr const_iterator cbegin() const noexcept { return begin(); }
    constexpr iterator end() noexcept { return {*this, size()}; }
    constexpr const_iterator end() const noexcept { return {*this, size()}; }
    constexpr const_iterator cend() const noexcept { return end(); }

    constexpr auto rbegin() noexcept { return std::make_reverse_iterator(end()); }
    constexpr auto rbegin() const noexcept { return std::make_reverse_iterator(end()); }
    constexpr auto crbegin() const noexcept { return std::make_reverse_iterator(end()); }

    constexpr auto rend() noexcept { return std::make_reverse_iterator(begin()); }
    constexpr auto rend() const noexcept { return std::make_reverse_iterator(begin()); }
    constexpr auto crend() const noexcept { return std::make_reverse_iterator(begin()); }