C++: How to pass any iterable type as a function parameter

Question

As an exercise I'm trying to implement Python's str.join method in C++. I will eventually add the function as a method of the std::string class but I figure getting it to work is more of a priority. I've defined the function as follows:

template<typename Iterable>
std::string join(const std::string sep, Iterable iter);

Is there any way that I can ensure that the Iterable type is actually iterable? E.g. I wouldn't want to receive an int or char..

Typal

How would you define "iterable"? – Mahone

@Mahone I would define it as container that you can iterate through – Typal

Can you provide a real example showing how you would call this function? – Mahone

So your iterable is an iterable container, not an iterator? – Mahone

Yes. Please excuse me, I'm trying to brush up on my C++ skills – Typal

This question may be of value: #30244947 – Mahone

@Justin's answer essentially applies, you can write the function assuming you will receive the correct type and if it is not the compiler will complain. The link I posted actually rejects arguments that are not standard style containers at the argument stage. That may enable you to provide a better error message but it's rather more complex. – Mahone

I will eventually add the function as a method of the std::string class .. meaning you plan on replacing std::string with your own, or you are wanting the language constructs of Python in C++ ala "string".join(val)? – Tutty

Answer 1

In C++, rather than having one Iterable, we pass in an iterator (almost a pointer) to the front and the end of the range:

template<typename Iter>
std::string join(const std::string &sep, Iter begin, Iter end);

Note that the sep should be passed as const reference, as you don't need to copy it.

You don't need to worry about whether the Iter is actually an iterator, though. This is because the code will simply fail to compile if it doesn't work.

For example, suppose you implemented it like so (this is a bad implementation):

template<typename Iter>
std::string join(const std::string &sep, Iter begin, Iter end) {
    std::string result;

    while (begin != end) {
        result += *begin;
        ++begin;
        if (begin != end) result += sep;
    }

    return result;
}

Then the type passed in as Iter must have an operator++, an operator!=, and an operator* to work, which is the well understood contract of an iterator.

Oceanography

"(almost a pointer)" .. technically it could be a pointer, e.g. char* x = "hello"; join("", x, x+5); – Tutty

that had occurred to me but pythons syntax is "string".join(list) so i am trying to mimic that. i wan't aware that it conflicts with c++ style – Typal

also, can you explain why it's a bad implementation? – Typal

"rather than having one Iterable, we pass in an iterator" - Well, we don't have to. Stepanov made the stl algorithms quite verbose when he decided to go with this. Andrei Alexandrescu has a talk about the merits of Range based algorithms as opposed to Iterator based. – Emblaze

@Typal It's a bad implementation because it's inefficient. It's not extremely inefficient, so it could work in many cases, but I didn't try to optimize it. For instance, notice how we check begin != end twice in every loop; it might be possible to shuffle code around to improve that. Also, although Python only requires the arguments in the iterator to be strings, it is possible to let the code work for any type which can be converted to a string (perhaps via std::to_string). There are more options; I said it was bad because I was just throwing out example code. – Oceanography

@StoryTeller It's better to follow the standard library's standard as of now. There is a std2 that is being worked on for future c++ standards, in which they try the range based algorithms, but since we aren't using that now, it is better to follow standard idioms. – Oceanography

I disagree (and am not trying to go for an extended discussion). I have great respect for the standard library, but when writing my own new utilities I follow what I consider the superior approach. – Emblaze

@Oceanography would the following code be better? ` while (true) { ret += *begin++; if (begin != end) ret += sep; else break; } ` – Typal

Answer 2

All standard c++ collections has begin() and end() member functions. You could make use of that fact to ensure that the passed argument is actually a collection (in your terminology - iterable) by some SFINAE (c++11 example):

#include <array>
#include <list>
#include <vector>
#include <map>
#include <string>

template <class Iterable>
auto join(const std::string sep, const Iterable& iterable) -> decltype(iterable.begin(), iterable.end(), std::string{}) {
    (void)sep; // to suppress warning that sep isn't used
    // some implementation
    return {};
}

int main() {
    join(";", std::array<int, 5>{});
    join(";", std::list<int>{});
    join(";", std::vector<float>{});
    join(";", std::string{});
    join(";", std::map<int, float>{});
    //join(";", int{}); // does not compile as int is not a collection
}

[live demo]

Ankh

Why suppressing "sep isn't used"? Surely sep would be used. – Madore

Answer 3

You may use template template syntax and - if needed - use SFINAE to make sure that proper class members are existing:

#include <vector>
#include <list>
#include <string>
#include <map>
#include <ostream>

//! Single value containers.
template< template<class> class L, class T,
    class EntryT = typename L<T>::value_type>
std::string my_join(const std::string_view sep, const L<T>& anyTypeIterable)
{
    std::stringstream ss;
    bool first = true;
    for (const EntryT& entry : anyTypeIterable)
    {
        if (first) first = false;
        else ss << sep;
        ss << entry;
    }
    return ss.str();
}

//! std::map specialization - SFINAE used here to filter containers with pair value_type
template< template<class, class> class L, class T0, class T1,
    class EntryT = typename L<T0, T1>::value_type,
    class FirstT = typeof(EntryT::first),
    class SecondT = typeof(EntryT::second)>
std::string my_join(const std::string_view sep, const L<T0, T1>& anyTypeIterable)
{
    std::stringstream ss;
    bool first = true;
    for (const EntryT& entry : anyTypeIterable)
    {
        if (first) first = false;
        else ss << sep;
        ss << entry.first << sep << entry.second;
    }
    return ss.str();
}

int main()
{
    std::cout << my_join("; ", std::vector<int>({1, 2, 3, 4})) << std::endl;
    std::cout << my_join("; ", std::list<int>({1, 2, 3, 4})) << std::endl;
    std::cout << my_join("; ", std::string("1234")) << std::endl;
    std::cout << my_join("; ", std::map<int, int>({ {1, 2}, {3, 4} })) << std::endl;
    return 0;
}

// Output:
// 1; 2; 3; 4
// 1; 2; 3; 4
// 1; 2; 3; 4
// 1; 2; 3; 4

Coimbatore

Answer 4

From https://devblogs.microsoft.com/oldnewthing/20190619-00/?p=102599 :

template<typename C, typename T = typename C::value_type>
auto do_something_with(C const& container)
{
  for (int v : container) { ... }
}

Or if the container doesn't implement value_type:

template<typename C, typename T = std::decay_t<decltype(*begin(std::declval<C>()))>>
auto do_something_with(C const& container)
{
  for (int v : container) { ... }
}

Or if you want only containers containing types convertible to int:

template<typename C, typename T = std::decay_t<decltype(*begin(std::declval<C>()))>,
    typename = std::enable_if_t<std::is_convertible_v<T, int>>>
auto do_something_with(C const& container)
{
  for (int v : container) { ... }
}

But see the comments in that blog post for more refinements.

Madore