Zeit/Speicher effizientes Arbeiten mit std :: vector

Question

Ich bin Umsetzung derzeit Astar Algorithmus, bei dem jeder Knoten in Vektor gespeichert wird und dann wieder auf äußere Objekt - wie folgt aus:

class Astar 
{ 
    std::vector<Node> find() 
    { 
     std::vector<Node> open; 
     std::vector<Node> closed; 
     std::vector<Node> path; 

     //A_star algorithm working with open and closed vectors 
     //when path found fill path with push_back() 

     return path; 
    } 
} 

Im äußeren Objektcode aussieht ähnlich wie diese:

class Foo 
{ 
    Astar astar; 
    std::vector<Node> path; 
    void findPath() 
    { 
     path = astar.find(); 
    } 
    //do stuff with path 
} 

Grund, warum findPath() vorhanden ist, dass ich in einem anderen Thread es laufen zu wollen, also, wenn Pfad gefunden wird - Dinge tun, sonst - vielleicht ist es Zeit, Weg zu finden (vereinfacht). Sache, die mich stört, ist path = astar.find();, weil es eine Menge kopieren kann (nicht zu erwähnen, dass push_back() in Astar Klasse auch Wert kopiert).

Mögliche Lösungen Ich dachte sind: Foo std::vector<Node> path; Referenz als Argument übergeben zu Astar ‚s find(); oder Freundschaft machen zwischen Foo und Astar so Foo privaten Pfad zugreifen konnte. Vor mir steht die Zeit- und Speichereffizienz (time over memory).

Answer 1

Denken Sie daran, dass C++ Return Value Optimization zulässt, daher ist die Rückgabe eines Vektors nach Wert an sich kein Problem.

jedoch:

• Es ist kostspielig wiederholte Zuordnungen von Objekten zu tun, die nur einmal vergeben werden könnten. Man könnte also theoretisch von der Methode eine Referenz oder einen Zeiger auf einen Puffer für den Pfad nehmen, der garantiert genügend Speicher haben muss. Auf diese Weise wird der äußere Code nur einmal zugewiesen und kann seinen Puffer für wiederholte Aufrufe wiederverwenden.
• Es ist teuer, ein Objekt zu konstruieren, das Sie nicht verwenden möchten. Vielleicht möchten Sie eine Methode namens has_path(const Node& source, const Node& target) oder sogar eine eigenständige Funktion mit dieser Funktionalität.