C++:
int in_vektor(vector<int> v, int a)
{
for( unsigned int i = 0; i < v.size(); i++){
if( a == v[i] ){
return 1;
}
}
return 0;
}
Was falsch ist? Ganz einfach! Du benutzt eine Container-Klasse des Std.. Alle Klassen des Std. befinden sich im Namensraum std.
C++:
int in_vektor(std::vector<int> v, int a)
{
for( unsigned int i = 0; i < v.size(); i++){
if( a == v[i] ){
return 1;
}
}
return 0;
}
Kurze Einführung in Optimierung u. Stil-Fragen
Was kann man verbessern? Na, so ziemlich alles
1. Funktionskopf
Hier kopierst du sowohl dein a als auch deinen std::vector, den du übergeben bekommst. Das kann bei größeren Datensätzen und evtl. anderen Dingen als int schonmal ziemlich teuer sein!
Dann ist dein Rückgabewert etwas "bescheiden" gewählt. Hier passt wohl ein boolean viel besser!
Okay, wie umgehen wir das mit dem kopieren von dem std::vector u. dem int? Ganz einfach: Referenzen o. Zeiger sind die Lösung! Na gut und da wir an denen nicht rumpfuschen wollen, setzen wir die als konstant. Da meckert der Compiler direkt falls wir Mist bauen. Das selbe gilt für den Rückgabewert:
C++:
if (in_vector(foo, 1) = 0)
Was passiert bei deiner Variante? Korrekt, die if-Bedingung ist immer erfüllt! Also auch hier const und diese Zuweisung ist nichtmehr möglich.
Dann noch schnell ein wenig aussagekräftigere Namen und den Rechtschreibfehler (ve
ctor) korrigiert und du hast folgendes:
C++:
const bool in_vector(std::vector<int> const& vec, const int value)
2. Implementierung
C++:
{
for( unsigned int i = 0; i < v.size(); i++){
if( a == v[i] ){
return 1;
}
}
return 0;
}
Es ist schonmal löblich, das dir aufgefallen ist, das i wohl kaum < 0 sein wird und d.h. unsigned hier korrekt ist. Aber das stimmt nicht ganz, denn auch wenn std::size_t, der im Std. als Typ für Größen definiert ist, meist einem unsigned int entspricht, muss dies aber nicht sein. Aber am besten: std::vector<int>::size_type, damit hast du den selben Typ wie bei vec.size() und kannst dir jedes implizit cast sparen
Dann das typische Pre- u. Post-Inkrementieren. Pre ist schneller, weil du dir das kopieren ersparst. Bei einfachen Typen wie int evtl. zu vernachlässigen, bei anderen aber auf keinen Fall und Einheitlichkeit reduziert Fehler!
Na gut, dann rufst du vor jeden Schleifenaufruf vec.size() ab. Um auch hier bischen zu optimieren, einfach vorher den Wert davon als konstante ablegen (const std::vector<int>::size_type size(vec.size())
und diese dann nutzen (i < size; ).
Nja aber dann kommt in der nächsten Zeile die Stelle, wo du den Index-Operator nutzt. Von d.h. können wir uns die vorherige Optimierung der Schleife sparen und das ganze auf eine noch wesentlich schnellere Weise machen: Iteratoren (wenn keine extra Klasse, dann Zeiger als solche ansehen
).
C++:
{
std::vector<int>::const_iterator it_end(vec.end());
for (std::vector<int>::const_iterator it(vec.begin()); it != it_end; ++it)
if (it->operator==(value)) return true;
return false;
}
So, wenn du jetzt nen Performance Analyser darüber laufen lässt, wirst du schon bei so einer einfachen Funktion enormen Geschwindigkeitsgewinn feststellen (pack einfach mal 10000 Daten in nen std::vector oder so).
3. Wiederverwendbarkeit
Okay aber so ist die Funktion noch nicht wiederverwendbar genug. Warum nur int als Typ zulassen? Wie geht's anders? Templates!
Einen Template-Parameter für den Value-Type anlegen und überall int durch diesen ersetzen.
C++:
template <typename value_type>
const bool in_vector(std::vector<value_type> const& vec, value_type const& value)
{
std::vector<value_type>::const_iterator it_end(vec.end());
for (std::vector<value_type>::const_iterator it(vec.begin()); it != it_end; ++it)
if (it->operator==(value)) return true;
return false;
}
So, schon können wir auch jeden anderen std::vector zulassen, der einen Operator== hat
Alles schön und gut, aber das ist mir zu lang?!
4. Die Std. Bibliothek u. ihre Funktionen / Der Einzeiler
C++:
#include <algorithm>
#include <vector>
template <typename value_type>
inline const bool in_vector(std::vector<value_type> const& vec, value_type const& value)
{ return std::find(vec.begin(), vec.end(), value) != vec.end(); }
So, damit jetzt dann mal viel Spaß
