Ich brauche Hilfe bei der Erstellung einer Einfügefunktion für diese Vektorklasse

Question

Rufen Sie Ihren Treiber "vector_test_driver.cpp" und Ihre Klassenimplementierungsdatei "VLIST.cpp". Definieren Sie für VLIST das folgende Verhalten:

1. Implementieren Sie einen Standardkonstruktor. Fügen Sie bei jedem Aufruf der Funktion die folgende Meldung ein: "Default Constructor Invoked".

2. Implementieren Sie einen Kopierkonstruktor, um eine tiefe Kopie eines VLIST-Objekts auszuführen. Fügen Sie bei jedem Aufruf der Funktion die folgende Nachricht ein: "Konstruktor aufgerufen" ". Die Funktion sollte auch den Inhalt jedes VLIST-Objekts auf einzelnen separaten Zeilen ausgeben.

3. Implementieren Sie den Destruktor. Schließen Sie bei jedem Aufruf der Funktion die folgende Meldung ein: "Destructor Invoked".

4. Implementieren Is_Full(), die wahr zurückgibt, wenn voll; sonst falsch; Fügen Sie die Meldung "Is_Full aufgerufen“ jedes Mal, wird die Funktion aufgerufen

5. Is_Empty() implementieren, die true zurück, wenn leer,. Andernfalls false; die Nachricht einschließen "is_empty aufgerufen“ jedes Mal, wenn die Funktion aufgerufen wird.

6. Implementieren Sie die Elementfunktion "Search", um den Vektor nach einem Element zu durchsuchen. Die Funktion sollte die Meldung "Artikel gefunden" oder "Artikel nicht gefunden" drucken. Welche Nachricht gedruckt wird, hängt davon ab, ob das Element im Vektor gefunden wurde oder nicht. Drucken Sie den gewünschten Artikel (Suchschlüssel). Fügen Sie die folgende Meldung "Suche aufgerufen" bei jedem Aufruf der Funktion ein.

7. Implementieren Sie eine Funktion namens "Einfügen", um ein Element dem Vektor in der Reihenfolge (alphabetische Reihenfolge) hinzuzufügen. Die Funktion sollte den Inhalt des VLIST-Objekts vor und nach der Ausführung der Funktion in einzelnen separaten Zeilen ausgeben. Fügen Sie bei jedem Aufruf der Funktion die folgende Meldung ein: "Insert Invoked".

8. Implementieren Sie eine Funktion namens "Remove", um ein Element aus dem Vektor zu entfernen. Die Funktion sollte den Inhalt des VLIST-Objekts vor und nach der Ausführung der Funktion in einzelnen separaten Zeilen ausgeben. Schließen Sie bei jedem Aufruf der Funktion die folgende Meldung ein: "Remove Invoked".

Hier meine Klassendefinition:

class VLIST 
{ 
public: 
//VLIST();    //default constructor 
//VLIST(const VLIST &); //copy constructor 
//~VLIST();    //destructor 
//bool IsEmpty();   //return true if empty; otherwise false 
//bool IsFull();   //return true if full; otherwise false 
//vector<string>::iterator Search(const string &); //returns the location of the string in the dynamic array 
//void Insert(const string & key); //add key to dynamic array if not full; otherwise prints a message stating dynamic array is full 
//void Remove(const string & key); //removes key from dynamic array if it is there; otherwise prints a message stating it was not in dynamic array; the function using an iterator and the erase function to remove an item from the vector. 
//void Print(); //Print every string in the array 
//other functions may be implemented if necessary 
private: 
// VLIST<string> DB; //vector 
//additonal state variables you may wish add 
}; 

Mein Code für die Insert-Funktion so weit;

void VLIST::Insert(const string & key) { 
     cout << "Insert invoked" << endl; 

     vector<string>::iterator vec; 
     vec = DB[count].begin(); 
     DB[count].at(1) = key; 

     count++; 
     } 

Ich bin ein bisschen nur Aufnahmen im Dunkeln. Ich bin mir sicher, dass mir eine Freund-Funktion wahrscheinlich helfen würde, auf Db zuzugreifen, da es privat ist. Aber ich habe versucht, mich an das Skelett zu halten, das man mir gegeben hat. Ich bin mir nicht sicher, wie man den Vektor korrekt implementiert, um Strings in einer Funktion einzufügen und in eine andere Funktion zu drucken.Ich will nicht die ganze Zuordnung getan, ich möchte nur, um zu sehen, wie die Insert-Funktion

Die Druckfunktion komme ich habe mit so weit nach oben umgesetzt werden könnte:

void VLIST::Print() { 

    for (int i = 0; i < count;i++) { 
     cout << " " << DB[count].at(i) << endl; 
    } 

Answer 1

Sie müssen "Implementieren" eine Einfügesortierung für std::vector. Es ist nicht klar, warum Ihr Professor diese Datenstruktur eine Liste nennt, sondern Sie zwingt, ein dynamisches Array zu verwenden (wahrscheinlich, um es zu imitieren). Ich würde so etwas tun. Achte nicht auf die Behauptungen.

void Insert(const std::string& key) 
    { 
    std::cout << "Insert Invoked.\n"; 
    print_db(std::cout); 
    assert(std::is_sorted(std::begin(db_), std::end(db_))); // Expects(std::is_sorted(db_)); 

    db_.push_back(key); 
    auto insert_pos = std::upper_bound(std::begin(db_), std::end(db_)-1, key); 
    std::rotate(insert_pos, std::end(db_)-1, std::end(db_)); 

    assert(std::is_sorted(std::begin(db_), std::end(db_))); // Ensures(std::is_sorted(db_)); 
    print_db(std::cout); 
    } 

Hier ist ein Demo.

Schauen Sie genau, was ich getan habe und versuchen Sie es in Ihr Modell zu passen. Versuchen Sie anstelle von std::upper_bound Ihre Search Methode und so weiter zu verwenden.

Eine Sache, die Sie generell mitnehmen sollten, ist die Idee, die Algorithmen, die vom Standard zur Verfügung gestellt werden, wiederzuverwenden. Nachschlagen, was std::rotate und std::upper_bound tun (für RandomAccessIterator s).

Wenn Sie eine binäre Suche für sich selbst implementieren, achten Sie darauf, wie viele Vergleiche Sie genau durchführen, da std::string Vergleiche sehr teuer sein können. Sie können eine binary_search mit "genau" log(n) Vergleiche (ein Vergleich pro Schleife, nicht zwei oder ähnliches) tun.