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 RandomAccessIterator
s verwenden, um stattdessen back_inserter
zu verwenden. Ist das sinnvoll? Vielen Dank.
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.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);
}
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)
}
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.