6
\$\begingroup\$

(Here is a link to this same code on Wandbox)

C++17 introduces member functions extract and insert on node-based containers (such as set and map) so that single elements can be transferred from container A to container B without any move operations. It also adds member function merge to transfer all contents of container A into container B. But there's no "range merge" function provided by the STL as far as I can tell. So, inspired by this question, I decided to write an iterator adaptor similar to std::move_iterator but which can be used to extract and insert instead of moving. Here's my usage example:

// snipped the definitions of classes K and V, but see the Wandbox if you care

int main()
{
    using KV = std::pair<K,V>;
    std::map<K,V> m1({
        KV{ "k1", "v1" },
        KV{ "k2", "v2" },
        KV{ "k3", "v3" },
    });
    std::map<K,V> m2;

    puts("Moving elements from m1 to m2...");
#if 0
    // the old boring way
    for (auto it = m1.begin(); it != m1.end(); ) {
        m2.insert( m1.extract(it++) );
    }
#else
    // the shiny new way
    auto begin = my::extract_iterator(m1, m1.begin());
    auto end = my::extract_iterator(m1, m1.end());
    auto out = my::insert_iterator(m2);
    std::copy(begin, end, out);
#endif
    puts("...done!");

    std::cout << "Contents of m1:" << std::endl;
    for (auto&& [k, v]: m1) {
        std::cout << k << ' ' << v << std::endl;
    }

    std::cout << "Contents of m2:" << std::endl;
    for (auto&& [k, v]: m2) {
        std::cout << k << ' ' << v << std::endl;
    }
}

And here's the implementation:

#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>

namespace my
{
    template<typename Container>
    class insert_iterator
    {
        Container *container;

    public:
        using iterator_category = std::output_iterator_tag;
        using difference_type = void;
        using value_type = void;
        using pointer = void;
        using reference = void;

        insert_iterator(Container& c) : container(&c) {}

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

        template<class N>
        insert_iterator& operator=(N&& nh)
        {
            container->insert(std::forward<N>(nh));
            return *this;
        }
    };

    template<typename Container, typename Iterator>
    class extract_iterator
    {
        Container *container;
        Iterator iterator;
        bool secretly_advanced = false;

    public:
        using iterator_category = std::input_iterator_tag;
        using difference_type = void;
        using value_type = void;
        using pointer = void;
        using reference = void;

        extract_iterator(Container& c, Iterator it) : container(&c), iterator(std::move(it)) {}

        auto operator*() {
            assert(!secretly_advanced);
            secretly_advanced = true;
            return container->extract(iterator++);
        }
        extract_iterator& operator++() {
            if (!secretly_advanced) ++iterator; 
            secretly_advanced = false;
            return *this;
        }
        extract_iterator operator++(int) {
            auto copy = *this;
            if (!secretly_advanced) ++iterator; 
            secretly_advanced = false;
            return copy;
        }
        bool operator==(const extract_iterator& o) const {
            return secretly_advanced == o.secretly_advanced && iterator == o.iterator;
        }
        bool operator!=(const extract_iterator& o) const { return !(*this == o); }
    };
} // namespace my

Notice that I'm using the default rules for class template parameter type deduction.

Notice that my input iterator (extract_iterator) sets its value_type to void. I'm not 100% sure that's kosher.

The secretly_advanced stuff is unfortunately necessary because libstdc++ implements its std::copy as something like

while (first != last) {
    *d_first++ = *first;
    ++first;
}

instead of

while (first != last) {
    *d_first++ = *first++;
}

and evaluating *first in my case invalidates first.iterator, so I figured the best thing to do was to advance it inside operator* itself and just keep track of whether it'd already been secretly advanced or not.

If I missed out on a chance to use some exciting new C++17ism, please tell me!

\$\endgroup\$
  • \$\begingroup\$ Can you provide a K and V so that we can compile this? Your link doesn't include any code (unless it's hidden in a script somewhere, but it would still be better in the question, for permanence). \$\endgroup\$ – Toby Speight Feb 21 '17 at 10:04
  • \$\begingroup\$ @TobySpeight, definitions of K and V are right before main. I think that definitions are not that necessary, since it is more or less obvious what they are doing. \$\endgroup\$ – Incomputable Feb 21 '17 at 10:24
  • \$\begingroup\$ What do you mean, "right before main"? - all I see is "Here's my usage example: // snipped the definitions of classes K and V, but see the Wandbox if you care int main()". No definition. \$\endgroup\$ – Toby Speight Feb 21 '17 at 10:31
  • \$\begingroup\$ Can I just using K = std::string? and the same for V? \$\endgroup\$ – Toby Speight Feb 21 '17 at 10:31
  • 1
    \$\begingroup\$ The test case on Wandbox uses a particular K and V with instrumented constructors and assignment operators, in order to "prove" that no move-constructions or assignments take place during the std::copy. But yeah, @TobySpeight, my intention is definitely that you ought to be able to use these iterators with any K and V of your choosing. \$\endgroup\$ – Quuxplusone Feb 22 '17 at 4:26
