Several container functions rewritten as an excercise

Question 1

I took one of my old university exercises for another language and re-solved it in c++. It consists of several higher order functions for vectors. I hope the comments are self-documenting enough.

I am mainly concerned about not utilizing "modern" c++ features enough and generally writing bad c++, but feedback of any kind would be greatly appreciated.

#include <type_traits>
#include <iostream>
#include <vector>
#include <utility>
#include <unordered_map>
#include "show.h"
#include "utils.hpp"
template <typename T> using Vec = std::vector<T>;
template <typename K, typename V> using Map = std::unordered_map<K,V>;
//Returns a vector of Bs, obtained by applying F to each A.
template <typename A, typename F, typename B = typename std::invoke_result<F,A>::type>
Vec<B> map(const Vec<A>& va, F f) {
 Vec<B> result;
 for (const auto& a : va)
 result.push_back(f(a));
 
 return result;
}
//Returns a vector of Bs, obtained by applying F to each A, and concatenating the resulting vectors.
template <typename A, typename F, typename B = typename std::invoke_result<F,A>::type::value_type>
Vec<B> flatmap(Vec<A> va, F f) {
 Vec<B> finalResultVector; 
 
 for(const auto& a : va){
 
 Vec<B> elementResult = f(a);
 finalResultVector.insert(finalResultVector.end(), elementResult.begin(), elementResult.end());
 }
 return finalResultVector;
}
 
//Returns a pair (prefix, suffix) of vectors of As, such that prefix ++ suffix == as.
//The suffix contains all As up to but excluding the first for which predicate p returned false.
template <typename A, typename P>
std::pair<Vec<A>,Vec<A>> span(Vec<A> va, P p) {
 Vec<A> prefix;
 Vec<A> suffix;
 
 for(size_t index = 0; index<va.size(); index++){
 
 auto a = va.at(index);
 if(p(a)){
 prefix.push_back(a);
 
 }else{
 
 suffix.insert(suffix.begin(),va.begin()+index,va.end());
 break;
 }
 
 }
 return {prefix, suffix}; 
}
//Returns the value obtained by repeatedly (from left to right) applying
//binary function f to the result of the previous application and the 
//current A. The first application is seeded with z.
template <typename A, typename B, typename F>
B foldleft(const Vec<A>& va, B z, F f) {
 
 B tmpResult = z;
 
 for(const auto& a : va){
 
 tmpResult = f(tmpResult,a); 
 } 
 return tmpResult;
}
//Returns a vector of Bs, obtained by repeatedly (from left to right) 
//applying binary function f to the result of the previous application 
//and the current A. The first application is seeded with z.
template <typename A, typename B, typename F>
Vec<B> scanleft(const Vec<A>& va, B z, F f) {
 Vec<B> resultVector = {z};
 
 for(size_t index = 0; index < va.size(); index++){
 
 auto result = f(resultVector.at(index), va.at(index));
 resultVector.push_back(result);
 }
 
 
 
 return resultVector;
}
//Returns a map, whose values are the equivalence classes determined by the key function f.
 
template <typename A, typename F, typename K = typename std::invoke_result<F,A>::type>
Map<K,Vec<A>> groupby(const Vec<A>& va, F f) {
 auto resultMap = Map<K,Vec<A>>();
 
 for(const auto& a : va){
 
 auto eqClass = f(a);
 auto pos = resultMap.find(eqClass);
 if(pos == resultMap.end()){
 
 resultMap.insert({eqClass,{a}});
 }else{
 
 pos->second.push_back(a);
 }
 }
 return resultMap;
}

Question 2

Welcome to Code Review! It would benefit reviewers to have a bit more information about the code in the description. From the help center page How to ask: "You will get more insightful reviews if you not only provide your code, but also give an explanation of what it does. The more detail, the better."

Question 3

Map

template <typename A, typename F, typename B = typename std::invoke_result<F,A>::type>
Vec<B> map(const Vec<A>& va, F f) {
 Vec<B> result;
 for (const auto& a : va)
 result.push_back(f(a));
 
 return result;
}

Why limit yourself to vector. I would write for a generic container C. For this you should use the template template. Note the standard containers take two parameters; a type and an allocator (we need to specify this).

While we are at the function declaration, I would use the return type of auto so you don't need to write out the ho rendus type expression twice. Let the compiler work it out for you.

