10
\$\begingroup\$

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.

\$\endgroup\$
2
  • 4
    \$\begingroup\$ I'm talking from the ignorance but, would it be possible to combine constexpr with initializer lists so that you can achieve the same thing without having so many types? \$\endgroup\$ Mar 2, 2018 at 11:17
  • 3
    \$\begingroup\$ Since I cant edit my previous comment, I'll add it up here. I've tried myself and it is completely possible to do it with arrays. However, it's limited to C++17 onwards, due to operator[] not being constexpr until then. If you are interested you can check it out here: godbolt.org/g/qfnn54 (it seems not to have the SIMD problem you mention when using -O3). \$\endgroup\$ Mar 2, 2018 at 12:34

1 Answer 1

1
\$\begingroup\$

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()); }
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.