Einfügen in die Mitte eines Arrays

Question

Ich habe ein Array int *playerNum in der die Liste aller Nummern der Spieler der Mannschaft gespeichert wird. Jeder Steckplatz z.B. playerNum[1]; eine Position in der Mannschaft darstellt, wenn ich einen neuen Spieler für eine neue Position in der Mannschaft hinzufügen möchte. Das heißt, ein neues Element in das Array irgendwo in der Nähe der Mitte einfügen, wie würde ich gehen über dies zu tun?

Im Moment dachte ich, dass Sie memcpy bis zu der Position, an der Sie den Player in ein neues Array einfügen möchten, und fügen Sie dann den neuen Player ein und kopieren Sie den Rest des Arrays rüber?

(Ich muss ein Array verwenden)

Answer 1

Da Sie von einem Array und "insert" sprechen, nehme ich an, dass es sich um ein sortiertes Array handelt. Sie brauchen nicht unbedingt ein zweites Array, vorausgesetzt, dass die Kapazität N Ihres bestehenden Arrays groß genug ist, um weitere Einträge zu speichern ( N>n , wobei n ist die Anzahl der aktuellen Einträge). Sie können die Einträge verschieben von k a n-1 (null-indiziert) auf k+1 a n , wobei k ist die gewünschte Einfügeposition. Einfügen des neuen Elements an der Indexposition k und erhöhen n von einem. Wenn das Feld zu Beginn nicht groß genug ist, können Sie den von Ihnen vorgeschlagenen Ansatz verfolgen oder einfach ein neues Feld mit größerer Kapazität zuweisen N' und kopieren Sie die vorhandenen Daten, bevor Sie den oben beschriebenen Einfügevorgang durchführen.

BTW: Da Sie C++ verwenden, können Sie einfach die std::vector .

Answer 2

Es ist zwar möglich, hierfür Arrays zu verwenden, aber C++ hat eine bessere Lösung zu bieten. Versuchen Sie für den Anfang std::vector ist ein ausreichender Allzweckcontainer, der auf einem dynamisch zugewiesenen Array basiert. Er verhält sich in vielen Fällen genau wie ein Array.

In Bezug auf Ihr Problem gibt es jedoch zwei Nachteile von Arrays oder Vektoren:

• Indizes müssen 0-basiert und zusammenhängend sein; Sie können keine Elemente aus der Mitte entfernen, ohne dass die Schlüssel/Wert-Zuordnungen für alle Elemente nach dem entfernten Element verloren gehen; wenn Sie also den Spieler auf Position 4 entfernen, wird der Spieler von Position 9 auf Position 8 verschoben
• Zufälliges Einfügen und Löschen (d.h. überall außer am Ende) ist teuer - O(n), d.h. die Ausführungszeit wächst linear mit der Arraygröße. Das liegt daran, dass jedes Mal, wenn Sie einfügen oder löschen, ein Teil des Arrays verschoben werden muss.

Wenn die Sache mit dem Schlüssel/Wert für Sie nicht wichtig ist, und Einfügen/Löschen ist nicht zeitkritisch, und Ihr Container wird nie wirklich groß sein, dann verwenden Sie auf jeden Fall einen Vektor. Wenn Sie eine zufällige Einfüge-/Löschleistung benötigen, aber die Schlüssel/Wert-Sache nicht wichtig ist, sehen Sie sich std::list (obwohl Sie dann keinen zufälligen Zugriff erhalten, d.h. die [] Operator ist nicht definiert, da seine Implementierung für verknüpfte Listen sehr ineffizient wäre; verknüpfte Listen sind auch sehr speicherhungrig, mit einem Overhead von zwei Zeigern pro Element). Wenn Sie Schlüssel/Wert-Zuordnungen beibehalten wollen, std::map ist Ihr Freund.