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;