std::vector<std::unique_ptr<>>::insert

[Fytch]

Hallo,

wie füge ich m nullptr s in einen std::vector<std::unique_ptr<>> mit n Elementen mit O(m+n) Laufzeit ein? Folgendes ist leider O(m*n):

std::fill_n( std::inserter( vec, vec.begin() + 123 ), m, nullptr );

Und ferner: wieso gibt es std::insert_iterator aber keinen std::emplace_iterator ?

LG

PS: ...ohne Speicheroverhead; einen zweiten Vektor erstellen und dann 'rübermoven ist keine Lösung.

[SeppJ]

Direkt vector::insert aufrufen, das ist von der Laufzeit her O(m+n), wobei m die Anzahl der neuen Elemente und n die Anzahl der Elemente hinter der Einfügeposition ist. Die fill_n/inserter-Kombination ist zu allgemein, um die speziellen Eigenarten eines Vectors auszunutzen. Faustregel: Wenn ein Container eine spezielle Methode für etwas anbietet, sollte diese bevorzugt werden gegenüber den allgemeinen Algorithmen. Anderes gutes Beispiel dafür: std::sort vs list::sort.

[Fytch]

SeppJ schrieb:

Direkt vector::insert aufrufen

Wie meinst du das? Folgendes ist gleich schlecht, auch O(m*n):

while( m-- )
    vec.insert( vec.begin() + 123, nullptr );

EDIT: Ah, du meintest wahrscheinlich dasjenige vector::insert , das eine Size nimmt. Geht hier nicht, da unique_ptr nicht kopierbar ist. Was man bräuchte, wäre ein vector::emplace , das die Argumente vor dem Konstruieren kopiert.

[SeppJ]

Fytch schrieb:

Geht hier nicht, da unique_ptr

Andere Faustregel: Relevante Informationen nicht in den Titel eines Threads packen. Dann besteht eine sehr viel höhere Chance, dass sie auch wahrgenommen wird, bevor dir jemand antwortet.

[Fytch]

SeppJ schrieb:

Andere Faustregel: Relevante Informationen nicht in den Titel eines Threads packen. Dann besteht eine sehr viel höhere Chance, dass sie auch wahrgenommen wird, bevor dir jemand antwortet.

Da hast du recht, habs angepasst.

[SeppJ]

Leider habe ich so spontan auch keine Idee, wie man das ohne Speicheroverhead machen kann, da es aus Gründen kein emplace_n gibt. Muss mal drüber nachdenken, aber ich bin nicht zuversichtlich, dass es überhaupt geht. Daher andere Frage: Welches ist das eigentliche Problem, das hier gelöst werden soll? Vielleicht gibt es ja viel bessere Lösungen für das Gesamtproblem, bei denen es nicht nötig ist, m Nullpointer an eine bestimmte Stelle eines Vectors einzufügen.

[manni66]

Mit resize und std::rotate?

#include <iostream>
#include <vector>
#include <memory>
#include <algorithm>

template <typename Cont>
void print( const Cont& c )
{
  for( const auto& i : c ) std::cerr << ( i ? *i : -1 ) << " ";
  std::cerr << "\n";
}

int main()
{
  std::vector<std::unique_ptr<int>> v;
  for( int i = 1; i <= 10; ++i ) {
     v.emplace_back(std::make_unique<int>(i));
  }

  v.resize(15);
  print(v);
  std::rotate( begin(v)+5, begin(v)+10, end(v));
  print(v);
}

[Fytch]

@SeppJ: der Ort, an dem ich die nullptr s einfügen möchte, wird später nach und nach von verschiedenen Threads mit echten Objekten befüllt. Die Reihenfolge dieser Objekte ist willkürlich aber die Anzahl steht von vornherein fest. Ich könnte einen zweiten Vektor als Zwischenpuffer verwenden, aber das bedeutet eine zusätzliche Allokation, da ich sie am Ende ohnehin in den großen Vektor hineinmove. Daher möchte ich direkt zu Beginn den Speicher an der richtigen Stelle alloziieren.

@manni66: Clever! Danke, funktioniert so.

LG

EDIT: Typo

[wob]

Ich bin immer wieder überrascht, wie sinnvoll rotate doch ist! Ich kannte das lange Zeit überhaupt nicht bzw. konnte mir keinen sinnvollen Einsatzzweck vorstellen, bis ich den "C++ Seasoning"-Vortrag von Sean Parent gesehen hatte.

Wahrscheinlich gibt es noch etliche solcher Dinge, die man wissen sollte!