In Vektor<struct> suchen

Onubub

Hallo an alle!

Ich habe z.B folgendes Strukt:

struct GdomWW 
{
	int arcid;
	double value;

};

Dieses Strukt packe ich einen Vektor!

vector<GdomWW> readGdomWWFile(string filename) {   // --  Tabelle lesen
	cout<<"Lese GDomWW file!"<<endl;
	ifstream file(filename);
	vector<GdomWW> table;
	if (!file.is_open()) {
		cerr << "Fehler beim Oeffnen der Datei" << endl;
		return table;
	}

	file.ignore(numeric_limits<streamsize>::max(), '\n'); // erste Zeile überspringen
	for (GdomWW s; file >>setprecision(16)>> s.arcid >> Char<','> >> s.value;)
		table.push_back(s);
	if (!file.eof()) // falls bis End-Of-File gelesen wurde, ist alles iO
	{
		cerr << "Fehler beim Lesen der Datei" << endl;
		return table;
	}

	return table;
}

Nun meine Frage: Wie suche ich in einen vektor<GdomWW> am effizentesten?
Z.B. nach einer bestimmten arcid?

Vielen Dank schon mal

Columbo

Ein Funktor:

struct GdomWW 
{
    int arcid;
    double value;

    struct CompareArcIds
    {
        int id;

        bool operator()( GdomWW const& obj ) const
        {
            return obj.arcid == id;
        }
    };
};

// ...

auto iter = std::find_if( vec.begin(), vec.end(), GdomWW::CompareArcIds{7} ); // vec steht für deinen vector

(ungetestet)
Falls du kein C++11 zur Verfügung hast, schreibe einen entsprechenden Konstruktor für CompareArcIds , ersetze die geschweiften Klammern in der letzten Zeile durch runde, und ersetze das auto durch std::vector<GdomWW>::iterator .

TNA

Onubub schrieb:

Nun meine Frage: Wie suche ich in einen vektor<GdomWW> am effizentesten?
Z.B. nach einer bestimmten arcid?

Du kannst natürlich immer eine Lineare Suche machen. Wenn es schneller gehen soll, musst du vorher sortieren, aber man kann den Vektor natürlich immer nur nach einem Kriterium gleichzeitig sortieren. Funktionen dafür findest du in <algorithm>

Columbo

Ach, die Frage ist, wie du es am effizientesten machst, nicht, wie überhaupt.

Tja, ein vector ist prinzipiell unsortiert, daher ist dort eine lineare Suche angebracht, die du wie im obigen (hoffentlich fehlerfreien) Beispiel vollführen kannst.

Solltest du einen immer sortierten Container benötigen, schau dir mal std::set / std::multiset an.

Onubub

Arcoth schrieb:

Ein Funktor:
struct GdomWW 
{
    int arcid;
    double value;
 
    struct CompareArcIds
    {
        int id;

        bool operator()( GdomWW const& obj ) const
        {
            return obj.arcid == id;
        }
    };
};

// ...

auto iter = std::find( vec.begin(), vec.end(), GdomWW::CompareArcIds{7} ); // vec steht für deinen vector
(ungetestet)
Falls du kein C++11 zur Verfügung hast, schreibe einen entsprechenden Konstruktor für CompareArcIds , ersetze die geschweiften Klammern in der letzten Zeile durch runde, und ersetze das auto durch std::vector<GdomWW>::iterator .

Danke für die schnelle Antwort.

könntest du mir das noch ein bisschen näher erklären?

TNA

Wäre es hier nicht einfacher und intuitiver den Vergleichsoperator zu überladen oder einfach std::find_if mit einer kleinen Lambdafunktion?

Columbo

TNA schrieb:

Wäre es hier nicht einfacher und intuitiver den Vergleichsoperator zu überladen

Und dann ein unnötiges temporäres Objekt zu erstellen?
Abgesehen davon nahm ich an, arcid ist irgendein Element, dass dem Objekt aber definitiv keine 'Identität' verleiht. Wenn man den Vergleichsoperator überlädt, dann ist das recht allgemein.

oder einfach std::find_if mit einer kleinen Lambdafunktion?

Nein! Wenn schon richtiges C++11, dann gleich range-based for:

for( auto const& i : vec )
    if( i.arcid == 7 )
    {
        // tu etwas mit i
        break; // Abbrechen, falls gewünscht
    }

Wieso irgendein ekliges Biest wie

std::find_if( std::begin(vec), std::end(vec), []( GdomWW const& g ){ return g.arcid == 7; } );

?

Onubub

Wieso irgendein ekliges Biest wie

std::find_if( std::begin(vec), std::end(vec), []( GdomWW const& g ){ return g.arcid == 7; } );

?

Ja genau!

Onubub

Ist denn

for( auto const& i : vec )
    if( i.arcid == 7 )
    {
        // tu etwas mit i
    }

schneller als

struct GdomWW 
{
    int arcid;
    double value;

    struct CompareArcIds
    {
        int id;

        bool operator()( GdomWW const& obj ) const
        {
            return obj.arcid == id;
        }
    };
};

// ...

auto iter = std::find( vec.begin(), vec.end(), GdomWW::CompareArcIds{7} ); // vec steht für deinen vector

