generic iterators to access elements of vectors without using Templates c++

Question

I am creating a function which should take as input iterators to vector for example:

vector<int> a;
foo(a.begin(),a.end())

The vector can hold any type.

Now the simple way to do this is using templates

template <typename Iterator>
void foo(Iterator first, Iterator last) {
    for (Iterator it = first; it!=last; ++it) {
        cout << *it;
    }
}

I want to know if there is a way to achieve the same functionality without using templates. Since using Templates would force me to include these functions in Header file of a public API which I don't want to. So I wanted to know is there an alternate way to access the iterators without using Templates.

Answer 1

This is a long answer. The short answer is "type erasure"; go learn about it.

The long answer is two answers. First I cover "do you just want to be able to iterate over contiguous ints?". Then you want span. This is a really simple form of type erasure that forgets what the exact container is you are working on so long as it is contiguous and over T.

The second answer is if you actually need to deal with multiple types (not just int) and multiple kinds of containers (not just contiguous ones).

The two answers are separated by a line.

---

The span concept (see gsl::span) is designed for pretty much this reason. It itself is a template (over the type you are working with), but it will be a concrete instance of a template in most interfaces.

Here is a toy version of it:

template<class T>
struct span_t {
  T* b = 0;
  T* e = 0;
  T* begin() const { return b; }
  T* end() const { return e; }
  span_t(span_t const&)=default;
  span_t& operator=(span_t const&)=default;
  span_t()=default;

  span_t( T* s, T* f ):b(s),e(f) {}
  span_t( T* s, std::size_t l):span_t(s, s+l){}
  template<std::size_t N>
  span_t( T(&arr)[N] ):span_t(arr, N) {}

  std::size_t size() const { return end()-begin(); }
  bool empty() const { return begin()==end(); }
  T& front() const { return *begin(); }
  T& back() const { return *(std::prev(end()); }
  T* data() const { return begin(); }

  span_t without_front( std::size_t N=1 ) const {
    return {std::next( begin(), (std::min)(N, size()) ), end()};
  }
  span_t without_back( std::size_t N=1 ) const {
    return {begin(), std::prev(end(), (std::min)(N, size()) )};
  }
};

we can augment it with conversion operators

namespace details {
  template<template<class...>class Z, class, class...Ts>
  struct can_apply:std::false_type{};
  template<class...>using void_t=void;
  template<template<class...>class Z, class...Ts>
  struct can_apply<Z, void_t<Z<Ts...>>, Ts...>:std::true_type{};
}
template<template<class...>class Z, class...Ts>
using can_apply = details::can_apply<Z,void,Ts...>;

template<class C>
using dot_data_r = decltype( std::declval<C>().data() );
template<class C>
using dot_size_r = decltype( std::declval<C>().size() );

template<class C>
using can_dot_data = can_apply< dot_data_r, C >;
template<class C>
using can_dot_size = can_apply< dot_size_r, C >;

can_dot_data detects via SFINAE if .data() is valid to do on an object of type C.

Now we add a constructor:

template<class T,
  std::enable_if_t<
    can_dot_data<T&>{}
    && can_dot_size<T&>{}
    && !std::is_same<std::decay_t<T>, span_t>{}
    , int
  > =0
>
span_t( T&& t ): span_t( t.data(), t.size() ) {}

which covers std::vector and std::string and std::array.

Your function now looks like:

void foo(span_t<int> s) {
  for (auto&& e:s)
    std::cout << s;
  }
}

with use:

std::vector<int> a;
foo(a);

now, this only works for contiguous containers of a specific type.

---

Suppose this is not what you want. Maybe you do need to solve this for a myriad of types, and you don't want to expose everything in the header.

Then what you need to do is known as type erasure.

You need to work out what minimal set of operations you need from the provided types. Then you need to write wrappers that "type erase" these operations down to "typeless" operations.

This goes in the header, or in another helper header.

In the interface of the function, or in a header intermediate helper, you take the incoming types and do the type erasure, then pass the type-erased types into the "real" implementation.

An example of type erasure is std::function. It takes almost anything that can be invoked with a fixed signature, and turns it into a single type-erased type. Everything except how to copy, destroy and invoke an instance of the type is "forgotten" or erased.

For your case:

template <typename Iterator>
void foo(Iterator first, Iterator last) {
  for (Iterator it = first; it!=last; ++it) {
    cout << *it;
  }
}

I see two things that need to be erased down to; iteration, and printing.

struct printable_view_t {
  void const* data = 0;
  void(*print_f)(std::ostream& os, void const*) = 0;

  explicit operator bool()const{return data;}
  printable_view_t() = default;
  printable_view_t(printable_view_t const&) = default;

  template<class T,
    std::enable_if_t<!std::is_same<T, printable_view_t>{}, int> =0
  >
  printable_view_t( T const& t ):
    data( std::addressof(t) ),
    print_f([](std::ostream& os, void const* pv){
      auto* pt = static_cast<T const*>(pv);
      os << *pt;
    })
  {}
  std::ostream& operator()(std::ostream& os)const {
    print_f(os, data);
    return os;
  }
  friend std::ostream& operator<<(std::ostream& os, printable_view_t p) {
    return p(os);
  }
};

printable_view_t is an example of type-erasing "I can be printed".

void bar( printable_view_t p ) {
  std::cout << p;
}

void test_bar() {
  bar(7);
  bar(3.14);
  bar(std::string("hello world"));
}

The next thing we'd have to do is type erase iteration. This is harder, because we want to type erase iteration over iterating over a printable_view_t type.

Type erasing foreach is a tad easier, and often more efficient.

template<class View>
struct foreach_view_t {
  void* data = 0;
  void(*func)( std::function<void(View)>, void* ) = 0;

  explicit operator bool()const{return data;}
  foreach_view_t() = default;
  foreach_view_t(foreach_view_t const&) = default;

  template<class T,
    std::enable_if_t<!std::is_same<std::decay_t<T>, foreach_view_t>{}, int> =0
  >
  foreach_view_t( T&& t ):
    data( const_cast<std::decay_t<T>*>(std::addressof(t)) ),
    func([](std::function<void(View)> f, void* pv){
      auto* pt = static_cast<std::remove_reference_t<T>*>(pv);
      for (auto&& e : *pt)
        f(decltype(e)(e));
    })
  {}
  void operator()(std::function<void(View)> f)const{
    func(f, data);
  }
};

we then daisy chain these together

void foo(foreach_view_t<printable_view_t> x) {
  x([](auto p){ std::cout << p; });
}

test code:

std::vector<int> a{1,2,3};

foo(a);

Now much of the header code was "hoisted" into the type erasure types instead of a function template body. But careful choice of the points of type erasure can let you keep what you need from the types precise and narrow, and the logic of how you use those operations private.

As an example, the above code doesn't care where you are printing it to; std::cout was not part of the type erasure.

Live example.