std:: insert iterator for unordered sets (or maps)?

Question

Is there an insert iterator in std:: for unordered sets? As far as I can see, std::inserter requires an iterator argument. This is unsafe for unordered containers (at least for boost::unordered_set), because they may reallocate during an insert operation and render the passed .begin() iterator invalid.

So currently I have to pass my own iterator which essentially is an boost::function_output_iterator with a functor that simply calls unorderedSet.insert(param1).

Why is it that std::inserter even requires the hint iterator argument anyway?

Answer 1

There isn't. The reason that the hint argument is required is that std::inserter is meant for containers where position is required in the context of insertion. As you know, this is not the case for unordered containers.

vector in an example of a container where knowing position is a requirement for insertion. From cppreference:

(1)
iterator insert( iterator pos, const T& value ); // (until C++11)
iterator insert( const_iterator pos, const T& value ); // (since C++11)

---

 (2)
iterator insert( const_iterator pos, T&& value ); // (since C++11)

---

(3)     
void insert( iterator pos, size_type count, const T& value ); // (until C++11)
iterator insert( const_iterator pos, size_type count, const T& value ); // (since C++11)

---

(4)     
template< class InputIt >
void insert( iterator pos, InputIt first, InputIt last); // (until C++11)
template< class InputIt >
iterator insert( const_iterator pos, InputIt first, InputIt last ); // (since C++11)

---

(5)
iterator insert( const_iterator pos, std::initializer_list<T> ilist ); // (since C++11)

Inserts elements at the specified location in the container.

  1-2) inserts value before pos
  3) inserts count copies of the value before pos
  4) inserts elements from range [first, last) before pos.
       This overload has the same effect as overload (3) if InputIt is an integral type. ^{(until C++11)}
       This overload only participates in overload resolution if InputIt qualifies as LegacyInputIterator, to avoid ambiguity with the overload (3). ^{(since C++11)} The behavior is undefined if first and last are iterators into *this.
  5) inserts elements from initializer list ilist before pos.

---

I know this isn't the answer you're looking for, but rolling out your own is easy enough, if not a bit verbose:

template<typename Container>
class unordered_inserter {
public:
    using iterator_category = std::output_iterator_tag;
    using value_type = void;
    using reference_type = void;
    using difference_type = void;
    using pointer = void;
    using reference = void;
    using container_type = Container;

    unordered_inserter& operator++() {return *this;} //no-op
    unordered_inserter& operator++(int) {return *this;} //no-op
    unordered_inserter& operator*() {return *this;} //no-op
    constexpr unordered_inserter& operator=(const typename Container::value_type& value) {
        container->insert(value);
        return *this;
    }
    constexpr unordered_inserter& operator=(typename Container::value_type&& value) {
        container->insert(std::move(value));
        return *this;
    }
    unordered_inserter(Container* container)
        :    container(container)
    {}
protected:
    Container* container;
};

This probably can be refactored to support other kinds of insertion, but I think this is enough for now.

Here's me playing a bit with it:

int main() {
    std::unordered_map<int, int> m;
    std::istringstream iss("1 2 3 4 5 6");

    std::transform(std::istream_iterator<int>(iss), std::istream_iterator<int>(), unordered_inserter(&m), [](int v) {
        return decltype(m)::value_type{v, v*v};
    });
    std::transform(m.begin(), m.end(), std::ostream_iterator<std::string>(std::cout, "\n"), [](auto pair) {
        return std::to_string(pair.first) + "," + std::to_string(pair.second);
    });
}

Live on Godbolt

---

A thing to note here is that your assertion that passing this hint argument to unordered containers is unsafe is wrong. When operator= is called, and a new element is inserted into the container, the iter member is updated to whatever insert returns. Since this value is required to be valid, there's no way that iter can ever be invalidated.