template<template<typename, typename> typename C, typename T, typename A, typename F>
auto map(C<T, A> const& container, F&& action)
{
 using Result = typename std::invoke_result<F,T>::type;
 C<Result, std::allocator<Result>> result;

Next: I would pre-allocate space for the resulting container.

 result.reserve(container.size());

Note: This will only work if your type C has a reserve method. So it will work for things like vector. But for things like std::list we need to do some meta programming to make it work.

#if __cplusplus == 202002L
template<typename C>
concept HasReserveMemberFunc = requires
{
 typename C::size_type;
 { std::declval<C>().reserve(std::declval<typename C::size_type>()) } -> std::same_as<void>;
};
#elif __cplusplus >= 201703L
template<typename C>
struct HasReserveMemberFuncType
{
 private:
 // If &U::reserve fails to compile then SFINAE ensures this is not a compiler error.
 // If just means this function does not exist in that case.
 template<typename U>
 static constexpr std::enable_if_t<std::is_member_pointer_v<decltype(&U::reserve)>, char> Test(int);
 // Notice the return type of this version is int
 // This function is always available.
 // But if the above function is available it will be chosen over this alternative as
 // it has an exact match with the parameter while this function will only be chosen if
 // the above function does not exist (Note: will not exist if it is removed by SFINAE).
 template<typename U>
 static constexpr int Test(...);
 public:
 // The value here is true if Test(int) is available which only happens
 // If C has a member reserve.
 static constexpr bool value = sizeof(Test<C>(0)) == sizeof(char);
};
template<typename C>
inline constexpr bool HasReserveMemberFunc = HasReserveMemberFuncType<C>::value;
#else
// You can do it with C++11
#error "You are out of luck"
#endif
template<typename C>
void reserve(C& c, std::size_t size)
{
 if constexpr (HasReserveMemberFunc<C>) {
 c.reserve(size);
 }
}

So now I would write map like this:

template<template<typename, typename> typename C, typename T, typename A, typename F>
auto map(C<T, A> const& container, F&& action)
{
 using Result = typename std::invoke_result<F,T>::type;
 C<Result, std::allocator<Result>> result;
 reserve(result, container.size());
 for (auto const& val : container) {
 result.push_back(action(val));
 }
 
 return result;
}

When meta programming, I would stay away from member functions when standard standalone versions exists. As not all types will have the members, but the standard will override them for most types to get standard behaviour.

std::begin(x) rather than x.begin()
std::end(x) rather than x.end()
std::size(x) rather than x.size()
etc... (not sure about others).

So this line:

finalResultVector.insert(finalResultVector.end(), elementResult.begin(), elementResult.end());

becomes:

finalResultVector.insert(std::end(finalResultVector),
 std::begin(elementResult), std::end(elementResult));

Be careful about passing vectors by value:

 Vec<B> map(const Vec<A>& va, F f) { // In map pass by const ref
 Vec<B> flatmap(Vec<A> va, F f) { // In flatmap pass by value

I would not use index based loops. But would prefer you to use iterators.

 for(size_t index = 0; index<va.size(); index++){

It seem more natural in C++ to use either range based, or if you can't use range based loops then standard algorithms, if you can use algorithms then iterator based loops and finally if nothing else works then look at index based loops:

for(auto loop = std::begin(va); loop != std::end(va); ++loop){

Don't copy values out of containers when using a reference will do and prefer operator[] over at().

 auto a = va.at(index);
 // I would do:
 auto& a = va[index];

Look at standard algorithms that you can use:

Example partition_copy() could (potentially) be used to implement your span function.

Think about situations where move semantics are important. Can we destructively remove items from the source using a move (rather than a copy). This may make a lot of these algorithms much more efficient when the object in the container is non trivial.

Question 4

Using a template template and shenanigans to assume/guess the second parameter as an allocator seems a bit pointless when the only standard container the function will work with is a vector in any case.

Question 5

I’m going to go in a different direction from @MartinYork’s review, and suggest that you should stick with just vectors, and not bother trying to support arbitrary containers. I think supporting arbitrary containers is far too complex, and not worth the effort because you’re probably going to be using vectors 90% of the time anyway. If you do want to support arbitrary containers... well, I’ll talk a bit about that at the end. I"ll also talk a bit about fitting into future C++, not just modern C++.

General stuff

Before I focus on the individual algorithms, there are a couple of general things that apply overall that I want to comment on.

First:

#include <type_traits>
#include <iostream>
#include <vector>
#include <utility>
#include <unordered_map>
#include "show.h"
#include "utils.hpp"

There are a couple of headers that aren’t included in the review. I presume they don’t matter?

<iostream> also doesn’t seem to serve a purpose.

 for(size_t index = 0; index<va.size(); index++){

You use size_t a couple places, but it should be spelled std::size_t.

Also, as a general rule, you shouldn’t write raw for loops... but when you do, you should use the following structure:

for (type name = initializer; name != limit; ++name)

In other words, don’t use <, use !=. You will find this produces better code gen.

Also, always use prefix increment, not postfix increment, unless you really mean it. It won’t make a difference for a simple unsigned integer, but it could make an enormous difference with certain types of iterator.

size_t should work, but the right thing to do is to use the container’s size_type. The best way to do that is probably something like this:

for (auto index = std::ranges::range_size_t<Vec<A>>{}; index != std::ranges::size(va); ++index)
// OR:
for (auto index = decltype(std::ranges::size(va)){}; index != std::ranges::size(va); ++index)

Ugly, yes, but, again, you shouldn’t be writing raw loops anyway. And even when you must, using indices is a bad idea (unless you actually need them, of course). (And, in fact, you don’t need them. But we’ll get to that.)

Then there are the aliases:

template <typename T> using Vec = std::vector<T>;
template <typename K, typename V> using Map = std::unordered_map<K,V>;

I’m struggling to see the point of these aliases. They don’t really add anything to the code, and they don’t help at all with readability.

In fact, quite the opposite: in practice, if I came across code like Vec<B> map(const Vec<A>& va, F f), I would curse and mutter, "okay, now, what is Vec?" and have to embark on a search of the code base to find out where it’s defined. On the other hand, if I came across std::vector<B> map(const std::vector<A>& va, F f)... well, everything I need to know is right there. There are no mysteries.

There is a fine line between simplification and obfuscation. Aliases should be about the former, not the latter. If it doesn’t help understanding, then it’s obfuscation. Vec<T> does not help understanding anything more than std::vector<T>, so it’s not worth the alias.

Speaking of the types... I know I said you should stick with vectors... and you should... but you should also take allocators into account. Personally, I use custom allocators (and polymorphic allocators) a lot and they can make for absolutely ginormous performance boosts. Being restricted to std::allocator<> pretty much voids it for me.

Adding allocator support is fairly trivial, so there’s not really much reason not to.

Finally:

Again, I know I said that you should stick with vectors... and you should... but that only means you should stick with vectors as the return type. There is no reason you need to limit the argument type to vectors.

For example, why wouldn’t you want to allow this?:

auto ints = std::ranges::views::iota(1, 5);
auto strs = map(ints, to_string);
// strs is a vector<string> containing:
// "1", "2", "3", "4"

Allowing arbitrary return types is hard. Allowing arbitrary argument types is easy. In fact, it’s trivial. In many cases, the function body won’t even change. In some cases, there will even be less code.

So let’s get into the specific functions.

Map

So, let me start by illustrating some of the general suggestions I made to the interface:

template <
 std::ranges::input_range R,
 typename F,
 typename B = std::invoke_result_t<F&, std::ranges::range_value_t<R>>,
 typename Alloc = std::allocator<B>
>
 requires std::regular_invocable<F&, std::ranges::range_value_t<R>>
auto map(R&& r, F&& f) -> std::vector<B, Alloc>
{
 // Just forward the call to the allocator version:
 return map(std::forward<R>(r), std::forward<F>(f), {});
}
// This overload lets you provide an allocator:
template <
 std::ranges::input_range R,
 typename F,
 typename B = std::invoke_result_t<F&, std::ranges::range_value_t<R>>,
 typename Alloc = std::allocator<B>
>
 requires std::regular_invocable<F&, std::ranges::range_value_t<R>>
auto map(R&&, F&&, Alloc const&) -> std::vector<B, Alloc>;

As you can see, now you can take any range as an argument, and you can use custom allocators.

The body of the function is almost unchanged:

template <
 std::ranges::input_range R,
 typename F,
 typename B = std::invoke_result_t<F&, std::ranges::range_value_t<R>>,
 typename Alloc = std::allocator<B>
>
 requires std::regular_invocable<F&, std::ranges::range_value_t<R>>
auto map(R&& r, F&& f, Alloc const& alloc) -> std::vector<B, Alloc>
{
 auto result = std::vector<B, Alloc>(alloc);
 if constexpr (std::ranges::sized_range<R>)
 result.reserve(std::ranges::size(r));
 for (auto&& a : std::forward<R>(r))
 result.push_back(f(std::forward<decltype(a)>(a)));
 return result;
}

The only changes are that I added a conditional reserve, did a bunch of forwarding for maximal efficiency, and, of course, constructed the result vector with the provided allocator. All of those changes (other than using the allocator, and the variable name changes) are not technically necessary; your existing code could be used literally unchanged. They should increase performance in some cases, though.

(Technically, you shouldn’t just use range_value_t<R> in regular_invocable<F&, range_value_t<R>> and invoke_result_t<F&, range_value_t<R>>, because, depending on the value category of R, you may be calling the function with a (possibly const) lvalue reference, or an rvalue. The correct thing to do is to use range_reference_t<R> or range_rvalue_reference_t<R>, depending on the category of R... or consider using indirect_result_t<F&, range_iterator_t<R>> instead of invoke_result, and indirectly_unary_invocable or indirectly_regular_unary_invocable instead of invocable or regular_invocable.)

There is one thing about this interface that I really don’t like, though. You provide a template parameter B that determines the value type of the result range. That’s fine... but... it’s the third template parameter.

To illustrate why that’s a problem, suppose I have a function object that converts an int to a float... but I want a double result:

auto const ints = std::vector{1, 2, 3, 4};
struct to_float
{
 constexpr auto operator()(int i) const noexcept -> float { return i; }
};
// This produces vector<float>:
auto floats = map(ints, to_float{});
// But I want vector<double>.
// I *want* to do this:
auto doubles = map<double>(ints, to_float{});
// ... but that won't work.
// I have to do this:
auto doubles = map<decltype(ints), to_float, double>(ints, to_float{});
// ... but THAT WON'T WORK EITHER!!!
// Because of the way argument deduction and reference collapsing work,
// I actually have to do THIS:
auto doubles = map<decltype(ints)&, to_float, double>(ints, to_float{});
// ... or, more correctly:
auto doubles = map<std::add_lvalue_reference_t<decltype(ints)>, to_float, double>(ints, to_float{});
// ... which is absurd.

I would suggest either taking that template parameter out completely, because it’s unnecessary:

template <
 std::ranges::input_range R,
 typename F,
 typename Alloc = std::allocator<std::invoke_result_t<F&, std::ranges::range_value_t<R>>>
>
 requires std::regular_invocable<F&, std::ranges::range_value_t<R>>
auto map(R&& r, F&& f)
{
 return map(std::forward<R>(r), std::forward<F>(f), {});
}
template <
 std::ranges::input_range R,
 typename F,
 typename Alloc
>
 requires std::regular_invocable<F&, std::ranges::range_value_t<R>>
auto map(R&& r, F&& f, Alloc const& alloc)
{
 auto result = std::vector<std::invoke_result_t<F&, std::ranges::range_value_t<R>>, Alloc>(alloc);
 if constexpr (std::ranges::sized_range<R>)
 result.reserve(std::ranges::size(r));
 for (auto&& a : std::forward<R>(r))
 result.push_back(f(std::forward<decltype(a)>(a)));
 return result;
}

OR restructure your functions so that the result value type is the first template parameter (possibly deduced), so you can do map<double>(ints, to_float{}) and get a vector<double> as the result. I’ll leave how to do that as an exercise for the reader.

Incidentally, as a general rule, you shouldn’t use raw loops... yes, even in a simple case like this. That for loop could be:

std::ranges::for_each(std::forward<R>(r), [&result, &f](auto&& a) { result.push_back(f(a)); });
// Forwarding of a removed just to make the line shorter.

But there’s little point to that here.

However... the entire algorithm is basically just std::ranges::transform() (transform() is how C++ spells monadic map.)

Which means:

template <
 std::ranges::input_range R,
 typename F,
 typename B = std::invoke_result_t<F&, std::ranges::range_value_t<R>>,
 typename Alloc = std::allocator<B>
>
 requires std::regular_invocable<F&, std::ranges::range_value_t<R>>
auto map(R&& r, F&& f, Alloc const& alloc) -> std::vector<B, Alloc>
{
 auto result = std::vector<B, Alloc>(alloc);
 if constexpr (std::ranges::sized_range<R>)
 result.reserve(std::ranges::size(r));
 std::ranges::transform(std::forward<R>(r), std::back_inserter(result), f);
 return result;
}

Which, aside from the reserving, is basically a one-liner.

We’ll get back to that, though.

Flat map

Pretty much everything that applies to map() applies here as well. The only novel stuff is in the heart of the loop.

Before that, though, I think there are some typos in the argument list. You take the source vector by value... which means it’s copied. Don’t you want to take it by reference, either const& or a forwarding reference?

Anywho, the loop:

 Vec<B> elementResult = f(a);
 finalResultVector.insert(finalResultVector.end(), elementResult.begin(), elementResult.end());

Now, I would say, there is no need force the return from the function into a vector. Just use auto. Constrain it if you must:

 std::ranges::input_range auto elementResult = f(a);
 finalResultVector.insert(end(finalResultVector), begin(elementResult), end(elementResult));

As of C++23, vectors get a new function you may find very useful:

 finalResultVector.append_range(f(a));

So, because it’s impractical to figure out the size to reserve, the function is really just:

template <
 std::ranges::input_range R,
 typename F
>
auto flatmap(R&& r, F&& f)
{
 using func_result_t = std::invoke_result_t<F&, std::ranges::range_value_t<R>>;
 auto result = std::vector<std::invoke_result_t<F&, std::ranges::range_value_t<func_result_t>>>{};
 for (auto&& a : std::forward<R>(r))
 result.append_range(f(std::forward<decltype<a>(a)));
 return result;
}

Span

This is actually a neat algorithm, and I struggled to think of a standard algorithm that does quite the same job. (I mean, it’s easily approximated by standard algorithms, but nothing does exactly the same job that I can think of.)

My biggest objection is to the name. "Span" already means something in C++, and it’s not this. And I don’t really see how splitting a range into two parts based on a predicate is "spanning". To me, a more logical name is something like split_at() or split_with(). It might even make sense to do split_with<N>() where it splits the range up to N times (instead of just once); N can default to 1, of course.

Now, the implementation of this function leaves a lot to be desired. The biggest problem stems from the usage of indices. As a general rule, working with ranges using indices is a bad idea. It’s all about the iterators.

Iterators are not only infinitely more powerful than indices... they’re actually faster. To understand why, consider these two simple loops:

// With indices:
for (auto i = 0uz; i != 10; ++i)
 sum += ptr[i];
// With iterators (pointers are iterators):
for (auto p = ptr; p != (p + 10); ++p)
 sum += *p;

Both loops do the same thing, but look deeper. With the indices, each time the loop is run, you have to take the index, multiply it by the size of the element, and then add it to ptr to get the actual address to read. But with the iterators (pointers), each time the loop is run you have to do... nothing. p is already the actual address to read. There is no need for any multiplication or addition.

Now, granted, in modern hardware, that multiply and addition is very fast, and likely effectively zero cost. And any decent compiler will be able to transform the index version to the iterator version while optimizing. So in practice, there’s no difference.

But that’s forgetting the fact that iterators can do so much more than indices. So even if there is no practical speed difference (and there may still be!), iterators are still the smarter choice.

And let me now prove the point, by showing you how simple this function becomes with iterators:

template <
 std::ranges::input_range R,
 std::indirect_unary_predicate<std::ranges::range_iterator_t<R>> Pred
>
auto span(R&& r, Pred&& pred)
{
 using vector_t = std::vector<std::ranges::range_value_t<R>>;
 using result_t = std::pair<vector_t, vector_t>;
 auto prefix = vector_t{};
 auto p = std::ranges::begin(r);
 auto const end = std::ranges::end(r);
 while ((p != end) and pred(*p))
 prefix.push_back(*p);
 return result_t{std::move(prefix), vector_t(p, end)};
}

(There is some complexity I’m glossing over here, such as how to handle ranges that aren’t common ranges. The right way would probably require C++23, and writing vector_t(std::from_range, std::ranges::subrange{p, end}). But, meh.)

Left fold

This seems like a pretty simple function, but there are a lot of dark corners hidden here.

The standard left fold algorithm is std::accumulate(). (There is no ranges version of accumulate()... yet.) So you could rewrite this function as:

template <typename A, typename B, typename F>
B foldleft(const Vec<A>& va, B z, F f)
{
 return std::accumulate(std::ranges::begin(va), std::ranges::end(va), z, f);
}

But there is a little wrinkle.

You see, std::accumulate() is specified (since C++20) to repeatedly move the result value. It would be as if you wrote:

template <typename R, typename B, typename F>
auto foldleft(R const& r, B z, F f)
{
 for (auto const& a : r)
 z = f(std::move(z), a); 
 return z;
}

Note there is no more tmpResult; that not only becomes unnecessary, it becomes an efficiency problem, because you either have to have an extra move, or a wholly unnecessary copy.

The reason why this is important is... well, what if B is a move-only type?

Even if it’s not a move-only type, what if it is an expensive-to-copy type, like std::string? The way foldleft() is currently written, you are guaranteed to pay for at least 1 copy (B tmpResult = z;). And there is no way to reuse expensive types, whereas, if you did f(move(z), a), f() could take the first argument by value, modify it, and then return it, all with no copies.

For example:

enum class nucleobase
{
 adenine,
 cytosine,
 guanine,
 thymine,
};
auto to_string(nucleobase n)
{
 using namespace std::string_literals;
 switch (n)
 {
 using enum nucleobase;
 case adenine: return "A"s;
 case cytosine: return "C"s;
 case guanine: return "G"s;
 case thymin: return "T"s;
 }
 throw std::invalid_argument{"not a known nucleobase"};
}
auto build_genome_string(std::string current_genome, nucleobase new_nucleobase)
{
 current_genome += to_string(new_nucleobase);
 return current_genome; // implicit move
}
auto genome = std::vector{
 nucleobase::guanine,
 nucleobase::adenine,
 nucleobase::thymine,
 nucleobase::thymine,
 nucleobase::adenine,
 nucleobase::cytosine,
 nucleobase::adenine,
};
auto genome_string = foldleft(genome, std::string{}, build_genome_string);
// returns "GATTACA"s;

With your original version, the init string is copied to tmpResult... that never happens in my std::accumulate()-like version. And then, in the original version, every time f(tmpResult, a) happens, which is build_genome_string(tmpResult, a), the string gets copied again from tmpResult to current_genome. With the std::accumulate()-like version... not a single copy of the string ever happens. Not even once. And that’s super important because as the string grows, it naturally reserves extra space each time, so you’ll reach a point where the number of re-allocations is effectively zero... whereas if the string is repeatedly copied, you could end up with many hundreds or even thousands—or, for a human genome, billions—of re-allocations. And, in the std::accumulate()-like version, you could reduce the number of re-allocations to literally zero, by using a string that has the memory pre-allocated as the init.

Scan left

In C++-ese, this an std::exclusive_scan(), because it has an initialzer. Without the initializer, it would be an inclusive scan.

As with span(), the biggest problem here is the use of indices to loop. I understand why you went this way, because:

You need to keep track of the position in two vectors: va and resultVector; and
resultVector is always changing, so you can’t keep a consistent iterator to it.

However, the key insight here is that, for every loop iteration, resultVector.at(index) is always resultVector.back(). So you actually only need to keep track of the position in va, and that vector isn’t changing, so iterators are fine.

Also, as an aside... vector::at() is a code smell, because the only difference between va.at(index) and va[index] is that va.at(index) checks first to make sure index is valid. But... if you don’t know for sure that index is valid... something else is very, very wrong. So you should never need that check. You certainly don’t need it here.

So, the function could just be:

template <typename A, typename B, typename F>
auto scanleft(std::vector<A> const& va, B z, F f)
{
 auto result_vector = std::vector{z};
 for (auto&& a : va)
 result_vector.push_back(f(result_vector.back(), a));
 return result_vector;
}

Note that I have removed result, because it is superfluous, and because by putting the result of f() directly into push_back(), it gets moved, not copied. (You could have also written resultVector.push_back(std::move(result))... but... why bother?)

Of course, all the other stuff I mentioned applies, like that you should use a generic range rather than a vector as the argument, you should provide allocator support, and so on.

Group by

With everything else I’ve mentioned, there’s not much to add here. Really, the only novel suggestion is that I would move or forward eqClass on the line resultMap.insert({eqClass, {a}}), rather than copying. Something like:

template <
 std::ranges::input_range R,
 typename F
>
 requires std::regular_invocable<F&, std::add_lvalue_reference_t<std::ranges::range_value_t<R>>>
auto groupby(R&& r, F&& f)
{
 using input_val_t = std::ranges::range_value_t<R>;
 using result_key_t = std::invoke_result_t<F&, std::add_lvalue_reference_t<input_val_t>>;
 using result_val_t = std::vector<input_val_t>;
 using result_map_t = std::unordered_map<result_key_t, result_val_t>;
 auto result_map = result_map_t{};
 for (auto&& val : std::forward<R>(r))
 {
 auto&& eq_class = f(val);
 if (auto pos = result_map.find(eq_class); pos == result_map.end())
 {
 result_map.emplace(
 std::forward<decltype(eq_class)>(eq_class),
 result_val_t{std::forward<decltype(val)>(val)}
 );
 }
 else
 {
 pos->second.push_back(std::forward<decltype(val)>(val));
 }
 }
 return result_map;
}

And, of course, it would be nice if it were possible to specify the key type, the value type, the hash function, the compare function, the allocator, etc..

Future C++ (C++23+)

Okay, so, "modern" C++ usually means C++11 or better, sometimes C++17 or better... but I’d like to talk about the future.

You see, C++20 really changed EVERYTHING, and it’s only going to get crazier with C++23 (which is just around the corner). C++20 introduced ranges, and pipelining, and there’s a very real chance of eventually getting an actual pipeline rewrite operator (|>). These are all about composability, so all-in-one functions like the ones you’re writing... they’re not really the future of C++.

Let me show you what I mean. Here’s what it looks like to take a sequence of integers and convert it to a vector strings, first using your interface (by default, ints would have to be a vector using your interface, but your interface could be easily extended to support generic ranges, as I suggested, so let’s assume you’ve done that):

auto strings = map(ints, to_string);

... and now using C++23:

auto strings = ints
 | std::ranges::views::transform(to_string)
 | std::ranges::to<std::vector>();

The only C++23 feature there is ranges::to. You can implement that in C++20, but there are a lot of moving parts you’d need to consider, and you’d have to fudge a fair bit.

In C++20, you’d have to do:

auto v = ints | std::ranges::views::transform(to_string);
// Luckily, v will be a common range (because ints is a common range), so we
// can just create the vector directly.
//
// If the v *weren't* a common range, we'd either have to use views::common,
// or, if even that won't work, jump through even more hoops like creating the
// strings vector first, using reserve, then using ranges::copy() and
// back_inserter. Yeah, it's a mess. That's why we got ranges::to in C++23.
auto strings = std::vector(std::ranges::begin(v), std::ranges::end(v));

Now, you may say that your version is superior, because it’s much shorter. However... you’d be missing the point.

The point is composability: the ability to write smaller pieces, and have them compose cleanly and efficiently. I can’t even begin to show the true power and magic of composability.

For starters, to address the length problem, you could create a custom range adaptor, and end up with:

auto strings = ints | map(to_string);

But, again, that’s just the tip of the iceberg.

Imagine you want to search for hash collisions of simple words. You could read a dictionary of words, strip out anything that isn’t a simple word, convert them all to lower case, hash them, and then look for duplicate hashes. You might think this would be a complicated program. However:

// Warning: untested code, written from the hip, may not compile or work as-is
// without some tweaking.
using hash_type = int; // or whatever
auto calculate_hash(std::string const& s) -> hash_type
{
 // ... whatever ...
}
auto main() -> int
{
 namespace ranges = std::ranges;
 namespace views = std::ranges::views;
 auto const path = std::filesystem::path{"/usr/share/dict/words"};
 auto const& locale = std::locale::global{};
 // Helper functions ------------------------------------------------
 auto const is_alpha = [&locale](auto const& s)
 {
 return ranges::all_of(s, [&locale](char c) { return std::isalpha(c, locale); };
 };
 auto const to_lower = [&locale](auto s)
 {
 // Okay, yeah, this is a dumb-brained to_lower(), but this is not a
 // conversation about Unicode.
 ranges::transform(s, std::ranges::begin(s), [&locale](char c) { return std::tolower(c, locale); });
 return s;
 };
 auto const make_hash = [](auto s)
 {
 auto hash = calculate_hash(s);
 return std::pair{std::move(hash), std::move(s)};
 };
 auto const by_hash = [](auto&& v) { return std::get<hash_type>(v); };
 // And here we go --------------------------------------------------
 // Open the input stream:
 auto strings = std::ifstream{path};
 strings.exceptions(std::ios_base::failbit | std::ios_base::badbit);
 // Generate the dictionary of hashes (a flat map with multiple keys using
 // a vector):
 auto hashes_view = views::istream<std::string>(strings)
 | views::filter(is_alpha)
 | views::transform(to_lower)
 | views::transform(make_hash);
 auto hashes = std::vector<std::pair<hash_type, std::string>>{};
 ranges::copy(hashes_view, std::back_inserter(hashes));
 // Sort the dictionary by hash:
 ranges::sort(hashes, {}, by_hash);
 // Produce a list of duplicated hashes:
 // (All of the next few chunks is because we don't have a pairwise view in C++20)
 auto duplicated_hashes_view = views::iota(decltype(ranges::size(hashes))(1), ranges::size(hashes))
 | views::filter([&hashes](auto i) { return std::get<hash_type>(hashes[i]) == std::get<hash_type>(hashes[i - 1]); })
 | views::transform([&hashes](auto i) { return std::get<hash_type>(hashes[i]) };
 auto duplicated_hashes = std::vector<hash_type>{};
 duplicated_hashes.reserve(ranges::size(duplicated_hashes_view));
 duplicated_hashes.assign(ranges::begin(duplicated_hashes_view), ranges::end(duplicated_hashes_view));
 auto duplicated_hashes_dupes = ranges::unique(duplicated_hashes);
 duplicated_hashes.erase(ranges::begin(duplicated_hashes_dupes), ranges::end(duplicated_hashes_dupes));
 // Remove all non-duplicated hashes.
 std::erase_if(hashes, [&duplicated_hashes](auto&& h) { return ranges::find(duplicated_hashes, std::get<hash_type>(h)) == ranges::end(duplicated_hashes); });
 // Convert the flat map with duplicate keys into a flat multimap
 auto duplicates = std::multimap<hash_type, std::string>(ranges::begin(hashes), ranges::end(hashes));
 // And... print:
 for (auto&& hash : duplicates | views::keys)
 {
 std::cout << hash << ":\n";
 auto const [b, e] = duplicates.equal_range(hash);
 ranges::for_each(b, e, [](auto&& s) { std::cout << "\t" << s << "\n"; })
 }
}

The above is C++20, and although it gets a little hoary (and buggy, for empty word lists) in the middle due to the tragic lack of range adaptors in C++20, it’s not that bad.

But this is what it might look like in C++23 and beyond, everything from the "and here we go" comment and below:

 // Open the input stream:
 auto strings = std::ifstream{path};
 strings.exceptions(std::ios_base::failbit | std::ios_base::badbit);
 // Generate the dictionary of hashes (a flat map with multiple keys using
 // a vector):
 auto const have_equal_hashes = [](auto&& p)
 {
 auto&& h1 = std::get<0>(p);
 auto&& h2 = std::get<1>(p);
 return std::get<hash_type>(h1) == std::get<hash_type>(h2);
 };
 // Pretty much the whole program is this single line!!!
 auto duplicates = views::istream<std::string>(strings)
 | views::filter(is_alpha)
 | views::transform(to_lower)
 | views::transform(make_hash)
 | actions::sort({}, by_hash) // Not yet standardized (but exists in range-v3)
 | views::pairwise // C++23
 | views::filter(have_equal_hashes)
 | views::transform([](auto&& t) { return std::array{std::get<0>(t), std::get<1>(t)}; })
 | views::join
 | views::unique({}, by_hash) // Proposed (but might not make C++23)
 | ranges::to<std::multimap>(); // C++23
 // And... print:
 for (auto&& hash : duplicates | views::keys)
 {
 std::cout << hash << ":\n";
 auto const [b, e] = duplicates.equal_range(hash);
 ranges::for_each(b, e, [](auto&& s) { std::cout << "\t" << s << "\n"; })
 }

As you can see, the whole program can be a single line. You can also see how much code just... disappears... between the C++20 and C++23+ versions. This is what the future looks like. (And, frankly, I may even be underestimating how much simpler future code could be.)

Even with just a simple example like the one I’ve been using of converting a bunch of numbers to strings... if you want to do just a little more, then the model of using an all-in-one function falls apart. For example, say I want to convert a bunch of numbers to strings, and then, because I’m superstitious, remove any numbers with 8 in them. How could I do that with map()? I can’t. I’d have to do it in two steps:

auto strings = map(views::iota(0, 100), [](auto i) { return std::to_string(i); });
std::erase_if(strings, [](auto&& s) { return s.contains('8'); });

But that’s not great, because it means creating a vector with 100 strings, and then removing the undesired ones. Whereas, if I do this:

auto const strings = views::iota(0, 100)
 | views::transform([](auto i) { return std::to_string(i); })
 | views::filter([](auto&& s) { return s.contains('8'); })
 | ranges::to<std::vector>();
// Or, in C++20:
auto const v = views::iota(0, 100)
 | views::transform([](auto i) { return std::to_string(i); })
 | views::filter([](auto&& s) { return s.contains('8'); });
auto const strings = std::vector(ranges::begin(v), ranges::end(v));

... then the vector is only created with the necessary amount of strings. Also, I can make it const without any trickery.

Keep in mind, though, that future C++ doesn’t necessarily make everything you’ve written meaningless. I mean, map() is just transform(), sure... and flatmap() is just transform() | join, sure... but groupby() is interesting. It might actually have helped in the hash collision example above.

The point I’m trying to illustrate is that if you really want to write really modern C++... as in, C++ for the future, not just the present... then what you need to look into is ranges. You need to study up on what ranges are, what views are and how they differ from containers, the difference between algorithms, views, and (potentially, in the future) actions, how to implement range adapters and range adapter closure objects (RACOs). And you need to restructure how you think about code, to move away from all-in-one algorithms like map(v, f), and toward composable concepts like v | transform(f) | to<vector>().

But all that... that’s a metric fuckton of work. And you won’t really reap the payoffs until the next version of C++, or maybe a version or two after that.

That’s why I suggest not bothering about being too clever, and just make what you have right now good. Don’t bother trying to support generating arbitrary output containers (but do look into accepting arbitrary ranges as input!). Vectors will work 90% of the time. That’s good enough for now. Maybe in a few years, when ranges::to is a thing, you can consider supporting arbitrary output containers (and/or restructuring all your algorithms into range adapters, or something like that). For now? Meh, don’t bother making something half-assed. Just do what you’re doing now well, and for the rest, wait for the future to come.

Loki Astari Loki Astari 97.7k5 gold badges126 silver badges341 bronze badges · Answer 1 · 2022-10-04 22:56:26Z

Map

template <typename A, typename F, typename B = typename std::invoke_result<F,A>::type>
Vec<B> map(const Vec<A>& va, F f) {
 Vec<B> result;
 for (const auto& a : va)
 result.push_back(f(a));
 
 return result;
}

Why limit yourself to vector. I would write for a generic container C. For this you should use the template template. Note the standard containers take two parameters; a type and an allocator (we need to specify this).

While we are at the function declaration, I would use the return type of auto so you don't need to write out the ho rendus type expression twice. Let the compiler work it out for you.

template<template<typename, typename> typename C, typename T, typename A, typename F>
auto map(C<T, A> const& container, F&& action)
{
 using Result = typename std::invoke_result<F,T>::type;
 C<Result, std::allocator<Result>> result;

Next: I would pre-allocate space for the resulting container.

 result.reserve(container.size());

Note: This will only work if your type C has a reserve method. So it will work for things like vector. But for things like std::list we need to do some meta programming to make it work.

#if __cplusplus == 202002L
template<typename C>
concept HasReserveMemberFunc = requires
{
 typename C::size_type;
 { std::declval<C>().reserve(std::declval<typename C::size_type>()) } -> std::same_as<void>;
};
#elif __cplusplus >= 201703L
template<typename C>
struct HasReserveMemberFuncType
{
 private:
 // If &U::reserve fails to compile then SFINAE ensures this is not a compiler error.
 // If just means this function does not exist in that case.
 template<typename U>
 static constexpr std::enable_if_t<std::is_member_pointer_v<decltype(&U::reserve)>, char> Test(int);
 // Notice the return type of this version is int
 // This function is always available.
 // But if the above function is available it will be chosen over this alternative as
 // it has an exact match with the parameter while this function will only be chosen if
 // the above function does not exist (Note: will not exist if it is removed by SFINAE).
 template<typename U>
 static constexpr int Test(...);
 public:
 // The value here is true if Test(int) is available which only happens
 // If C has a member reserve.
 static constexpr bool value = sizeof(Test<C>(0)) == sizeof(char);
};
template<typename C>
inline constexpr bool HasReserveMemberFunc = HasReserveMemberFuncType<C>::value;
#else
// You can do it with C++11
#error "You are out of luck"
#endif
template<typename C>
void reserve(C& c, std::size_t size)
{
 if constexpr (HasReserveMemberFunc<C>) {
 c.reserve(size);
 }
}

So now I would write map like this:

template<template<typename, typename> typename C, typename T, typename A, typename F>
auto map(C<T, A> const& container, F&& action)
{
 using Result = typename std::invoke_result<F,T>::type;
 C<Result, std::allocator<Result>> result;
 reserve(result, container.size());
 for (auto const& val : container) {
 result.push_back(action(val));
 }
 
 return result;
}

When meta programming, I would stay away from member functions when standard standalone versions exists. As not all types will have the members, but the standard will override them for most types to get standard behaviour.

std::begin(x) rather than x.begin()
std::end(x) rather than x.end()
std::size(x) rather than x.size()
etc... (not sure about others).

So this line:

finalResultVector.insert(finalResultVector.end(), elementResult.begin(), elementResult.end());

becomes:

finalResultVector.insert(std::end(finalResultVector),
 std::begin(elementResult), std::end(elementResult));

Be careful about passing vectors by value:

 Vec<B> map(const Vec<A>& va, F f) { // In map pass by const ref
 Vec<B> flatmap(Vec<A> va, F f) { // In flatmap pass by value

I would not use index based loops. But would prefer you to use iterators.

 for(size_t index = 0; index<va.size(); index++){

It seem more natural in C++ to use either range based, or if you can't use range based loops then standard algorithms, if you can use algorithms then iterator based loops and finally if nothing else works then look at index based loops:

for(auto loop = std::begin(va); loop != std::end(va); ++loop){

Don't copy values out of containers when using a reference will do and prefer operator[] over at().

 auto a = va.at(index);
 // I would do:
 auto& a = va[index];

Look at standard algorithms that you can use:

Example partition_copy() could (potentially) be used to implement your span function.

Think about situations where move semantics are important. Can we destructively remove items from the source using a move (rather than a copy). This may make a lot of these algorithms much more efficient when the object in the container is non trivial.

Using a template template and shenanigans to assume/guess the second parameter as an allocator seems a bit pointless when the only standard container the function will work with is a vector in any case.

indi indi 16.4k2 gold badges25 silver badges64 bronze badges · Answer 2 · 2022-10-08 22:21:34Z

I’m going to go in a different direction from @MartinYork’s review, and suggest that you should stick with just vectors, and not bother trying to support arbitrary containers. I think supporting arbitrary containers is far too complex, and not worth the effort because you’re probably going to be using vectors 90% of the time anyway. If you do want to support arbitrary containers... well, I’ll talk a bit about that at the end. I"ll also talk a bit about fitting into future C++, not just modern C++.

General stuff

Before I focus on the individual algorithms, there are a couple of general things that apply overall that I want to comment on.

First:

#include <type_traits>
#include <iostream>
#include <vector>
#include <utility>
#include <unordered_map>
#include "show.h"
#include "utils.hpp"

There are a couple of headers that aren’t included in the review. I presume they don’t matter?

<iostream> also doesn’t seem to serve a purpose.

 for(size_t index = 0; index<va.size(); index++){

You use size_t a couple places, but it should be spelled std::size_t.

Also, as a general rule, you shouldn’t write raw for loops... but when you do, you should use the following structure:

for (type name = initializer; name != limit; ++name)

In other words, don’t use <, use !=. You will find this produces better code gen.

Also, always use prefix increment, not postfix increment, unless you really mean it. It won’t make a difference for a simple unsigned integer, but it could make an enormous difference with certain types of iterator.

size_t should work, but the right thing to do is to use the container’s size_type. The best way to do that is probably something like this:

for (auto index = std::ranges::range_size_t<Vec<A>>{}; index != std::ranges::size(va); ++index)
// OR:
for (auto index = decltype(std::ranges::size(va)){}; index != std::ranges::size(va); ++index)

Ugly, yes, but, again, you shouldn’t be writing raw loops anyway. And even when you must, using indices is a bad idea (unless you actually need them, of course). (And, in fact, you don’t need them. But we’ll get to that.)

Then there are the aliases:

template <typename T> using Vec = std::vector<T>;
template <typename K, typename V> using Map = std::unordered_map<K,V>;

I’m struggling to see the point of these aliases. They don’t really add anything to the code, and they don’t help at all with readability.

In fact, quite the opposite: in practice, if I came across code like Vec<B> map(const Vec<A>& va, F f), I would curse and mutter, "okay, now, what is Vec?" and have to embark on a search of the code base to find out where it’s defined. On the other hand, if I came across std::vector<B> map(const std::vector<A>& va, F f)... well, everything I need to know is right there. There are no mysteries.

There is a fine line between simplification and obfuscation. Aliases should be about the former, not the latter. If it doesn’t help understanding, then it’s obfuscation. Vec<T> does not help understanding anything more than std::vector<T>, so it’s not worth the alias.

Speaking of the types... I know I said you should stick with vectors... and you should... but you should also take allocators into account. Personally, I use custom allocators (and polymorphic allocators) a lot and they can make for absolutely ginormous performance boosts. Being restricted to std::allocator<> pretty much voids it for me.

Adding allocator support is fairly trivial, so there’s not really much reason not to.

Finally:

Again, I know I said that you should stick with vectors... and you should... but that only means you should stick with vectors as the return type. There is no reason you need to limit the argument type to vectors.

For example, why wouldn’t you want to allow this?:

auto ints = std::ranges::views::iota(1, 5);
auto strs = map(ints, to_string);
// strs is a vector<string> containing:
// "1", "2", "3", "4"

Allowing arbitrary return types is hard. Allowing arbitrary argument types is easy. In fact, it’s trivial. In many cases, the function body won’t even change. In some cases, there will even be less code.

So let’s get into the specific functions.

Map

So, let me start by illustrating some of the general suggestions I made to the interface:

template <
 std::ranges::input_range R,
 typename F,
 typename B = std::invoke_result_t<F&, std::ranges::range_value_t<R>>,
 typename Alloc = std::allocator<B>
>
 requires std::regular_invocable<F&, std::ranges::range_value_t<R>>
auto map(R&& r, F&& f) -> std::vector<B, Alloc>
{
 // Just forward the call to the allocator version:
 return map(std::forward<R>(r), std::forward<F>(f), {});
}
// This overload lets you provide an allocator:
template <
 std::ranges::input_range R,
 typename F,
 typename B = std::invoke_result_t<F&, std::ranges::range_value_t<R>>,
 typename Alloc = std::allocator<B>
>
 requires std::regular_invocable<F&, std::ranges::range_value_t<R>>
auto map(R&&, F&&, Alloc const&) -> std::vector<B, Alloc>;

As you can see, now you can take any range as an argument, and you can use custom allocators.

The body of the function is almost unchanged:

template <
 std::ranges::input_range R,
 typename F,
 typename B = std::invoke_result_t<F&, std::ranges::range_value_t<R>>,
 typename Alloc = std::allocator<B>
>
 requires std::regular_invocable<F&, std::ranges::range_value_t<R>>
auto map(R&& r, F&& f, Alloc const& alloc) -> std::vector<B, Alloc>
{
 auto result = std::vector<B, Alloc>(alloc);
 if constexpr (std::ranges::sized_range<R>)
 result.reserve(std::ranges::size(r));
 for (auto&& a : std::forward<R>(r))
 result.push_back(f(std::forward<decltype(a)>(a)));
 return result;
}

The only changes are that I added a conditional reserve, did a bunch of forwarding for maximal efficiency, and, of course, constructed the result vector with the provided allocator. All of those changes (other than using the allocator, and the variable name changes) are not technically necessary; your existing code could be used literally unchanged. They should increase performance in some cases, though.

(Technically, you shouldn’t just use range_value_t<R> in regular_invocable<F&, range_value_t<R>> and invoke_result_t<F&, range_value_t<R>>, because, depending on the value category of R, you may be calling the function with a (possibly const) lvalue reference, or an rvalue. The correct thing to do is to use range_reference_t<R> or range_rvalue_reference_t<R>, depending on the category of R... or consider using indirect_result_t<F&, range_iterator_t<R>> instead of invoke_result, and indirectly_unary_invocable or indirectly_regular_unary_invocable instead of invocable or regular_invocable.)

There is one thing about this interface that I really don’t like, though. You provide a template parameter B that determines the value type of the result range. That’s fine... but... it’s the third template parameter.

To illustrate why that’s a problem, suppose I have a function object that converts an int to a float... but I want a double result:

auto const ints = std::vector{1, 2, 3, 4};
struct to_float
{
 constexpr auto operator()(int i) const noexcept -> float { return i; }
};
// This produces vector<float>:
auto floats = map(ints, to_float{});
// But I want vector<double>.
// I *want* to do this:
auto doubles = map<double>(ints, to_float{});
// ... but that won't work.
// I have to do this:
auto doubles = map<decltype(ints), to_float, double>(ints, to_float{});
// ... but THAT WON'T WORK EITHER!!!
// Because of the way argument deduction and reference collapsing work,
// I actually have to do THIS:
auto doubles = map<decltype(ints)&, to_float, double>(ints, to_float{});
// ... or, more correctly:
auto doubles = map<std::add_lvalue_reference_t<decltype(ints)>, to_float, double>(ints, to_float{});
// ... which is absurd.

I would suggest either taking that template parameter out completely, because it’s unnecessary:

template <
 std::ranges::input_range R,
 typename F,
 typename Alloc = std::allocator<std::invoke_result_t<F&, std::ranges::range_value_t<R>>>
>
 requires std::regular_invocable<F&, std::ranges::range_value_t<R>>
auto map(R&& r, F&& f)
{
 return map(std::forward<R>(r), std::forward<F>(f), {});
}
template <
 std::ranges::input_range R,
 typename F,
 typename Alloc
>
 requires std::regular_invocable<F&, std::ranges::range_value_t<R>>
auto map(R&& r, F&& f, Alloc const& alloc)
{
 auto result = std::vector<std::invoke_result_t<F&, std::ranges::range_value_t<R>>, Alloc>(alloc);
 if constexpr (std::ranges::sized_range<R>)
 result.reserve(std::ranges::size(r));
 for (auto&& a : std::forward<R>(r))
 result.push_back(f(std::forward<decltype(a)>(a)));
 return result;
}

OR restructure your functions so that the result value type is the first template parameter (possibly deduced), so you can do map<double>(ints, to_float{}) and get a vector<double> as the result. I’ll leave how to do that as an exercise for the reader.

Incidentally, as a general rule, you shouldn’t use raw loops... yes, even in a simple case like this. That for loop could be:

std::ranges::for_each(std::forward<R>(r), [&result, &f](auto&& a) { result.push_back(f(a)); });
// Forwarding of a removed just to make the line shorter.

But there’s little point to that here.

However... the entire algorithm is basically just std::ranges::transform() (transform() is how C++ spells monadic map.)

Which means:

template <
 std::ranges::input_range R,
 typename F,
 typename B = std::invoke_result_t<F&, std::ranges::range_value_t<R>>,
 typename Alloc = std::allocator<B>
>
 requires std::regular_invocable<F&, std::ranges::range_value_t<R>>
auto map(R&& r, F&& f, Alloc const& alloc) -> std::vector<B, Alloc>
{
 auto result = std::vector<B, Alloc>(alloc);
 if constexpr (std::ranges::sized_range<R>)
 result.reserve(std::ranges::size(r));
 std::ranges::transform(std::forward<R>(r), std::back_inserter(result), f);
 return result;
}

Which, aside from the reserving, is basically a one-liner.

We’ll get back to that, though.

Flat map

Pretty much everything that applies to map() applies here as well. The only novel stuff is in the heart of the loop.

Before that, though, I think there are some typos in the argument list. You take the source vector by value... which means it’s copied. Don’t you want to take it by reference, either const& or a forwarding reference?

Anywho, the loop:

 Vec<B> elementResult = f(a);
 finalResultVector.insert(finalResultVector.end(), elementResult.begin(), elementResult.end());

Now, I would say, there is no need force the return from the function into a vector. Just use auto. Constrain it if you must:

 std::ranges::input_range auto elementResult = f(a);
 finalResultVector.insert(end(finalResultVector), begin(elementResult), end(elementResult));

As of C++23, vectors get a new function you may find very useful:

 finalResultVector.append_range(f(a));

So, because it’s impractical to figure out the size to reserve, the function is really just:

template <
 std::ranges::input_range R,
 typename F
>
auto flatmap(R&& r, F&& f)
{
 using func_result_t = std::invoke_result_t<F&, std::ranges::range_value_t<R>>;
 auto result = std::vector<std::invoke_result_t<F&, std::ranges::range_value_t<func_result_t>>>{};
 for (auto&& a : std::forward<R>(r))
 result.append_range(f(std::forward<decltype<a>(a)));
 return result;
}

Span

This is actually a neat algorithm, and I struggled to think of a standard algorithm that does quite the same job. (I mean, it’s easily approximated by standard algorithms, but nothing does exactly the same job that I can think of.)

My biggest objection is to the name. "Span" already means something in C++, and it’s not this. And I don’t really see how splitting a range into two parts based on a predicate is "spanning". To me, a more logical name is something like split_at() or split_with(). It might even make sense to do split_with<N>() where it splits the range up to N times (instead of just once); N can default to 1, of course.

Now, the implementation of this function leaves a lot to be desired. The biggest problem stems from the usage of indices. As a general rule, working with ranges using indices is a bad idea. It’s all about the iterators.

Iterators are not only infinitely more powerful than indices... they’re actually faster. To understand why, consider these two simple loops:

// With indices:
for (auto i = 0uz; i != 10; ++i)
 sum += ptr[i];
// With iterators (pointers are iterators):
for (auto p = ptr; p != (p + 10); ++p)
 sum += *p;

Both loops do the same thing, but look deeper. With the indices, each time the loop is run, you have to take the index, multiply it by the size of the element, and then add it to ptr to get the actual address to read. But with the iterators (pointers), each time the loop is run you have to do... nothing. p is already the actual address to read. There is no need for any multiplication or addition.

Now, granted, in modern hardware, that multiply and addition is very fast, and likely effectively zero cost. And any decent compiler will be able to transform the index version to the iterator version while optimizing. So in practice, there’s no difference.

But that’s forgetting the fact that iterators can do so much more than indices. So even if there is no practical speed difference (and there may still be!), iterators are still the smarter choice.

And let me now prove the point, by showing you how simple this function becomes with iterators:

template <
 std::ranges::input_range R,
 std::indirect_unary_predicate<std::ranges::range_iterator_t<R>> Pred
>
auto span(R&& r, Pred&& pred)
{
 using vector_t = std::vector<std::ranges::range_value_t<R>>;
 using result_t = std::pair<vector_t, vector_t>;
 auto prefix = vector_t{};
 auto p = std::ranges::begin(r);
 auto const end = std::ranges::end(r);
 while ((p != end) and pred(*p))
 prefix.push_back(*p);
 return result_t{std::move(prefix), vector_t(p, end)};
}

(There is some complexity I’m glossing over here, such as how to handle ranges that aren’t common ranges. The right way would probably require C++23, and writing vector_t(std::from_range, std::ranges::subrange{p, end}). But, meh.)

Left fold

This seems like a pretty simple function, but there are a lot of dark corners hidden here.

The standard left fold algorithm is std::accumulate(). (There is no ranges version of accumulate()... yet.) So you could rewrite this function as:

template <typename A, typename B, typename F>
B foldleft(const Vec<A>& va, B z, F f)
{
 return std::accumulate(std::ranges::begin(va), std::ranges::end(va), z, f);
}

But there is a little wrinkle.

You see, std::accumulate() is specified (since C++20) to repeatedly move the result value. It would be as if you wrote:

template <typename R, typename B, typename F>
auto foldleft(R const& r, B z, F f)
{
 for (auto const& a : r)
 z = f(std::move(z), a); 
 return z;
}

Note there is no more tmpResult; that not only becomes unnecessary, it becomes an efficiency problem, because you either have to have an extra move, or a wholly unnecessary copy.

The reason why this is important is... well, what if B is a move-only type?

Even if it’s not a move-only type, what if it is an expensive-to-copy type, like std::string? The way foldleft() is currently written, you are guaranteed to pay for at least 1 copy (B tmpResult = z;). And there is no way to reuse expensive types, whereas, if you did f(move(z), a), f() could take the first argument by value, modify it, and then return it, all with no copies.

For example:

enum class nucleobase
{
 adenine,
 cytosine,
 guanine,
 thymine,
};
auto to_string(nucleobase n)
{
 using namespace std::string_literals;
 switch (n)
 {
 using enum nucleobase;
 case adenine: return "A"s;
 case cytosine: return "C"s;
 case guanine: return "G"s;
 case thymin: return "T"s;
 }
 throw std::invalid_argument{"not a known nucleobase"};
}
auto build_genome_string(std::string current_genome, nucleobase new_nucleobase)
{
 current_genome += to_string(new_nucleobase);
 return current_genome; // implicit move
}
auto genome = std::vector{
 nucleobase::guanine,
 nucleobase::adenine,
 nucleobase::thymine,
 nucleobase::thymine,
 nucleobase::adenine,
 nucleobase::cytosine,
 nucleobase::adenine,
};
auto genome_string = foldleft(genome, std::string{}, build_genome_string);
// returns "GATTACA"s;

With your original version, the init string is copied to tmpResult... that never happens in my std::accumulate()-like version. And then, in the original version, every time f(tmpResult, a) happens, which is build_genome_string(tmpResult, a), the string gets copied again from tmpResult to current_genome. With the std::accumulate()-like version... not a single copy of the string ever happens. Not even once. And that’s super important because as the string grows, it naturally reserves extra space each time, so you’ll reach a point where the number of re-allocations is effectively zero... whereas if the string is repeatedly copied, you could end up with many hundreds or even thousands—or, for a human genome, billions—of re-allocations. And, in the std::accumulate()-like version, you could reduce the number of re-allocations to literally zero, by using a string that has the memory pre-allocated as the init.

Scan left

In C++-ese, this an std::exclusive_scan(), because it has an initialzer. Without the initializer, it would be an inclusive scan.

As with span(), the biggest problem here is the use of indices to loop. I understand why you went this way, because:

You need to keep track of the position in two vectors: va and resultVector; and
resultVector is always changing, so you can’t keep a consistent iterator to it.

However, the key insight here is that, for every loop iteration, resultVector.at(index) is always resultVector.back(). So you actually only need to keep track of the position in va, and that vector isn’t changing, so iterators are fine.

Also, as an aside... vector::at() is a code smell, because the only difference between va.at(index) and va[index] is that va.at(index) checks first to make sure index is valid. But... if you don’t know for sure that index is valid... something else is very, very wrong. So you should never need that check. You certainly don’t need it here.

So, the function could just be:

template <typename A, typename B, typename F>
auto scanleft(std::vector<A> const& va, B z, F f)
{
 auto result_vector = std::vector{z};
 for (auto&& a : va)
 result_vector.push_back(f(result_vector.back(), a));
 return result_vector;
}

Note that I have removed result, because it is superfluous, and because by putting the result of f() directly into push_back(), it gets moved, not copied. (You could have also written resultVector.push_back(std::move(result))... but... why bother?)

Of course, all the other stuff I mentioned applies, like that you should use a generic range rather than a vector as the argument, you should provide allocator support, and so on.

Group by

With everything else I’ve mentioned, there’s not much to add here. Really, the only novel suggestion is that I would move or forward eqClass on the line resultMap.insert({eqClass, {a}}), rather than copying. Something like:

template <
 std::ranges::input_range R,
 typename F
>
 requires std::regular_invocable<F&, std::add_lvalue_reference_t<std::ranges::range_value_t<R>>>
auto groupby(R&& r, F&& f)
{
 using input_val_t = std::ranges::range_value_t<R>;
 using result_key_t = std::invoke_result_t<F&, std::add_lvalue_reference_t<input_val_t>>;
 using result_val_t = std::vector<input_val_t>;
 using result_map_t = std::unordered_map<result_key_t, result_val_t>;
 auto result_map = result_map_t{};
 for (auto&& val : std::forward<R>(r))
 {
 auto&& eq_class = f(val);
 if (auto pos = result_map.find(eq_class); pos == result_map.end())
 {
 result_map.emplace(
 std::forward<decltype(eq_class)>(eq_class),
 result_val_t{std::forward<decltype(val)>(val)}
 );
 }
 else
 {
 pos->second.push_back(std::forward<decltype(val)>(val));
 }
 }
 return result_map;
}

And, of course, it would be nice if it were possible to specify the key type, the value type, the hash function, the compare function, the allocator, etc..

Future C++ (C++23+)

Okay, so, "modern" C++ usually means C++11 or better, sometimes C++17 or better... but I’d like to talk about the future.

You see, C++20 really changed EVERYTHING, and it’s only going to get crazier with C++23 (which is just around the corner). C++20 introduced ranges, and pipelining, and there’s a very real chance of eventually getting an actual pipeline rewrite operator (|>). These are all about composability, so all-in-one functions like the ones you’re writing... they’re not really the future of C++.

Let me show you what I mean. Here’s what it looks like to take a sequence of integers and convert it to a vector strings, first using your interface (by default, ints would have to be a vector using your interface, but your interface could be easily extended to support generic ranges, as I suggested, so let’s assume you’ve done that):

auto strings = map(ints, to_string);

... and now using C++23:

auto strings = ints
 | std::ranges::views::transform(to_string)
 | std::ranges::to<std::vector>();

The only C++23 feature there is ranges::to. You can implement that in C++20, but there are a lot of moving parts you’d need to consider, and you’d have to fudge a fair bit.

In C++20, you’d have to do:

auto v = ints | std::ranges::views::transform(to_string);
// Luckily, v will be a common range (because ints is a common range), so we
// can just create the vector directly.
//
// If the v *weren't* a common range, we'd either have to use views::common,
// or, if even that won't work, jump through even more hoops like creating the
// strings vector first, using reserve, then using ranges::copy() and
// back_inserter. Yeah, it's a mess. That's why we got ranges::to in C++23.
auto strings = std::vector(std::ranges::begin(v), std::ranges::end(v));

Now, you may say that your version is superior, because it’s much shorter. However... you’d be missing the point.

The point is composability: the ability to write smaller pieces, and have them compose cleanly and efficiently. I can’t even begin to show the true power and magic of composability.

For starters, to address the length problem, you could create a custom range adaptor, and end up with:

auto strings = ints | map(to_string);

But, again, that’s just the tip of the iceberg.

Imagine you want to search for hash collisions of simple words. You could read a dictionary of words, strip out anything that isn’t a simple word, convert them all to lower case, hash them, and then look for duplicate hashes. You might think this would be a complicated program. However:

// Warning: untested code, written from the hip, may not compile or work as-is
// without some tweaking.
using hash_type = int; // or whatever
auto calculate_hash(std::string const& s) -> hash_type
{
 // ... whatever ...
}
auto main() -> int
{
 namespace ranges = std::ranges;
 namespace views = std::ranges::views;
 auto const path = std::filesystem::path{"/usr/share/dict/words"};
 auto const& locale = std::locale::global{};
 // Helper functions ------------------------------------------------
 auto const is_alpha = [&locale](auto const& s)
 {
 return ranges::all_of(s, [&locale](char c) { return std::isalpha(c, locale); };
 };
 auto const to_lower = [&locale](auto s)
 {
 // Okay, yeah, this is a dumb-brained to_lower(), but this is not a
 // conversation about Unicode.
 ranges::transform(s, std::ranges::begin(s), [&locale](char c) { return std::tolower(c, locale); });
 return s;
 };
 auto const make_hash = [](auto s)
 {
 auto hash = calculate_hash(s);
 return std::pair{std::move(hash), std::move(s)};
 };
 auto const by_hash = [](auto&& v) { return std::get<hash_type>(v); };
 // And here we go --------------------------------------------------
 // Open the input stream:
 auto strings = std::ifstream{path};
 strings.exceptions(std::ios_base::failbit | std::ios_base::badbit);
 // Generate the dictionary of hashes (a flat map with multiple keys using
 // a vector):
 auto hashes_view = views::istream<std::string>(strings)
 | views::filter(is_alpha)
 | views::transform(to_lower)
 | views::transform(make_hash);
 auto hashes = std::vector<std::pair<hash_type, std::string>>{};
 ranges::copy(hashes_view, std::back_inserter(hashes));
 // Sort the dictionary by hash:
 ranges::sort(hashes, {}, by_hash);
 // Produce a list of duplicated hashes:
 // (All of the next few chunks is because we don't have a pairwise view in C++20)
 auto duplicated_hashes_view = views::iota(decltype(ranges::size(hashes))(1), ranges::size(hashes))
 | views::filter([&hashes](auto i) { return std::get<hash_type>(hashes[i]) == std::get<hash_type>(hashes[i - 1]); })
 | views::transform([&hashes](auto i) { return std::get<hash_type>(hashes[i]) };
 auto duplicated_hashes = std::vector<hash_type>{};
 duplicated_hashes.reserve(ranges::size(duplicated_hashes_view));
 duplicated_hashes.assign(ranges::begin(duplicated_hashes_view), ranges::end(duplicated_hashes_view));
 auto duplicated_hashes_dupes = ranges::unique(duplicated_hashes);
 duplicated_hashes.erase(ranges::begin(duplicated_hashes_dupes), ranges::end(duplicated_hashes_dupes));
 // Remove all non-duplicated hashes.
 std::erase_if(hashes, [&duplicated_hashes](auto&& h) { return ranges::find(duplicated_hashes, std::get<hash_type>(h)) == ranges::end(duplicated_hashes); });
 // Convert the flat map with duplicate keys into a flat multimap
 auto duplicates = std::multimap<hash_type, std::string>(ranges::begin(hashes), ranges::end(hashes));
 // And... print:
 for (auto&& hash : duplicates | views::keys)
 {
 std::cout << hash << ":\n";
 auto const [b, e] = duplicates.equal_range(hash);
 ranges::for_each(b, e, [](auto&& s) { std::cout << "\t" << s << "\n"; })
 }
}

The above is C++20, and although it gets a little hoary (and buggy, for empty word lists) in the middle due to the tragic lack of range adaptors in C++20, it’s not that bad.

But this is what it might look like in C++23 and beyond, everything from the "and here we go" comment and below:

 // Open the input stream:
 auto strings = std::ifstream{path};
 strings.exceptions(std::ios_base::failbit | std::ios_base::badbit);
 // Generate the dictionary of hashes (a flat map with multiple keys using
 // a vector):
 auto const have_equal_hashes = [](auto&& p)
 {
 auto&& h1 = std::get<0>(p);
 auto&& h2 = std::get<1>(p);
 return std::get<hash_type>(h1) == std::get<hash_type>(h2);
 };
 // Pretty much the whole program is this single line!!!
 auto duplicates = views::istream<std::string>(strings)
 | views::filter(is_alpha)
 | views::transform(to_lower)
 | views::transform(make_hash)
 | actions::sort({}, by_hash) // Not yet standardized (but exists in range-v3)
 | views::pairwise // C++23
 | views::filter(have_equal_hashes)
 | views::transform([](auto&& t) { return std::array{std::get<0>(t), std::get<1>(t)}; })
 | views::join
 | views::unique({}, by_hash) // Proposed (but might not make C++23)
 | ranges::to<std::multimap>(); // C++23
 // And... print:
 for (auto&& hash : duplicates | views::keys)
 {
 std::cout << hash << ":\n";
 auto const [b, e] = duplicates.equal_range(hash);
 ranges::for_each(b, e, [](auto&& s) { std::cout << "\t" << s << "\n"; })
 }

As you can see, the whole program can be a single line. You can also see how much code just... disappears... between the C++20 and C++23+ versions. This is what the future looks like. (And, frankly, I may even be underestimating how much simpler future code could be.)

Even with just a simple example like the one I’ve been using of converting a bunch of numbers to strings... if you want to do just a little more, then the model of using an all-in-one function falls apart. For example, say I want to convert a bunch of numbers to strings, and then, because I’m superstitious, remove any numbers with 8 in them. How could I do that with map()? I can’t. I’d have to do it in two steps:

auto strings = map(views::iota(0, 100), [](auto i) { return std::to_string(i); });
std::erase_if(strings, [](auto&& s) { return s.contains('8'); });

But that’s not great, because it means creating a vector with 100 strings, and then removing the undesired ones. Whereas, if I do this:

auto const strings = views::iota(0, 100)
 | views::transform([](auto i) { return std::to_string(i); })
 | views::filter([](auto&& s) { return s.contains('8'); })
 | ranges::to<std::vector>();
// Or, in C++20:
auto const v = views::iota(0, 100)
 | views::transform([](auto i) { return std::to_string(i); })
 | views::filter([](auto&& s) { return s.contains('8'); });
auto const strings = std::vector(ranges::begin(v), ranges::end(v));

... then the vector is only created with the necessary amount of strings. Also, I can make it const without any trickery.

Keep in mind, though, that future C++ doesn’t necessarily make everything you’ve written meaningless. I mean, map() is just transform(), sure... and flatmap() is just transform() | join, sure... but groupby() is interesting. It might actually have helped in the hash collision example above.

The point I’m trying to illustrate is that if you really want to write really modern C++... as in, C++ for the future, not just the present... then what you need to look into is ranges. You need to study up on what ranges are, what views are and how they differ from containers, the difference between algorithms, views, and (potentially, in the future) actions, how to implement range adapters and range adapter closure objects (RACOs). And you need to restructure how you think about code, to move away from all-in-one algorithms like map(v, f), and toward composable concepts like v | transform(f) | to<vector>().

But all that... that’s a metric fuckton of work. And you won’t really reap the payoffs until the next version of C++, or maybe a version or two after that.

That’s why I suggest not bothering about being too clever, and just make what you have right now good. Don’t bother trying to support generating arbitrary output containers (but do look into accepting arbitrary ranges as input!). Vectors will work 90% of the time. That’s good enough for now. Maybe in a few years, when ranges::to is a thing, you can consider supporting arbitrary output containers (and/or restructuring all your algorithms into range adapters, or something like that). For now? Meh, don’t bother making something half-assed. Just do what you’re doing now well, and for the rest, wait for the future to come.

Stack Exchange Network

Several container functions rewritten as an excercise

2 Answers 2

Map

General stuff

Map

Flat map

Span

Left fold

Scan left

Group by

Future C++ (C++23+)

Your Answer

Sign up or log in

Post as a guest

Post as a guest

Hot Network Questions

Several container functions rewritten as an excercise

2 Answers 2

Map

General stuff

Map

Flat map

Span

Left fold

Scan left

Group by

Future C++ (C++23+)

Your Answer

Sign up or log in

Post as a guest

Post as a guest

Related

Hot Network Questions