camper

Arcoth schrieb:

oder einfach std::find_if mit einer kleinen Lambdafunktion?

Nein! Wenn schon richtiges C++11, dann gleich range-based for:
for( auto const& i : vec )
    if( i.arcid == 7 )
    {
        // tu etwas mit i
    }
Wieso irgendein ekliges Biest wie
std::find_if( std::begin(vec), std::end(vec), []( GdomWW const& g ){ return g.arcid == 7; } );
?

Und das macht schon mal etwas ganz anderes...

Columbo

Ich sehe es sofort. Ich habe das break; vergessen. Das stand da ursprünglich, ich habe keinen blassen Schimmer, wieso es verschwunden ist.

Onubub

Wie bekomme ich die position raus wenn ich die gewünschte zahl in meinen vektor gefunden habe?

for( auto const& i : vec )
    if( i.arcid == 7 )
    {
        // tu etwas mit i
    }

Columbo

Ach, du willst die Position? Das ist etwas anderes. Ich dachte, du willst das Element, um damit direkt etwas zu tun. In dem Fall, nimm einfach die Version mit std::find_if und wende std::distance an (um den Abstand zum Anfang des Vektors zu bekommen).
Falls du überhaupt tatsächlich die Position brauchst, und nicht irgendeinen Iterator.

Oder du durchläufst den Vektor mit einem Index, dann hast du den Index bzw. die Position direkt.

Onubub

Und was wäre schneller weil ich öfters in großen Vektoren suche!

Arcoth schrieb:

In dem Fall, nimm einfach [megamühsame Hacks]

Genau das stört mich an den neuen for-Loops. Wenn ich im Nachhinein den Iterator oder sowas von dem Element will, muss ich alles umschreiben. Jeden . in ->. Also praktisch das Gegenteil von generisch.

Onubub schrieb:

Und was wäre schneller weil ich öfters in großen Vektoren suche!

Maps verwenden
In Vektoren suchen ist immer langsam, egal wie du es machst (und alle Varianten sind gleich schnell).

Onubub

epicfail++11 schrieb:

Onubub schrieb:

Und was wäre schneller weil ich öfters in großen Vektoren suche!

Maps verwenden
In Vektoren suchen ist immer langsam, egal wie du es machst (und alle Varianten sind gleich schnell).

Ja aber ich habe auch eine struktur die so aussieht

struct CityWaterMap // eine struct für die City Water Map Tabelle
{
	int arcid_dvsn;
	int kontiID_dvsn;
	int arcid_city;
	int kontiID_city;
	double share_dvsn; // 3.Spalte ist eine Fließkommazahl
	int arcid_ret_flow;
};

Da dachte ich ein Vektor wäre da besser.

Man kann sich einen Vector (oder ein eigens äquivalent) auch sortiert halten, und dann ein binäre Suche darauf anwenden. Das macht suchen und drüberiterieren dann recht schnell, aber einfügeoperationen werden dafür dann richtig teuer.

Nathan

Onubub schrieb:

epicfail++11 schrieb:

Onubub schrieb:

Und was wäre schneller weil ich öfters in großen Vektoren suche!

Maps verwenden
In Vektoren suchen ist immer langsam, egal wie du es machst (und alle Varianten sind gleich schnell).

Da dachte ich ein Vektor wäre da besser.

Die Entscheidung für/gegen vector hat doch nichts damit zu tun, was du darin speicherst*, sondern was du damit machen willst.
Brauchste einen vector, nimmste einen vector.
Brauchste eine map, nimmste eine map.

*Ja, ja std::list hat einen size overhead per element, der bei kleinen Typen ins Gewicht fällt.

Musst du nur nach arcid_dvsn suchen, oder nach allen Eigenschaften (oder kannst du verkraften, nach den anderen langsamer zu suchen)?

Wenn nur nach arcid_dvsn, dann ist eine Map klar am besten.

Wenn nicht, brauchst du ein etwas komplexeres Setup, das etwas Overhead beim Einfügen verursacht und mehr Speicher verbraucht, dafür superschnell im Suchen ist.

vector<CityWaterMap> BigCityMap; // Vektor zum Speichern der Elemente

map<int, std::size_t> arcid_view; // arcid to vector-Index
map<int, std::size_t> kontiID_view; // kontiID to vector-Index

// Suchen:
int arcid_to_search = ...; // nach dem Suchen wir
CityWaterMap& found = BigCityMap[arcid_view[arcid_to_search]]; // Gefunden!

// Einfügen:
CityWaterMap newCity;
BigCityMap.push_back(newCity);
arcid_view[newCity.arcid] = BigCityMap.size()-1;
kontiID_view[newCity.kontiID] = BigCityMap.size()-1;

Die Grundregel im Optimieren für C++ ist: Messen. Nimm erst einmal einen Vektor, das ist am einfachsten. Wenn sich herausstellt, dass der zu langsam ist, dann mach wechsle zu Map. Aber erst, nachdem du nachgewiesen hast, dass es wirklich das Suchen im Vektor ist, was so viel Zeit braucht.

In Vektor&lt;struct&gt; suchen

In Vektor<struct> suchen