This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of C++11 status.

### 676. Moving the unordered containers

Section: 22.5 [unord] Status: C++11 Submitter: Howard Hinnant Opened: 2007-05-05 Last modified: 2016-01-28

Priority: Not Prioritized

View all other issues in [unord].

View all issues with C++11 status.

Discussion:

Move semantics are missing from the `unordered` containers. The proposed resolution below adds move-support consistent with N1858 and the current working draft.

The current proposed resolution simply lists the requirements for each function. These might better be hoisted into the requirements table for unordered associative containers. Futhermore a mild reorganization of the container requirements could well be in order. This defect report is purposefully ignoring these larger issues and just focusing on getting the unordered containers "moved".

[ 2009-07-28 Reopened by Alisdair. No longer solved by concepts. ]

[ 2009-10-17 Removed rvalue-swaps from wording. ]

[ 2009-10 Santa Cruz: ]

> Move to Review. Alisdair will review proposed wording.

[ 2009-10-29 Daniel updates wording. ]

[ 2010-01-26 Alisdair updates wording. ]

[ 2010-02-10 Howard updates wording to reference the unordered container requirements table (modified by 704) as much as possible. ]

[ Voted to WP in Bellevue. ]

[ post Bellevue, Pete notes: ]

> Please remind people who are reviewing issues to check that the text modifications match the current draft. Issue 676, for example, adds two overloads for unordered_map::insert taking a hint. One takes a const_iterator and returns a const_iterator, and the other takes an iterator and returns an iterator. This was correct at the time the issue was written, but was changed in Toronto so there is only one hint overload, taking a const_iterator and returning an iterator.

> This issue is not ready. In addition to the relatively minor signature problem I mentioned earlier, it puts requirements in the wrong places. Instead of duplicating requirements throughout the template specifications, it should put them in the front matter that talks about requirements for unordered containers in general. This presentation problem is editorial, but I'm not willing to do the extensive rewrite that it requires. Please put it back into Open status.

[ 2010-02-11 Moved to Tentatively Ready after 5 positive votes on c++std-lib. ]

[ 2010-02-24 Pete moved to Open: ]

> The descriptions of the semantics of the added `insert` functions belong in the requirements table. That's where the rest of the `insert` functions are.

[ 2010 Pittsburgh: ]

> Move issue 676 to Ready for Pittsburgh. Nico to send Howard an issue for the broader problem.

Rationale:

[ San Francisco: ]

> Solved by N2776.

[ Rationale is obsolete. ]

Proposed resolution:

`unordered_map`

Change 22.5.4 [unord.map]:

>     class unordered_map
>     {
>         ...
>         unordered_map(const unordered_map&);
>         unordered_map(unordered_map&&);
>         unordered_map(const Allocator&);
>         unordered_map(const unordered_map&, const Allocator&);
>         unordered_map(unordered_map&&, const Allocator&);
>         ...
>         unordered_map& operator=(const unordered_map&);
>         unordered_map& operator=(unordered_map&&);
>         ...
>         // modifiers
>         ...
>         std::pair<iterator, bool> insert(const value_type& obj);
>         template <class P> pair<iterator, bool> insert(P&& obj);
>         iterator       insert(const_iterator hint, const value_type& obj);
>         template <class P> iterator       insert(const_iterator hint, P&& obj);
>         ...
>         mapped_type& operator[](const key_type& k);
>         mapped_type& operator[](key_type&& k);
>         ...
>     };

Add to 22.5.4.3 [unord.map.elem]:

>     mapped_type& operator[](const key_type& k);

> > ...

> > Requires: `key_type` shall be `CopyConstructible` and `mapped_type` shall be `DefaultConstructible`.

> > Complexity: Average case `O(1)`, worst case `O(size())`.

>     mapped_type& operator[](key_type&& k);

> > Requires: `key_type` shall be `MoveConstructible` and `mapped_type` shall be `DefaultConstructible`.

> > Effects: If the `unordered_map` does not already contain an element whose key is equivalent to `k` , inserts the value `value_type(std::move(k), mapped_type())`.

> > Returns: A reference to `x.second`, where `x` is the (unique) element whose key is equivalent to `k`.

> > Complexity: Average case `O(1)`, worst case `O(size())`.

Add new section [unord.map.modifiers]:

>     template <class P>
>       pair<iterator, bool> insert(P&& x);

> > Requires: `value_type` is constructible from `std::forward<P>(x)`.

> > Effects: Inserts `x` converted to `value_type` if and only if there is no element in the container with key equivalent to the key of `value_type(x)`.

