Title
insert iterators inefficient for expensive to move types
Status
nad
Section
[insert.iterators]
Submitter
Howard Hinnant

Created on 2009-02-02.00:00:00 last changed 164 months ago

Messages

Date: 2010-10-21.18:28:33

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 [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 [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 [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;
Date: 2010-10-21.18:28:33

[ 2009-10 Santa Cruz: ]

NAD, solved by the removal of concepts.

Date: 2010-10-21.18:28:33

[ 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.

Date: 2010-10-21.18:28:33

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

Date: 2010-10-21.18:28:33

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

Date: 2013-01-25.00:32:44

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);

History
Date User Action Args
2010-10-21 18:28:33adminsetmessages: + msg4653
2010-10-21 18:28:33adminsetmessages: + msg4652
2010-10-21 18:28:33adminsetmessages: + msg4651
2010-10-21 18:28:33adminsetmessages: + msg4650
2010-10-21 18:28:33adminsetmessages: + msg4649
2009-02-02 00:00:00admincreate