11
\$\begingroup\$

I want to implement something like C# Linq in C++

Currently only select and where is implemented, but others should be fairly easy if I can make a good structure.

The main concerns I have is I am not sure when to pass reference and when to pass value. Also how it works with different types (array type, lvalue, rvalue, const type, etc)

namespace linq {

    namespace detail
    {
        template <typename T>
        struct IteratorBase
        {
            virtual ~IteratorBase() {}

            virtual T operator *() const = 0;
            virtual IteratorBase & operator++() = 0; // prefix ++
            virtual bool operator==(const IteratorBase &other) const = 0;
            bool operator!=(const IteratorBase &other) const { return !(other == *this); }
        };

        template <typename T>
        struct Iterator : IteratorBase<T>
        {
            virtual std::unique_ptr<Iterator> copy() = 0;
        };

        template <typename T, typename InputIterator>
        struct IteratorImpl : Iterator<T>
        {
            IteratorImpl() : _it() {}
            IteratorImpl(const InputIterator &it) : _it(it) {}

            ~IteratorImpl() {}

            T operator *() const { return *_it; }
            IteratorBase<T> & operator++() { ++_it; return *this; };
            bool operator==(const IteratorBase<T> &other) const
            {
                const IteratorImpl *otherptr = dynamic_cast<const IteratorImpl *>(&other);
                if (otherptr) {
                    return _it == otherptr->_it;
                }
                return false;
            }

            std::unique_ptr<Iterator<T>> copy()
            {
                return std::unique_ptr<Iterator<T>>{ new IteratorImpl<T, InputIterator>(_it) };
            }

        private:
            InputIterator _it;
        };

        template <typename T>
        struct IteratorWrapper : IteratorBase<T>
        {
            template <typename InputIterator>
            IteratorWrapper(const InputIterator &it) : _it(new IteratorImpl<T, InputIterator>(it)) {}
            IteratorWrapper(const IteratorWrapper &other) : _it(other._it->copy()) {}

            ~IteratorWrapper() {}

            T operator *() const { return *(*_it); }
            IteratorBase<T> & operator++() { ++(*_it); return *this; }
            bool operator==(const IteratorBase<T> &other) const {
                const IteratorWrapper *otherptr = dynamic_cast<const IteratorWrapper *>(&other);
                if (otherptr) {
                    return (*otherptr->_it) == (*_it);
                }
                return false;
            }
        private:
            const std::unique_ptr<Iterator<T>> _it;
        };

        template <typename T, typename U>
        struct SelectIterator
        {
            SelectIterator(const IteratorWrapper<T> &it, std::function<U(T)>func) : _it(it), _func(func) {}

            U operator *() const { return _func(*_it); }
            SelectIterator & operator++() { ++_it; return *this; }
            bool operator==(const SelectIterator &other) const { return _it == other._it; }

        private:
            IteratorWrapper<T> _it;
            std::function<U(T)> _func;
        };

        template <typename T>
        struct WhereIterator
        {
            WhereIterator(const IteratorWrapper<T> &begin, const IteratorWrapper<T> &end, std::function<bool(T)>func) : _it(begin), _end(end), _func(func), _val()
            {
                validate();
            }

            WhereIterator(const IteratorWrapper<T> &end) : _it(end), _end(end), _func(), _val() {};

            T operator *() const { return _val; }
            WhereIterator & operator++() { ++_it; validate(); return *this; }
            bool operator==(const WhereIterator &other) const { return _it == other._it; }

        private:

            void validate()
            {
                if (_it != _end) {
                    _val = *_it;

                    while (_it != _end && !_func(_val)) {
                        ++_it;
                        _val = *_it;
                    }
                }
            }

            T _val;
            IteratorWrapper<T> _it;
            IteratorWrapper<T> _end;
            std::function<bool(T)> _func;
        };

        template <typename T>
        struct Range
        {
            template <typename InputIterator>
            Range(const InputIterator &begin, const InputIterator &end)
            : _begin(begin), _end(end)
            {}

            IteratorWrapper<T> & begin() { return _begin; }
            IteratorWrapper<T> & end() { return _end; }

