13

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..

aydow
  • 3,673
  • 2
  • 23
  • 40
  • 2
    How would you define "iterable"? – Galik Nov 17 '16 at 06:05
  • @Galik I would define it as container that you can iterate through – aydow Nov 17 '16 at 06:11
  • Can you provide a real example showing how you would call this function? – Galik Nov 17 '16 at 06:14
  • So your `iterable` is an *iterable container*, not an iterator? – Galik Nov 17 '16 at 06:18
  • Yes. Please excuse me, I'm trying to brush up on my C++ skills – aydow Nov 17 '16 at 06:25
  • This question may be of value: https://stackoverflow.com/questions/30244447/how-to-sfinae-out-non-containers-parameters – Galik Nov 17 '16 at 06:25
  • @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. – Galik Nov 17 '16 at 06:28
  • _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)`? – txtechhelp Nov 17 '16 at 06:47

4 Answers4

15

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.

Justin
  • 24,288
  • 12
  • 92
  • 142
  • 1
    "(almost a pointer)" .. technically it _could_ be a pointer, e.g. `char* x = "hello"; join("", x, x+5);` – txtechhelp Nov 17 '16 at 06:13
  • 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 – aydow Nov 17 '16 at 06:16
  • 1
    also, can you explain why it's a bad implementation? – aydow Nov 17 '16 at 06:33
  • 3
    *"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. – StoryTeller - Unslander Monica Nov 17 '16 at 06:38
  • 1
    @aydow 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. – Justin Nov 17 '16 at 06:38
  • @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. – Justin Nov 17 '16 at 06:40
  • 3
    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. – StoryTeller - Unslander Monica Nov 17 '16 at 06:42
  • 1
    @Justin would the following code be better? ` while (true) { ret += *begin++; if (begin != end) ret += sep; else break; } ` – aydow Nov 25 '16 at 04:21
11

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]

Mike Precup
  • 4,148
  • 21
  • 41
W.F.
  • 13,888
  • 2
  • 34
  • 81
2

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
Michał Jaroń
  • 469
  • 4
  • 11
0

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.

Jon
  • 5,275
  • 5
  • 39
  • 51