4
\$\begingroup\$

Recently I wrote a back_inserter with the same interface as the std::back_inserter just for supporting several containers in the constructor and doing push_back for each. The solution needs C++17. Please give me some feedback! Thanks.

#include <iterator>
#include <tuple>

namespace stx {

template <class Container, class... Containers>
class back_insert_iterator
{
public:
    using value_type        = void;
    using difference_type   = void;
    using pointer           = void;
    using reference         = void;
    using iterator_category = std::output_iterator_tag;

    explicit back_insert_iterator(Container& container, Containers&... containers) : containers(container, containers...) {
    }

    back_insert_iterator& operator=(const typename Container::value_type& value) {
        std::apply([&](auto&... container) { ((container.push_back(value)), ...); }, containers);
        return *this;
    }

    back_insert_iterator& operator=(typename Container::value_type&& value) {
        std::apply([&](auto&... container) { ((container.push_back(std::move(value))), ...); }, containers);
        return *this;
    }

    back_insert_iterator& operator*() {
        return *this;
    }

    back_insert_iterator& operator++() {
        return *this;
    }

    back_insert_iterator& operator++(int) {
        return *this;
    }

private:
    std::tuple<Container&, Containers&...> containers;
};

template <class Container, class... Containers>
auto back_inserter(Container& container, Containers&... containers) {
    return back_insert_iterator<Container, Containers...>(container, containers...);
}

}

And you can use it like this:

#include <iostream>
#include <vector>

auto main() -> int {

    const auto numbers = std::vector<int>{ 1, 2, 3, 4, 5 };

    std::vector<int> copy1, copy2;

    std::copy(numbers.begin(), numbers.end(), stx::back_inserter(copy1, copy2));

    std::cout << "(numbers == copy1) = " << std::boolalpha << (numbers == copy1) << '\n';
    std::cout << "(numbers == copy2) = " << std::boolalpha << (numbers == copy2) << '\n';

};

A front_inserter would of course look similar, just calling push_front instead. Some specific additional questions:

  • does the operator= method with the r-value work as intended or do I need to pass the value differently to the lambda?
  • do I need an extra static_assert to check that each Container supports the same value_type or at least some that are convertible to avoid overloading the user with template errors in case they are different?
  • is there another solution where I could let the user provide and optional argument for execution policy, for example std::execution::par
  • the original std::back_inserter saves the container as pointer - is there any advantage versus my inserter which saves them per reference?
\$\endgroup\$
  • 2
    \$\begingroup\$ > (container.push_back(std::move(value))), ...): moving value's content several times is a bad idea. After the first move, value's state is valid but unspecified. It doesn't make a difference in you test because moving an int is equivalent to copying it, since ints as all built-in types don't have move semantics. But try it with std::strings, for instance, and you'll see a difference \$\endgroup\$ – papagaga Oct 26 '18 at 8:37
6
\$\begingroup\$

The general structure seems fine to me. However, some things can still be improved!

Iterator requirements

Iterators are required to satisfy the Swappable and CopyAssignable named requirements, but the current implementation doesn't. (This is also why the std::back_inserter implementation you looked at used pointers instead of references, the latter cannot be reseated.)

And from a design perspective, this provides an interesting dilemma: Do you want to support assignment from different underlying container types? For example, like this:

std::deque<int> copy1{};
std::list<int> copy2{};

auto out = stx::back_inserter(copy1, copy2);
// out is of type stx::back_inserter_iterator<std::deque<int>, std::list<int>>

std::vector<int> copy3{};

out = stx::back_inserter(copy2, copy3, copy1);
// assignment from stx::back_inserter_iterator<std::list<int>, std::vector<int>, std::deque<int>>

If no, the solution is easy: Change the container references to pointers (to make assignment possible), add assignment operator overloads, and either use std::swaps default implementation or write your own swap function for stx::back_inserter_iterator.

This is the easy way, but in reality likely not very useful, since assignment only allows for the exact same container types.

If yes, the solution becomes more complicated, as the actual container types need to be abstracted away. One idea for this is using inheritance in an external storage class (rough idea):

template<typename ValueType>
class container_storage_base {
public:
    virtual ~container_storage_base() {}
    virtual void push_back(const ValueType&) = 0;
    virtual void push_back(ValueType&&) = 0;
};

template<typename Container, typename... Containers>
class container_storage : container_storage_base<typename Container::value_type> {
    std::tuple<Container&, Containers&...> containers; // can use references here

public:
    void push_back(const typename Container::value_type& value) override { ... }
    void push_back(typename Container::value_type&& value) override { ... }
};

Inside of stx::back_inserter_iterator, you could then simply store a std::shared_ptr<container_storage_base<ValueType>>, thus freely allowing assignment between different stx::back_inserter_iterator<ValueType> instances (as long as ValueType remains the same).

Why std::shared_ptr?

We need some indirection in order to allow for virtual dispatch to work, and using a pointer seems to be the easiest solution for that. However, we also need to release the container_storage object once we no longer need it, and for that, smart pointer come in very handy.

But: Iterators need to be copyable, and that isn't something supported by std::unique_ptr (only allowing for a unique owner), thus std::shared_ptr was chosen.

Other Nitpicks

  • Most functions could be marked noexcept (even if only conditionally).

Q & A

  • does the operator= method with the r-value work as intended or do I need to pass the value differently to the lambda?

    Works as intended.

    Well, mostly. With the expansion, value will be moved from for every container, i.e. every container but the first will move from an already moved-from value. To get the initial value to all containers, copies will need to be made.

  • do I need an extra static_assert to check that each Container supports the same value_type or at least some that are convertible to avoid overloading the user with template errors in case they are different?

    Do you need to? Not necessarily.

    Would it be nice for users of the implementation? Absolutely!

  • is there another solution where I could let the user provide and optional argument for execution policy, for example std::execution::par

    I'm confused: Execution policies are for algorithms, not iterators themselves.

    Of course, you can always add a data member to store a value if you want to, but I fail to see how storing an execution policy would be helpful here, as there aren't any calls to algorithms internally (and just adding an execution policy to data doesn't accomplish anything).

  • the original std::back_inserter saves the container as pointer - is there any advantage versus my inserter which saves them per reference?

    See above, you cannot reassign references.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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