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

8
  • 2
    How would you define "iterable"?
    – Galik
    Nov 17, 2016 at 6:05
  • @Galik I would define it as container that you can iterate through
    – aydow
    Nov 17, 2016 at 6:11
  • Can you provide a real example showing how you would call this function?
    – Galik
    Nov 17, 2016 at 6:14
  • So your iterable is an iterable container, not an iterator?
    – Galik
    Nov 17, 2016 at 6:18
  • Yes. Please excuse me, I'm trying to brush up on my C++ skills
    – aydow
    Nov 17, 2016 at 6:25

4 Answers 4

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.

8
  • 1
    "(almost a pointer)" .. technically it could be a pointer, e.g. char* x = "hello"; join("", x, x+5);
    – txtechhelp
    Nov 17, 2016 at 6:13
  • 1
    also, can you explain why it's a bad implementation?
    – aydow
    Nov 17, 2016 at 6: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. Nov 17, 2016 at 6: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, 2016 at 6:38
  • 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. Nov 17, 2016 at 6:42
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]

1
  • Why suppressing "sep isn't used"? Surely sep would be used.
    – Jon
    Sep 14, 2020 at 23:49
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
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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.