> > Returns: The `bool` component of the returned `pair` indicates whether the insertion takes place, and the iterator component points to the element with key equivalent to the key of `value_type(x)`.

> > Complexity: Average case `O(1)`, worst case `O(size())`.

> > Remarks: `P` shall be implicitly convertible to `value_type`, else this signature shall not participate in overload resolution.

>     template <class P>
>       iterator insert(const_iterator hint, P&& x);

> > Requires: `value_type` is constructible from `std::forward<P>(x)`.

> > Effects: Inserts `x` converted to `value_type` if and only if there is no element in the container with key equivalent to the key of `value_type(x)`. The iterator `hint` is a hint pointing to where the search should start. Implementations are permitted to ignore the hint.

> > Returns: An iterator pointing to the element with key equivalent to the key of `value_type(x)`.

> > Complexity: Average case `O(1)`, worst case `O(size())`.

> > Remarks: `P` shall be implicitly convertible to `value_type`, else this signature shall not participate in overload resolution.

`unordered_multimap`

Change 22.5.5 [unord.multimap]:

>     class unordered_multimap
>     {
>         ...
>         unordered_multimap(const unordered_multimap&);
>         unordered_multimap(unordered_multimap&&);
>         unordered_multimap(const Allocator&);
>         unordered_multimap(const unordered_multimap&, const Allocator&);
>         unordered_multimap(unordered_multimap&&, const Allocator&);
>         ...
>         unordered_multimap& operator=(const unordered_multimap&);
>         unordered_multimap& operator=(unordered_multimap&&);
>         ...
>         // modifiers
>         ...
>         iterator insert(const value_type& obj);
>         template <class P> iterator insert(P&& obj);
>         iterator       insert(const_iterator hint, const value_type& obj);
>         template <class P> iterator       insert(const_iterator hint, P&& obj);
>         ...
>     };

Add new section [unord.multimap.modifiers]:

>     template <class P>
>       iterator insert(P&& x);

> > Requires: `value_type` is constructible from `std::forward<P>(x)`.

> > Effects: Inserts `x` converted to `value_type`.

> > Returns: An iterator pointing to the element with key equivalent to the key of `value_type(x)`.

> > Complexity: Average case `O(1)`, worst case `O(size())`.

> > Remarks: `P` shall be implicitly convertible to `value_type`, else this signature shall not participate in overload resolution.

>     template <class P>
>       iterator insert(const_iterator hint, P&& x);

> > Requires: `value_type` is constructible from `std::forward<P>(x)`.

> > Effects: Inserts `x` converted to `value_type` if and only if there is no element in the container with key equivalent to the key of `value_type(x)`. The iterator `hint` is a hint pointing to where the search should start. Implementations are permitted to ignore the hint.

> > Returns: An iterator pointing to the element with key equivalent to the key of `value_type(x)`.

> > Complexity: Average case `O(1)`, worst case `O(size())`.

> > Remarks: `P` shall be implicitly convertible to `value_type`, else this signature shall not participate in overload resolution.

`unordered_set`

Change 22.5.6 [unord.set]:

>     class unordered_set
>     {
>         ...
>         unordered_set(const unordered_set&);
>         unordered_set(unordered_set&&);
>         unordered_set(const Allocator&);
>         unordered_set(const unordered_set&, const Allocator&);
>         unordered_set(unordered_set&&, const Allocator&);
>         ...
>         unordered_set& operator=(const unordered_set&);
>         unordered_set& operator=(unordered_set&&);
>         ...
>         // modifiers
>         ...
>         std::pair<iterator, bool> insert(const value_type& obj);
>         pair<iterator, bool> insert(value_type&& obj);
>         iterator       insert(const_iterator hint, const value_type& obj);
>         iterator       insert(const_iterator hint, value_type&& obj);
>         ...
>     };

`unordered_multiset`

Change 22.5.7 [unord.multiset]:

>     class unordered_multiset
>     {
>         ...
>         unordered_multiset(const unordered_multiset&);
>         unordered_multiset(unordered_multiset&&);
>         unordered_multiset(const Allocator&);
>         unordered_multiset(const unordered_multiset&, const Allocator&);
>         unordered_multiset(unordered_multiset&&, const Allocator&);
>         ...
>         unordered_multiset& operator=(const unordered_multiset&);
>         unordered_multiset& operator=(unordered_multiset&&);
>         ...
>         // modifiers
>         ...
>         iterator insert(const value_type& obj);
>         iterator insert(value_type&& obj);
>         iterator       insert(const_iterator hint, const value_type& obj);
>         iterator       insert(const_iterator hint, value_type&& obj);
>         ...
>     };