1
\$\begingroup\$

It seems that GCC's implementation of C++17 isn't complete enough to compile your code (at least at 6.3.0), but I can offer a few comments:

Headers

Your includes don't match your uses. I found I needed

#include <cassert>
#include <iterator>
#include <utility>

(some of the others are needed by your main(), but shouldn't belong in your header file).

Pointer to container object

You accept a container as a reference, but then store its address. It might be clearer to use a reference, as it cannot be null:

    Container &container;

However, if you do this, then an iterator into a given container can't be assigned from an iterator to a different container. In other words, operator=() would be constrained to work only when both iterators reference the same container, which might be too restrictive, and certainly surprising compared with the Standard Library iterators.

C asserts

I'm not convinced that this assert is good:

        assert(!secretly_advanced);

Asserts are good for testing invariants, but this looks like it's checking that client code has used it in the prescribed manner. If you're to check this at all, it might be better to raise an exception. On the other hand, since you aren't checking that the user doesn't dereference the end() iterator, perhaps it's more appropriate to behave like the standard library, and not impose checking.

\$\endgroup\$
  • \$\begingroup\$ I think if I store a reference, my iterator is no longer assignable. I also think I get iterator_traits for free, given that I'm providing all the appropriate member typedefs (AFAIK). ...Or, in what way were you thinking it'd help to specialize iterator_traits? (Your other points are well taken.) \$\endgroup\$ – Quuxplusone Feb 22 '17 at 9:52
  • 1
    \$\begingroup\$ I think you're right on both counts - I've amended my answer. \$\endgroup\$ – Toby Speight Feb 22 '17 at 9:55
  • \$\begingroup\$ Also, I found the use of insert_operator as its own proxy object to be a bit strange - but I couldn't pin down exactly what made me uncomfortable about it. I guess it's just not a pattern I'd seen before. \$\endgroup\$ – Toby Speight Feb 22 '17 at 10:00
0
\$\begingroup\$

Thanks to discussion at the San Francisco C++ meetup, here is a definite flaw in my original code:

    template<class N>
    insert_iterator& operator=(N&& nh)
    {
        container->insert(std::forward<N>(nh));
        return *this;
    }

A guideline was proposed: "Unconstrained forwarding references are always a bad idea." I don't yet 100% agree with that guideline, but I definitely agree when forwarding references are used in ways that might be mistaken for special member functions. The above code breaks usages like the following:

auto out1 = my::insert_iterator(m2);
auto out2 = my::insert_iterator(m2);
out1 = out2;

The above fails because out1 = out2 tries to find a match for insert_iterator::operator=(insert_iterator&). This would be an okay match for the implicitly defaulted copy-assignment operator insert_iterator::operator=(const insert_iterator&), but unfortunately it's a perfect match for the specialization insert_operator::operator=(N&&) [with N=insert_iterator&]. So we end up trying to call the equivalent of

container->insert(out2);

and we get a compiler error.

In some cases the appropriate fix would be to constrain the template with std::enable_if_t<!std::is_same_v<std::decay_t<N>, insert_iterator>>; but in this case the appropriate fix is just to Be Less Clever.

    insert_iterator& operator=(typename Container::node_type&& nh)
    {
        container->insert(std::move(nh));
        return *this;
    }

I'm also now vaguely worried about exception-safety.

The good news is that node handles are fundamentally memory-leak-proof; if you destroy a node handle without inserting it anywhere, then the destructor frees the node (and its contents) for you.

The worrisome news is that Container::insert can definitely throw (most obviously, if T::operator< resp. std::hash<T>::operator() throws), and it wouldn't surprise me if Container::extract could throw too. Do we need to do anything special to deal with exceptions here? I think the answer is "no, we get the basic exception guarantee that nothing will go horribly wrong as long as you don't try to use those iterators again," but I haven't formally explored it.

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