Skip to content

Instantly share code, notes, and snippets.

@xr1s
Last active August 30, 2023 21:34
Show Gist options
  • Save xr1s/3aed5b933f256e8f4cf9a4c3f76a5c27 to your computer and use it in GitHub Desktop.
Save xr1s/3aed5b933f256e8f4cf9a4c3f76a5c27 to your computer and use it in GitHub Desktop.
C++ Chain Range Adaptor
// https://xr1s.me/2023/08/13/cxx-user-defined-range-adaptor/
#include <fmt/core.h>
#include <algorithm>
#include <concepts>
#include <deque>
#include <forward_list>
#include <iterator>
#include <ranges>
#include <tuple>
#include <utility>
#include <variant>
#include <vector>
template <typename T, typename Ts>
struct IsOneOfImpl;
template <typename T, template <typename...> typename Cont, typename... Ts>
struct IsOneOfImpl<T, Cont<Ts...>> {
constexpr static inline bool value = (... || std::same_as<T, Ts>);
};
// IsOneOf<T, std::tuple<Ts...>> 判断 T 是否为 Ts 的其中一部分
// 除了 std::tuple, 用 std::variant 也行, IsOneOf<T, std::variant<Ts...>>
// 这里不用 IsOneOf<T, Ts...> 是为了方便后续处理 Enumerate 生成的类型
template <typename T, typename Ts>
concept IsOneOf = IsOneOfImpl<T, Ts>::value;
template <size_t N, typename T>
struct IndexedElement: T {};
template <template <typename...> typename Cont, typename S, typename... T>
struct EnumerateImpl;
template <template <typename...> typename Cont, size_t... I, typename... T>
struct EnumerateImpl<Cont, std::index_sequence<I...>, T...> {
using type = Cont<IndexedElement<I, T>...>;
};
// Enumerate 用来为 T 做下标标记, 这样才能在编译期取出当前迭代器所在的位置
// 在迭代到当前第 N 个容器的 end() 后通过 get<N + 1> 来获取下一个容器的 begin()
// 使用方法是 Enumerate<容器, 类型列表...>
// 如 Enumerate<std::tuple, int, float>
// -> std::tuple<IndexedElement<0, int>, IndexedElement<1, float>>
template <template <typename...> typename Cont, typename... T>
using Enumerate =
EnumerateImpl<Cont, std::make_index_sequence<sizeof...(T)>, T...>::type;
template <std::ranges::viewable_range... Ranges>
class ChainView: public std::ranges::view_interface<ChainView<Ranges...>> {
std::tuple<Ranges...> ranges;
using InnerIteratorVariant =
Enumerate<std::variant, std::ranges::iterator_t<Ranges>...>;
class Iterator;
constexpr static inline size_t N = sizeof...(Ranges);
public:
using iterator = Iterator;
using value_type = std::common_type_t<typename std::iterator_traits<
std::ranges::iterator_t<Ranges>>::value_type...>;
ChainView() = default;
explicit ChainView(Ranges &&...ranges): ranges{std::move(ranges)...} {
}
Iterator begin() {
using Head = std::variant_alternative_t<0, InnerIteratorVariant>;
return Iterator{this, Head{std::get<0>(this->ranges).begin()}};
}
Iterator end() {
using Last = std::variant_alternative_t<N - 1, InnerIteratorVariant>;
return Iterator{this, Last{std::get<N - 1>(this->ranges).end()}};
}
// 支持 chain(v0)(v1)(v2) 语法调用
template <std::ranges::viewable_range Range>
auto operator()(Range &&range) && {
using R = std::ranges::views::all_t<Range>;
R ref = std::forward<Range>(range);
std::tuple args =
std::tuple_cat(std::move(this->ranges), std::tuple{std::move(ref)});
return std::make_from_tuple<ChainView<Ranges..., R>>(std::move(args));
}
// 支持 v0 | chain(v1) | chain(v2) 语法调用
template <std::ranges::viewable_range Range>
friend auto operator|(Range &&range, const ChainView &cv) {
using R = std::ranges::views::all_t<Range>;
R ref = std::forward<Range>(range);
std::tuple args =
std::tuple_cat(std::tuple{std::move(ref)}, std::move(cv.ranges));
return std::make_from_tuple<ChainView<R, Ranges...>>(std::move(args));
}
};
template <std::ranges::viewable_range... Ranges>
class ChainView<Ranges...>::Iterator {
ChainView *view = nullptr;
InnerIteratorVariant inner;
public:
using difference_type = ptrdiff_t;
using value_type = ChainView::value_type;
Iterator() = default;
template <typename T>
requires IsOneOf<T, ChainView::InnerIteratorVariant>
Iterator(ChainView *view, T &&iterator)
: view{view}, inner{std::forward<T>(iterator)} {
}
template <typename T>
Iterator &next(IndexedElement<N - 1, T> &iterator) {
++iterator;
return *this;
}
template <size_t I, typename T>
Iterator &next(IndexedElement<I, T> &iterator) {
auto &curr = std::get<I>(this->view->ranges);
if (++std::forward<T>(iterator) == curr.end()) {
using NextIterator =
std::variant_alternative_t<I + 1, ChainView::InnerIteratorVariant>;
auto &next = std::get<I + 1>(this->view->ranges);
this->inner = IndexedElement<I + 1, NextIterator>{next.begin()};
};
return *this;
}
Iterator &operator++() {
return std::visit(
[this]<typename T>(T &&iterator) -> Iterator & {
return this->next(std::forward<T>(iterator));
},
this->inner);
}
Iterator operator++(int) {
auto here = *this;
++*this;
return here;
}
value_type &operator*() const & {
return std::visit(
[]<size_t I, typename T>(const IndexedElement<I, T> &iterator)
-> value_type & { return *iterator; },
this->inner);
}
bool operator==(const Iterator &other) const & {
return this->inner == other.inner;
}
bool operator!=(const Iterator &other) const & {
return this->inner != other.inner;
}
};
template <std::ranges::viewable_range... Ranges>
ChainView(Ranges &&...) -> ChainView<std::ranges::views::all_t<Ranges>...>;
struct ChainAdaptor {
template <std::ranges::viewable_range... Ranges>
static auto operator()(Ranges &&...ranges) {
return ChainView{std::forward<Ranges>(ranges)...};
}
};
constexpr inline ChainAdaptor chain;
int main() {
std::vector vi = {0, 1, 1, 2, 3, 5, 7, 13, 21, 34, 55, 89, 144};
std::deque qi = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
std::forward_list fi = {1, 4, 9, 16, 25, 36, 49, 64, 81, 100};
auto view = vi | chain(qi)(fi) | chain(vi, qi, fi)
| std::ranges::views::filter(
[](const int &value) { return value % 2 == 0; })
| std::ranges::views::transform(
[](const int &value) { return std::to_string(value); });
//
std::ranges::for_each(
view, [](const auto &value) { fmt::println("{:?}", value); });
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment