npm ERR! /home/bate/.node-gyp/16.11.1/include/node/v8-internal.h: In function ‘void v8::internal::PerformCastCheck(T*)’: npm ERR! /home/bate/.node-gyp/16.11.1/include/node/v8-internal.h:492:38: error: ‘remove_cv_t’ is not a member of ‘std’; did you mean ‘remove_cv’? npm ERR! 492 | !std::is_same<Data, std::remove_cv_t<T>>::value>::Perform(data); npm ERR! | ^~~~~~~~~~~ npm ERR! | remove_cv npm ERR! /home/bate/.node-gyp/16.11.1/include/node/v8-internal.h:492:38: error: ‘remove_cv_t’ is not a member of ‘std’; did you mean ‘remove_cv’? npm ERR! 492 | !std::is_same<Data, std::remove_cv_t<T>>::value>::Perform(data); npm ERR! | ^~~~~~~~~~~ npm ERR! | remove_cv npm ERR! /home/bate/.node-gyp/16.11.1/include/node/v8-internal.h:492:50: error: template argument 2 is invalid npm ERR! 492 | !std::is_same<Data, std::remove_cv_t<T>>::value>::Perform(data); npm ERR! | ^ npm ERR! /home/bate/.node-gyp/16.11.1/include/node/v8-internal.h:492:63: error: ‘::Perform’ has not been declared npm ERR! 492 | !std::is_same<Data, std::remove_cv_t<T>>::value>::Perform(data); npm ERR! | ^~~~~~~ npm ERR! ../src/binding.cpp: In function ‘Nan::NAN_METHOD_RETURN_TYPE render(Nan::NAN_METHOD_ARGS_TYPE)’:
出错原因：std::remove_cv_t 是 C++14 引入的，而 gcc 默认为 C++11，感叹 C++ 拖后腿日常。
So in this post, you will learn how to write a ranges library from scratch in C++17, with some useful functionality that doesn’t exists in the C++20 library <ranges>, like enumerate or zip.
C++11 range-based loop
It’s very convinent to use range-based for loop since C++11:
1 2 3 4 5
std::vector<int> list;
for (auto &&x: list) { print(x + 1); }
C++20 ranges library
But sometimes, I wonder what if I need to get the index while iterating over a range? In Python, we can use enumerate, zip, map, and so on. While there is no equivalant functions in C++, until C++20 which introduced many range operations like std::views::transform for map in Python, use it like this:
1 2 3 4 5 6 7 8 9
#include<ranges>
std::vector<int> list;
for (auto &&x: list | std::views::transform([] (auto &&x) { return x + 1; }) ) { print(x); }
It will apply + 1 to every value in list before calling into the loop body.
Yeah, the operator| here - I’d like to call it the pipe style, is even more convinent than Python’s function style range operations. Especially when the pipe is long:
1 2 3 4 5 6 7 8 9 10 11
#include<ranges>
std::vector<unique_ptr<int>> list;
for (auto &&x: list | std::views::transform([] (auto &&x) { return x.get(); }) | std::views::transform([] (auto &&x) { return x + 1; }) | std::views::reverse ) { print(x); }
Of course, the function style also supported in C++20:
1 2 3 4 5 6 7
#include<ranges>
std::vector<int> list;
for (auto &&x: std::views::transform([] (auto &&x) { return x + 1; }, list)) { print(x); }
The lambda definition looks too verbose here, let’s simplify it by a macro:
for (auto &&x: list | std::views::transform(LAMBDA1(x, x + 1))) { print(x); }
Wait a miniute…
However, the transform or map isn’t so useful after all. While they don’t even have zip and enumerate!!! They are very commonly used in daily programming. Otherwise I still have to write for (int i... when the index is necessary.
So I decide to write my only ranges library rather than waiting for C++ standard to support this.
My ranges library!
First of all, we need to define a generic range class.
1 2 3 4 5 6 7 8 9 10 11 12
template <classIt> structrange { It m_begin; It m_end;
constexprrange(It begin, It end) : m_begin(std::move(begin)), m_end(std::move(end)) {}
constexpr It begin()const{ return m_begin; } constexpr It end()const{ return m_end; } };
Then, we we want to create a range for a std::vector<int>, we can use:
1 2
std::vector<int> list; auto r = range<std::vector<int>::iterator>(list.begin(), list.end());
To be generic, we can use decltype to automatically determine the iterator type of a given object:
1 2
some_type_that_we_dont_know list; auto r = range<decltype(list.begin())>(list.begin(), list.end());
Compile-time argument deduction
But this way we will have to write range<decltype(t.begin())>(t.begin(), t.end()) every time… Don’t worry! We can use the complile-time argument deduction (CTAD) feature since C++17 to automatically deduce the <class It> with given rule when argument has a confirmed type:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
template <classIt> structrange { It m_begin; It m_end;
constexprrange(It begin, It end) : m_begin(std::move(begin)), m_end(std::move(end)) {}
constexpr It begin()const{ return m_begin; } constexpr It end()const{ return m_end; } };
// define the deduction rule: template <classIt> range(It begin, It end) -> range<It>;
Then, when range(t.begin(), t.end()) is called, it will be automatically deduced as range<decltype(t.begin())>(t.begin(), t.end()).
The pipable class
Given that most transformations only takes one range as input, thus can support the pipe style syntax (excluding zip which requires multiple input), we’d like to define a common class for all kind of range operators, called pipable:
First let’s implement the easiest range operator: map
To do so, we need to implement our custom iterators, which requires many knowledge on what C++ iterators actually are.
range-based for loops are 纸老虎
For example, the following C++11 range-based for loop:
1 2 3
for (auto x: list) { print(x); }
Is nothing more than a shortcut for:
1 2 3 4
for (auto it = list.begin(); it != list.end(); ++it) { auto x = *it; print(x); }
Where the begin and end are duck-typing method names for all objects to be considered iterable, so if you write:
1 2 3 4
int not_iterable = 42; for (auto x: not_iterable) { print(x); }
The compiler will complain something like: error: int have no member named begin. That’s because range-based for loops are just… nothing more than shortcuts…
Iterators are classes trying to imitate pointers
So what actually the type it is?
1 2 3 4
for (auto it = list.begin(); it != list.end(); ++it) { auto x = *it; print(x); }
Looking at the *it here, we wonder if it is actually a pointer, i.e. int *?
Not really, the real type of list.begin() is vector<int>::iterator, which is a class with these operator overloading methods defined:
operator*() for getting the pointed value with *it
operator++() for iterate to the next value with ++it
operator!=() for comparing two iterators to see if it comes to end()
As you can see, C++ iterators are classes trying to behave as if it is a pointer, for allowing algorithm reuse ability, and minimize the effort for C programmers to adapt from C pointers to C++ iterators.
So to implement custom iterators…
So if we want to implement our own iterators, we can simply define the above three operator overloading methods to control the behavior.
Now that we want to implement map, we acutally is willing the following code:
1 2 3
for (auto x: list | map(func)) { print(x); }
to be translated into:
1 2 3 4
for (auto it = list.begin(); it != list.end(); ++it) { auto x = func(*it); // changed here print(x); }
right?
So why not just overload the operator*() to make it return func(*it) instead, while other operators remain the same.
template <classFunc, classBase> structmap_iterator { Func m_func; Base m_it;
// using `decltype(auto)` (since C++14) instead of `auto` so that // even if `m_func` returns a reference, it automatically becames // `auto &` rather than dereferencing that... constexprdecltype(auto) operator*()const{ returnm_func(*m_it); }
Here we used map_iterator{...} rather than map_iterator(...) so that we don’t have to write the constructor ourselves but ask the compiler to assign its members with default order (since C++11).
Then test it in main function:
1 2 3 4 5 6 7
intmain(){ std::vector<int> list = {1, 2, 3, 4}; for (auto &&x: list | map([] (auto &&x) { return x + 1; })) { std::cout << x << std::endl; } return0; }
Compile and run it:
1 2 3 4 5
$ g++ -std=c++20 a.cpp && ./a.out 2 3 4 5
Succeed! We managed to make our first step in implementing ranges library ourselves!
What’s next?
Next, we will go ahead to implement the enumerate and zip as well with the same technique we learnt from implementing the map.
Implement enumerate
Now that we want to implement enumerate, we acutally is willing the following code:
1 2 3
for (auto [x, y]: list | enumerate(func)) { print(x, y); }
to be translated into:
1 2 3 4 5
size_t index = 0; for (auto it = list.begin(); it != list.end(); ++it, ++index) { auto [x, y] = std::pair(index, *it); print(x, y); }
right?
Here, the auto [x, y] = ... is the structual binding syntax since C++17, and ... can be a std::pair, or std::tuple, or any thing unpackable, we will take a deep look into this later.
So now we need to overload operator*() to make it return a pair of values, whose first value is the index, which is incresed during operator++(), like this:
Yes, the Python zip can pass above two ‘challenge’ :)
Finally…
You may ‘submit’ the ‘homework’ via 评论区, or GitHub, or any other way that fesible. Submitting this homework won’t affect anyone’s GPA or KPI, but this one is just for fun!
Below is the final source code of this tutorial, your homework may be either based on it or completely from scratch:
Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.