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

### 977. insert iterators inefficient for expensive to move types

Section: 25.5.2 [insert.iterators] Status: NAD Submitter: Howard Hinnant Opened: 2009-02-02 Last modified: 2016-01-28

Priority: Not Prioritized

View all other issues in [insert.iterators].

View all issues with NAD status.

Discussion:

The new concepts for the insert iterators mandate an extra copy when inserting an lvalue:

>     requires CopyConstructible<Cont::value_type>
>       back_insert_iterator<Cont>&
>       operator=(const Cont::value_type& value);

> > -1- Effects: `push_back(*container, Cont::value_type(value));`

The reason is to convert `value` into an rvalue because the current `BackInsertionContainer` concept only handles `push_back`-ing rvalues:

>     concept BackInsertionContainer<typename C> : Container<C> {
>       void push_back(C&, value_type&&);
>     }

Without the conversion of `value` to an rvalue, the assignment operator fails to concept check.

A solution is to modify the `BackInsertionContainer` concept so that the client can pass in the parameter type for `push_back` similar to what is already done for the `OutputIterator` concept:

>     concept BackInsertionContainer<typename C, typename Value = C::value_type&&>
>       : Container<C> {
>          void push_back(C&, Value);
>     }

This allows the assignment operator to be adjusted appropriately:

>     requires BackInsertionContainer<Cont, Cont::value_type const&> &&
>              CopyConstructible<Cont::value_type>
>       back_insert_iterator<Cont>&
>       operator=(const Cont::value_type& value);

> > -1- Effects: `push_back(*container, value);`

[ We may want to propagate this fix to other concepts such as `StackLikeContainer`. ]

[ Solution and wording collaborated on by Doug and Howard. ]

[ Batavia (2009-05): ]

> Howard notes that "these operations behaved efficiently until concepts were added."

> Alisdair is uncertain that the proposed resolution is syntactically correct.

> Move to Open, and recommend the issue be deferred until after the next Committee Draft is issued.

[ 2009-10 Santa Cruz: ]

> NAD, solved by the removal of concepts.

Proposed resolution:

Change [container.concepts.free]:

>     concept FrontInsertionContainer<typename C, typename Value = C::value_type&&>
>         : Container<C> {
>       void push_front(C&, value_type&& Value);

>       axiom FrontInsertion(C c, value_type Value x) {
>         x == (push_front(c, x), front(c));
>       }
>     }

> ...

>     concept BackInsertionContainer<typename C, typename Value = C::value_type&&>
>         : Container<C> {
>       void push_back(C&, value_type&& Value);
>     }

> ...

>     concept InsertionContainer<typename C, typename Value = C::value_type&&>
>         : Container<C> {
>       iterator insert(C&, const_iterator, value_type&& Value);

>       axiom Insertion(C c, const_iterator position, value_type Value v) {
>         v == *insert(c, position, v);
>       }
>     }

Change [container.concepts.member]:

>     auto concept MemberFrontInsertionContainer<typename C, typename Value = C::value_type&&>
>         : MemberContainer<C> {
>       void C::push_front(value_type&& Value);

>       axiom MemberFrontInsertion(C c, value_type Value x) {
>         x == (c.push_front(x), c.front());
>       }
>     }

> ...

>     auto concept MemberBackInsertionContainer<typename C, typename Value = C::value_type&&>
>         : MemberContainer<C> {
>       void C::push_back(value_type&& Value);
>     }

> ...

>     auto concept MemberInsertionContainer<typename C, typename Value = C::value_type&&>
>         : MemberContainer<C> {
>       iterator C::insert(const_iterator, value_type&& Value);

>       axiom MemberInsertion(C c, const_iterator position, value_type Value v) {
>         v == *c.insert(position, v);
>       }
>     }

Change [container.concepts.maps]:

>     template <MemberFrontInsertionContainer C, typename Value = C::value_type&&>
>     concept_map FrontInsertionContainer<C, Value> {
>       typedef Container<C>::value_type value_type;

>       void push_front(C& c, value_type&& Value v) { c.push_front(static_cast<value_type&& Value>(v)); }
>     }

> ...

>     template <MemberBackInsertionContainer C, typename Value = C::value_type&&>
>     concept_map BackInsertionContainer<C, Value> {
>       typedef Container<C>::value_type value_type;

>       void push_back(C& c, value_type&& Value v) { c.push_back(static_cast<value_type&& Value>(v)); }
>     }

> ...

>     template <MemberInsertionContainer C, typename Value = C::value_type&&>
>     concept_map InsertionContainer<C, Value> {
>       typedef Container<C>::value_type value_type;
>       Container<C>::iterator insert(C& c, Container<C>::const_iterator i, value_type&& Value v)
>       { return c.insert(i, static_cast<value_type&& Value>(v)); }
>     }

Change 25.5.2.2 [back.insert.iterator]:

>     template <BackInsertionContainer Cont>
>     class back_insert_iterator {
>       ...
>       requires BackInsertionContainer<Cont, const Cont::value_type&>
>                CopyConstructible<Cont::value_type>
>         back_insert_iterator<Cont>&
>           operator=(const Cont::value_type& value);
>       ...

Change [back.insert.iter.op=]:

>     requires BackInsertionContainer<Cont, const Cont::value_type&>
>              CopyConstructible<Cont::value_type>
>       back_insert_iterator<Cont>&
>         operator=(const Cont::value_type& value);

> > -1- Effects: `push_back(*container, Cont::value_type(value));`

Change 25.5.2.3 [front.insert.iterator]:

>     template <FrontInsertionContainer Cont>
>     class front_insert_iterator {
>       ...
>       requires FrontInsertionContainer<Cont, const Cont::value_type&>
>                CopyConstructible<Cont::value_type>
>         front_insert_iterator<Cont>&
>           operator=(const Cont::value_type& value);
>       ...

Change [front.insert.iter.op=]:

>     requires FrontInsertionContainer<Cont, const Cont::value_type&>
>              CopyConstructible<Cont::value_type>
>       front_insert_iterator<Cont>&
>         operator=(const Cont::value_type& value);

> > -1- Effects: `push_front(*container, Cont::value_type(value));`

Change 25.5.2.4 [insert.iterator]:

>     template <InsertionContainer Cont>
>     class insert_iterator {
>       ...
>       requires InsertionContainer<Cont, const Cont::value_type&>
>                CopyConstructible<Cont::value_type>
>         insert_iterator<Cont>&
>           operator=(const Cont::value_type& value);
>       ...

Change [insert.iter.op=]:

>     requires InsertionContainer<Cont, const Cont::value_type&>
>              CopyConstructible<Cont::value_type>
>       insert_iterator<Cont>&
>         operator=(const Cont::value_type& value);

> > -1- Effects:

> > >     iter = insert(*container, iter, Cont::value_type(value));
> > >     ++iter;