C++20과 C++23을 활용한 “파이썬스러운” API 구현 #14: groupby, permutations, product

앞서 기본 구현을 통해 groupby, permutations, product를 C++로 옮기는 방법을 살펴봤습니다. 여기서는 C++20의 Concepts와 Ranges 라이브러리를 활용해 정교한(또는 확장된) 구현 방법을 간단히 예시로 보여드리겠습니다.

파이썬스럽다는 것은 단순히 기능을 흉내내는 데 그치지 않고, 타입 안정성, 가독성, 모듈성까지 고려하는 것입니다. Concepts로 입력 타입을 제약하거나, Variadic Template로 product를 여러 컨테이너에 확장하는 예제를 살펴보죠.

정교한(또는 확장된) 구현 예제

1. groupby에 Concepts 적용하기

groupby는 연속된 원소를 key 함수 결과에 따라 그룹화합니다. 여기서 key 함수는 원소를 받아 어떤 key로 매핑하는 Callable이어야 합니다. C++20 Concepts를 사용해 key 함수가 올바른 형태인지 검사하고, 입력 컨테이너가 Forward Range인지 제약할 수 있습니다.

#include <concepts>
#include <ranges>
#include <functional>

// ForwardRange와 KeyFunc 제약
template<typename R, typename KeyFunc>
concept Groupable = 
    std::ranges::forward_range<R> && 
    std::regular_invocable<KeyFunc, std::ranges::range_reference_t<R>>;

// 개선된 groupby_view
template<Groupable R, typename KeyFunc>
requires std::regular_invocable<KeyFunc, std::ranges::range_reference_t<R>>
class groupby_view {
    R& r_;
    KeyFunc kf_;

    struct group {
        std::invoke_result_t<KeyFunc, std::ranges::range_reference_t<R>> key;
        std::ranges::iterator_t<R> begin_it;
        std::ranges::iterator_t<R> end_it;
    };

    class iterator {
    public:
        using base_it = std::ranges::iterator_t<R>;

        iterator(base_it current, base_it end, KeyFunc kf)
            : current_(current), end_(end), kf_(kf), done_(current == end) {
            if (!done_) {
                key_ = std::invoke(kf_, *current_);
                next_ = find_next_group_end(current_);
            }
        }

        iterator& operator++() {
            if (!done_) {
                current_ = next_;
                if (current_ == end_) {
                    done_ = true;
                } else {
                    key_ = std::invoke(kf_, *current_);
                    next_ = find_next_group_end(current_);
                }
            }
            return *this;
        }

        bool operator!=(const iterator& other) const {
            return done_ != other.done_ || current_ != other.current_;
        }

        auto operator*() const {
            group g{key_, current_, next_};
            return g;
        }

    private:
        base_it find_next_group_end(base_it start) {
            auto cur_key = std::invoke(kf_, *start);
            auto it = start; ++it;
            for (; it != end_; ++it) {
                if (std::invoke(kf_, *it) != cur_key) break;
            }
            return it;
        }

        base_it current_, end_, next_;
        KeyFunc kf_;
        bool done_;
        std::invoke_result_t<KeyFunc, std::ranges::range_reference_t<R>> key_;
    };

public:
    groupby_view(R& r, KeyFunc kf) : r_(r), kf_(kf) {}
    auto begin() { return iterator(std::ranges::begin(r_), std::ranges::end(r_), kf_); }
    auto end() { return iterator(std::ranges::end(r_), std::ranges::end(r_), kf_); }
};

template<typename R, typename KeyFunc>
requires Groupable<R, KeyFunc>
auto groupby_func(R& r, KeyFunc kf) {
    return groupby_view<R, KeyFunc>(r, kf);
}

이제 groupby_func를 사용할 때, 입력 컨테이너가 forward_range이고, KeyFunc가 실제로 *it를 받아 key를 반환하는 callable인지 컴파일 시 검사합니다.

2. permutations에서 r 파라미터 고려 및 Concepts 적용

permutations에서 r이 주어지면, 길이가 r인 순열만 생성해야 합니다. 또한 비교 연산이 가능한 타입인지 확인하는 Concepts를 적용해볼 수 있습니다. std::totally_ordered 개념을 사용하면 정렬 가능한 타입인지 체크할 수 있습니다.

#include <algorithm>
#include <concepts>
#include <ranges>

template<std::ranges::forward_range R>
requires std::totally_ordered<std::ranges::range_value_t<R>>
class permutations_view {
public:
    permutations_view(R r, std::size_t rlen=0)
        : original_(std::move(r)) {
        if (rlen == 0) rlen = std::ranges::distance(original_);
        r_ = rlen;
        std::ranges::sort(original_);
        end_ = (std::ranges::empty(original_));
    }

    class iterator {
    public:
        iterator(permutations_view* parent, bool end)
            : parent_(parent), end_(end) {}

        iterator& operator++() {
            if (!std::next_permutation(std::ranges::begin(parent_->original_), std::ranges::end(parent_->original_))) {
                end_ = true;
            }
            return *this;
        }

        bool operator!=(const iterator& other) const {
            return end_ != other.end_;
        }

        auto operator*() const {
            std::vector<std::ranges::range_value_t<R>> res;
            auto it = std::ranges::begin(parent_->original_);
            for (std::size_t i = 0; i < parent_->r_; ++i, ++it) {
                res.push_back(*it);
            }
            return res;
        }

    private:
        permutations_view* parent_;
        bool end_;
    };