            template <typename Functor>
            auto select(Functor func) -> Range<decltype(func(T()))>
            {
                using ReturnType = decltype(func(T()));
                return { SelectIterator<T, ReturnType>(_begin, func), SelectIterator<T, ReturnType>(_end, func) };
            }

            Range where(std::function<bool(T)> func)
            {
                return { WhereIterator<T>(_begin, _end, func), WhereIterator<T>(_end) };
            }

        private:
            IteratorWrapper<T> _begin;
            IteratorWrapper<T> _end;
        };

        template <typename T>
        struct ValueIterator
        {
            ValueIterator(T val) : _val(val) {}

            T operator *() const { return _val; }
            ValueIterator & operator++() { ++_val; return *this; }
            bool operator==(const ValueIterator &other) const { return _val == other._val; }

        private:
            T _val;
        };

    }

    using detail::Range;

    template <typename T>
    Range<T> range(T from, T end)
    {
        return { detail::ValueIterator<T>(from), detail::ValueIterator<T>(end) };
    }

    template <typename T>
    Range<T> range(T end)
    {
        return { detail::ValueIterator<T>(T()), detail::ValueIterator<T>(end) };
    }

    template <typename FromType>
    auto from(FromType f) -> Range<typename std::remove_reference<decltype(*std::begin(f))>::type>
    {
        return { std::begin(f), std::end(f) };
    }

    template <typename T>
    auto from(std::initializer_list<T> f) -> Range<T>
    {
        return { std::begin(f), std::end(f) };
    }
}

It can be used like this

{
    std::vector<int> vec = {1,2,3,4,5}; // some iterable
    auto r =
    linq::from(vec)
    .where([](int i){ return i % 2;})
    .select([](int i){ return i * i;})
    ;

    for (auto obj : r)
    {
        std::cout << obj << "\n";
    }
}

{
    auto r =
    linq::range(1, 30)
    .where([](int i){ return i % 2;})
    .select([](int i){ return i * i;})
    ;

    for (auto obj : r)
    {
        std::cout << obj << "\n";
    }
}
\$\endgroup\$
  • \$\begingroup\$ This is great. I don't know enough C++ to really answer your questions though (I'm much more of a C and C# guy!) \$\endgroup\$ – Jonathon Reinhart Nov 25 '13 at 4:21
  • \$\begingroup\$ I thought Linq failed as a DB extraction (or is now considered horrible). Could be wrong. \$\endgroup\$ – Martin York Nov 25 '13 at 6:03
  • \$\begingroup\$ There is framework to convert linq expression to query. But I am refer to linq style functional approach to process list here. My code have nothing to do with DB. \$\endgroup\$ – Bryan Chen Nov 25 '13 at 6:22
  • 1
    \$\begingroup\$ If you're just looking for this sort of capability, see cpplinq.codeplex.com - even if you want to write your own it may still be worth looking at some of the decisions they made (such as operator>> instead of dot-methods to enhance extensibility). \$\endgroup\$ – Michael Urman Nov 25 '13 at 16:00
1
\$\begingroup\$

I am not sure this is a good idea (nor do I think the cpplinq in @MichaelUrman's post is a good idea - though it's definitely workable).

Basically you are writing a fully templated hierarchy of classes, to replace (existing, stable and presumably tested) functionality in std algorithm:

Your code:

auto r =
linq::range(1, 30)
.where([](int i){ return i % 2;})
.select([](int i){ return i * i;})
;

for (auto obj : r)
{
    std::cout << obj << "\n";
}

std code:

std::vector<int> src{1, /**/, 29};
std::vector<int> x;
std::copy_if(src.begin(), src.end(), std::back_inserter(x), [](int i){ return i % 2;});
std::transform(x.begin(), x.end(), x.begin(), [](int i){ return i * i;});

You could create your own transform_if, combining the two functions above.

\$\endgroup\$
  • 1
    \$\begingroup\$ Yes I agree the functionality are similar and performance of std algorithm is definitely better. but don't you think my way is easier to read/write? and my iterators are lazy evaluated so if I only need first N objects I only have to evaluate functors in select/where for first N objects. Maybe there is way to do this with std library but I don't know about it. \$\endgroup\$ – Bryan Chen Nov 26 '13 at 19:56

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.