676. Moving the unordered containers

Section: 23.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 23.5.3 [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 23.5.3.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 23.5.4 [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 23.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 23.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);
    ...
};