how do I write a function that can iterate over a generic type in a typesafe way

Question

I want to write a function that can input an iterator over a given generic type in a typesafe way. One possible use case would be writing a function like accumulate/map/fold:

#include <iterator>
#include <vector>
#include <functional>

template <typename V, typename K>
K accumulate(
      std::function<K(K, V)> accumulator,
      /* WHAT TYPE DO I PUT HERE */ it,
      /* WHAT TYPE DO I PUT HERE */ end,
      K initial) {
  K sum = initial;
  for (; it != end; ++it) {
    V item = *it;
    sum = accumulator(sum, item);
  }
  return sum;
}

How can I do this in a way that the compiler will check types and all that good stuff?

Previously asked here

Unclear what you're asking. Compiler will check the types in any case. Please, clarify, and "all that good stuff". — Ivan Aksamentov - Drop, Dec 15 '15 at 23:51
Meanwhile, you could get some inspiration on how STL-like implementations might look like in practice [HERE](http://en.cppreference.com/w/cpp/algorithm). For example, your [accumulate](http://en.cppreference.com/w/cpp/algorithm/accumulate). Of course, you can always open up your favorite Standard Library's header files and read them. P.S. Let's pray for C++17 and [concepts](http://en.cppreference.com/w/cpp/language/constraints). — Ivan Aksamentov - Drop, Dec 15 '15 at 23:55
Sam wants to avoid crashing nonsense like `bool a = false, b = true; bool *ap = &a, *bp = &b; print_all(ap, bp);` that would get past the basic type-checking. — user4581301, Dec 16 '15 at 00:03
Maybe I'm missing something obvious, but it seems to me the template just needs another parameter, "typename I", with "I" becoming"WHAT DO I PUT HERE". — Sam Varshavchik, Dec 16 '15 at 00:29
@T.C. Along the line of my first impression: Code review followed by a wagging finger or head smack. I'd expect a base class for all iterators on which you can do a `static_assert`, but I'm not finding anything pretty and simple. — user4581301, Dec 16 '15 at 00:38

score 0 · Answer 1 · answered Dec 16 '15 at 04:03

Study the patterns used in the containers of the standard library. The problem is you're trying to make explicit a number of types that the container should be defining. In addition, prudent use of auto means you don't have explicit declare some types at all.

template <typename C, typename R>
R accumulate(
      std::function<R(R, C::value_type)> accumulator,
      R initial
) {
  auto sum = initial;
  for (auto it = C.begin(); it != C.end(); ++it) {
    sum = accumulator(sum, *it);
  }
  return sum;
}

By using the container type as your template argument, you can rely upon its value_type definition for type safety on the accumulator function. By using auto for the iterators and using the standard begin() and end() methods, you don't have to even explicitly mention their type. (Just to be sure, they're C::iterator if you needed them.)

Avik Paul · Accepted Answer · 2015-12-16T07:11:43.107

I think I understood your question, and I can think of two different approaches, both has pros and cons :

[1] Use a 3rd template type for the iterators, say ITER. Advantage is easier code, works with more collection types, less restriction. Disadvantage is, does not capture the dependency constraint between ITER and V, i.e. ITER must be an iterator which iterates over type V, namely V = ITER::value_type.

[2] Explicitly call out the dependent type instead of creating new template param. It captures the dependent types more accurately, less number of template params. Disadvantage is, it relies on the type declaration of the collection which may not be the standard (what if ITER does not have a child type ITER::value_type, or it is named differently ?) . You will use the kewyword typename for the dependent types here. Here the compiler can do better handling of compilation errors, however note that you would hardly get any feedback about type errors unless you actually instantiate it. So you need to test the code with 2/3 concrete types.

The C++ code illustrates both approaches. BTW why are you using typename, I think it should be just "template < class V, ..". typename is used for dependent types (e.g. function accumulate2)

template <class V, class K, class ITER>
K accumulate1(
      std::function<K(K, V)> accumulator,
      ITER it,
      ITER end,
      K initial) {
  K sum = initial;
  for (; it != end; ++it) {
    V item = *it;
    sum = accumulator(sum, item);
  }
  return sum;
}

template <class K, class ITER>
K accumulate2(
      std::function<K(K, typename ITER::value_type)> accumulator,
      ITER it,
      ITER end,
      K initial) {
  K sum = initial;
  for (; it != end; ++it) {
    typename ITER::value_type item = *it;
    sum = accumulator(sum, item);
  }
  return sum;
}

string AppendInt(const string& s, int n) {
  char buffer [65];
  sprintf(buffer, "%s/%d", s.c_str(), n);
  return string(buffer);
}

int main(int argc, char* argv[]) {
  std::function<string(string,int)> fun =
      [](string s, int n) -> string { return AppendInt(s,n); };
  string initial = "x";
  vector<int> array = {13, 24, 50, 64, 32};
  string sum1 = accumulate1(fun, array.begin(), array.end(), initial);
  string sum2 = accumulate2(fun, array.begin(), array.end(), initial);
  printf("accumulate1 : %s\n", sum1.c_str()); // o/p: x/13/24/50/64/32
  printf("accumulate2 : %s\n", sum2.c_str()); // o/p: x/13/24/50/64/32
}

To add few points, this is the general guideline, use as few independent types as possible and use more dependent types / deduced types. In C++ STL compiler does not produce much type error (unlike Java), only during actual call / instantiation compiler will do type checking. For e.g. you can mix the two types K and V, and assign one type to other, and it will not be caught when you instantiate with same type, e.g. — Avik Paul, Dec 16 '15 at 07:17

how do I write a function that can iterate over a generic type in a typesafe way

2 Answers2

Linked