wake-up-neo.com

Was ist der Vorteil von std :: back_inserter gegenüber std :: inserter?

Soweit ich feststellen kann, dass std::back_inserter überall in einem STL-Algorithmus funktioniert, können Sie stattdessen einen std::inserter übergeben, der mit .end() erstellt wurde:

std::copy(l.begin(), l.end(), std::back_inserter(dest_list));
std::copy(l.begin(), l.end(), std::inserter(dest_list, dest_list.end()));

UND, im Gegensatz zu back_inserter, funktioniert inserter für jeden STL-Container !! Ich habe es erfolgreich für std::vector, std::list, std::map, std::unordered_map ausprobiert, bevor ich überrascht kam.

Ich dachte, das liegt vielleicht daran, dass Push_back für einige Strukturen schneller sein könnte als insert(.end()), aber ich bin mir nicht sicher ...

Das scheint für std::list nicht der Fall zu sein (macht Sinn):

// Copying 10,000,000 element-list with std::copy. Did it twice w/ switched order just in case that matters.
Profiling complete (884.666 millis total run-time): inserter(.end())
Profiling complete (643.798 millis total run-time): back_inserter
Profiling complete (644.060 millis total run-time): back_inserter
Profiling complete (623.151 millis total run-time): inserter(.end())

Aber es tut etwas für std::vector, obwohl ich nicht wirklich weiß, warum ?:

// Copying 10,000,000 element-vector with std::copy.
Profiling complete (985.754 millis total run-time): inserter(.end())
Profiling complete (746.819 millis total run-time): back_inserter
Profiling complete (745.476 millis total run-time): back_inserter
Profiling complete (739.774 millis total run-time): inserter(.end())

Ich denke, in einem Vektor gibt es etwas mehr Aufwand, um herauszufinden, wo sich der Iterator befindet, und dann ein Element dorthin zu setzen, und zwar nur arr [count ++]. Vielleicht ist es das?

Aber ist das der Hauptgrund?

Meine Folgefrage, denke ich, lautet: "Ist es in Ordnung, std::inserter(container, container.end()) für eine mit Templaten versehene Funktion zu schreiben und zu erwarten, dass sie für (fast) jeden STL-Container funktioniert?"

Ich habe die Zahlen nach dem Wechsel zu einem Standard-Compiler aktualisiert. Hier sind die Details meines Compilers:
gcc-Version 4.8.2 (Ubuntu 4.8.2-19ubuntu1) 
Ziel: x86_64-linux-gnu

Mein Build-Befehl:

g++ -O0 -std=c++11 algo_test.cc

Ich denke diese Frage stellt die zweite Hälfte meiner Frage , nämlich: "Kann ich eine vorgefertigte Funktion schreiben, die std::inserter(container, container.end()) verwendet und davon ausgeht, dass sie für fast jeden Container funktioniert?"

Die Antwort war "Ja, für jeden Container außer std::forward_list". Aufgrund der Diskussion in den Kommentaren unten und in der Antwort von user2746253 klingt es jedoch so, als sollte ich mir bewusst sein, dass dies für std::vector langsamer wäre als die Verwendung von std::back_inserter...

Daher möchte ich vielleicht meine Vorlage auf Container spezialisieren, die stattdessen RandomAccessIterators verwenden, um stattdessen back_inserter zu verwenden. Ist das sinnvoll? Vielen Dank.

c++vectorstliteratorcontainers
42
NHDaly

Iterator-Typen

  • std::back_inserter gibt std::back_insert_iterator zurück, der Container::Push_back() verwendet.
  • std::inserter gibt std::insert_iterator zurück, der Container::insert() verwendet.

std :: list

Für Listen ist std::list::Push_back fast dasselbe wie std::list::insert. Der einzige Unterschied besteht darin, dass insert den Iterator an das eingefügte Element zurückgibt.

bits/stl_list.h

void Push_back(const value_type& __x)
  { this->_M_insert(end(), __x); }
void _M_insert(iterator __position, const value_type& __x)
  {
    _Node* __tmp = _M_create_node(__x);
    __tmp->_M_hook(__position._M_node);
  }

bits/list.tcc

template<typename _Tp, typename _Alloc> typename list<_Tp, _Alloc>::iterator
list<_Tp, _Alloc>::insert(iterator __position, const value_type& __x)
  {
  _Node* __tmp = _M_create_node(__x);
  __tmp->_M_hook(__position._M_node);
  return iterator(__tmp);
  }

std :: vector

Bei std::vector sieht es etwas anders aus. Push-Back prüft, ob eine Neuzuordnung erforderlich ist und ob der Wert nicht nur an der richtigen Stelle platziert wird.

bits/stl_vector.h

void Push_back(const value_type& __x)
  {
  if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
    {
    _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x);
    ++this->_M_impl._M_finish;
    }
  else
    _M_insert_aux(end(), __x);
  }

Aber in std::vector::insert gibt es noch 3 weitere Dinge, die sich auf die Leistung auswirken. _. Bits/vector.tcc

template<typename _Tp, typename _Alloc> typename vector<_Tp, _Alloc>::iterator
vector<_Tp, _Alloc>::insert(iterator __position, const value_type& __x)
  {
  const size_type __n = __position - begin(); //(1)
  if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
  && __position == end()) //(2)
    {
    _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x);
    ++this->_M_impl._M_finish;
    }
  else
    {
    _M_insert_aux(__position, __x);
    }
  return iterator(this->_M_impl._M_start + __n); //(3)
  }
49
user2746253

Kurze Antwort ist, dass Sie mit std::insert_iterator an einer beliebigen Position im Container einfügen können:

//insert at index 2
auto it = std::inserter(v, v.begin() + 2);
*it = 4;

Um dies zu erreichen, muss std :: vector vorhandene Elemente nach Index 2 im obigen Beispiel um eine Stelle nach unten verschieben. Dies ist eine O(n)-Operation, es sei denn, Sie fügen am Ende ein, da nichts anderes nach unten verschoben werden kann. Aber es muss immer noch relevante Prüfungen durchgeführt werden, die O(1) perf Strafe verursachen. Für verknüpfte Listen können Sie an beliebiger Stelle in der O(1)-Zeit einfügen, so dass keine Strafe entsteht. Der back_inserter fügt am Ende immer ein, also auch keine Strafe.

0
Shital Shah