Ich dachte nur, wenn ich std::inplace_merge es wahrscheinlich so etwas wie dies aussehen würde implementieren waren:Ist es möglich, eine Inplace Merge ohne temporären Speicher durchzuführen?
template <class Bi, class Cmp>
void inplace_merge(Bi first, Bi middle, Bi last, Cmp cmp) {
if(first != last) {
typedef typename iterator_traits<Bi>::value_type T;
typedef typename iterator_traits<Bi>::difference_type Dist;
const Dist count = distance(first, last);
if(count != 1) {
// can I avoid this allocation?
T *const temp = new T[count];
merge(first, middle, middle, last, temp, cmp);
copy(temp, temp + count, first);
delete [] temp;
}
}
}
Ich weiß, dass ich nur die vorhandene Implementierung verwenden könnte, aber das ist irgendwie nebensächlich. Ich war nur neugierig, ob es einen besseren Algorithmus als das, was ich weiß, gab.
Der Grund dafür in den Sinn kam, dass die meisten der C++ Standardbibliothek (alle von der STL, wenn ich mich recht erinnere), der Benutzer angeben können, wie und wo Zuweisungen ausführen, aber wenn std::inplace_merge erfordert eine Zuweisung von Design es scheint, dass es keine Möglichkeit gibt, dies zu kontrollieren, wenn es ein Problem wäre.
denke ich, ein Hinweis auf die Antwort aus dem Standard kommt selbst in Bezug auf die Komplexität der std::inplace_merge:
Komplexität: Wenn genügend zusätzliche Speicher verfügbar ist, (letzte - erste) - 1 Vergleiche. Wenn kein zusätzlicher Speicher verfügbar ist, kann ein Algorithmus mit Komplexität N log N (wobei N gleich ist, um zuletzt zu dauern) verwendet werden.
Für mich bedeutet dies, dass die bekannten effizienten Versionen des Algorithmus zusätzlichen Speicherplatz benötigen. Lies ich das richtig? Wenn ja, wird erwähnt, woher der Speicher kommen soll?
In-Place, * per Definition *, erfordert keine zusätzlichen Speicherzuweisungen (es erfordert nur O (1) temporären Speicher auf dem Stapel). Ihre Implementierung ist nicht vorhanden. –
@Adam: Inkorrekt, bedeutet dies, dass die Ergebnisse im selben Speicher wie die Quelle sind (im Gegensatz zu nur 'merge', die die Ergebnisse in einen vom Aufrufer bereitgestellten Puffer legt). Beispielsweise verwendet STLPort temporären Speicher in der Form von: '_Temporary_buffer <_BidirektionalIter, _Tp >__buf (__ zuerst, __last);' wenn Sie ihre Implementierung betrachten. –
Nach weiteren Untersuchungen scheint es, dass es keine einzige Definition von "in-place" gibt (siehe http://en.wikipedia.org/wiki/In-place_algorithm). Die traditionelle Definition, die von Algorithmus-Theoretikern verwendet wird, ist eine, die O (1) zusätzlichen Speicher verwendet, während diejenige, die vom C++ - Standard verwendet wird, offensichtlich dieselbe verwendet, die den gleichen Speicher für Eingabe und Ausgabe verwendet. –