    auto begin() {
        if (end_) return iterator(this, true);
        return iterator(this, false);
    }
    auto end() {
        return iterator(this, true);
    }

private:
    R original_;
    std::size_t r_;
    bool end_;
};

template<std::ranges::forward_range R>
requires std::totally_ordered<std::ranges::range_value_t<R>>
auto permutations_func(R r, std::size_t rlen=0) {
    return permutations_view<R>(std::move(r), rlen);
}

이제 permutations_func는 입력이 정렬 가능한 값 타입을 갖는 Range인지 확인하고, r 길이의 부분 순열을 적절히 반환합니다.

3. product를 Variadic Template으로 확장

product를 두 개의 컨테이너에 대해 구현했지만, Variadic Template을 이용하면 임의 개수의 컨테이너를 받아 그들의 카테시안 곱을 생성할 수 있습니다. Concepts로 모든 컨테이너가 forward_range인지 체크할 수 있고, fold expression을 통해 우아하게 구현할 수 있습니다.

#include <tuple>
#include <concepts>
#include <utility>
#include <ranges>

// 모든 컨테이너가 forward_range인지 체크
template<typename... Rs>
concept AllForwardRanges = (std::ranges::forward_range<Rs> && ...);

template<AllForwardRanges... Rs>
class product_multi_view {
    // 모든 컨테이너를 tuple로 보관
    std::tuple<Rs&...> containers_;

    // iterator는 각 컨테이너의 iterator를 tuple로 관리
    // 각각의 iterator 범위를 통해 카테시안 곱을 구현
    // 재귀 없이 fold expression으로 다음 조합 계산 가능

    // helper to create iterator tuple
    template<typename... Rs2>
    static auto begin_tuple(Rs2&... rs) {
        return std::tuple(std::ranges::begin(rs)...);
    }

    template<typename... Rs2>
    static auto end_tuple(Rs2&... rs) {
        return std::tuple(std::ranges::end(rs)...);
    }

public:
    product_multi_view(Rs&... rs) : containers_(rs...) {}

    class iterator {
        product_multi_view* parent_;
        std::tuple<std::ranges::iterator_t<Rs>...> its_;
        std::tuple<std::ranges::iterator_t<Rs>...> begins_;
        std::tuple<std::ranges::iterator_t<Rs>...> ends_;
        bool done_;

        template<std::size_t I=0>
        bool increment_tuple() {
            if constexpr (I == sizeof...(Rs)) {
                // 모든 범위를 넘어감
                return true;
            } else {
                auto& it = std::get<I>(its_);
                auto& end = std::get<I>(ends_);
                ++it;
                if (it == end) {
                    auto& begin = std::get<I>(begins_);
                    it = begin;
                    // 다음 범위를 올려 increment
                    return increment_tuple<I+1>();
                }
                return false;
            }
        }

    public:
        iterator(product_multi_view* parent, bool end)
            : parent_(parent), done_(end) {
            if (!end) {
                // begins와 ends 구성
                std::apply([&](auto&... rs){
                    begins_ = product_multi_view::begin_tuple(rs...);
                    ends_ = product_multi_view::end_tuple(rs...);
                    its_ = begins_;
                    // 만약 어떤 컨테이너가 empty면 done_=true
                    bool empty_any = ((std::ranges::empty(rs)) || ...);
                    if (empty_any) done_ = true;
                }, parent_->containers_);
            }
        }

        iterator& operator++() {
            if (!done_) {
                if (increment_tuple<0>()) {
                    done_ = true;
                }
            }
            return *this;
        }

        bool operator!=(const iterator& other) const {
            return done_ != other.done_;
        }

        auto operator*() const {
            // its_를 통해 현재 조합을 vector나 tuple로 반환 가능
            // 여기서는 tuple로 반환
            return std::apply([&](auto&... it) {
                return std::tuple<decltype(*it)...>(*it...);
            }, its_);
        }
    };

    auto begin() {
        return iterator(this, false);
    }
    auto end() {
        return iterator(this, true);
    }
};

template<AllForwardRanges... Rs>
auto product_func(Rs&... rs) {
    return product_multi_view<Rs...>(rs...);
}

이 정교한 구현에서는 Variadic Template과 Concepts를 활용해 임의 개수의 컨테이너 카테시안 곱을 생성합니다. 모든 컨테이너가 forward_range인지 체크하고, empty 컨테이너가 하나라도 있으면 즉시 빈 결과를 반환하도록 처리했습니다.

성능과 메모리 측면

• groupby 정교화: Concepts로 타입 안정성과 표현력 강화.
• permutations 정교화: 정렬 가능 타입 제약, r 처리 및 lazy 계산.
• product 정교화: Variadic Template로 확장, Concepts로 모든 컨테이너 제약, fold expression으로 우아한 구현.

관련 링크 및 리소스

• C++20 Concepts (cppreference)
• C++20 Ranges (cppreference)
• Eric Niebler's range-v3 - 풍부한 뷰와 어댑터 예제

마무리

이번 글에서는 groupby, permutations, product의 기본 구현에 이어, Concepts와 Ranges를 활용해 정교하고 확장된 구현 방법까지 살펴봤습니다. 타입 제약을 통해 에러를 컴파일 타임에 잡고, Variadic Template과 fold expression으로 코드 가독성과 확장성을 높일 수 있음을 보았습니다.

 

앞으로도 파이썬스러운 추상화를 C++에서 더욱 우아하게 다듬어가는 과정에서, 이러한 정교한 구현 기법이 큰 도움이 되길 바랍니다.