🔤 😾 👨🏽‍✈️ Björn Straustrup beantwortet die Top 5 C ++

Im Vorfeld des Kursbeginns erstellte "C ++ Developer" eine Übersetzung von interessantem Material.

Marielle Frank und Sonny Lee, Autoren des Learn C ++ - Kurses über Codecademy, hatten kürzlich die Gelegenheit, Dr. Björn Straustrup, den Erfinder von C ++, zu interviewen.

Im Rahmen dieses Interviews beantwortete er die C ++ - Fragen, die die meisten Stimmen zu Stack Overflow erhielten. Obwohl alle Interviews lesenswert sind, erlaubte uns die Codecademy großzügig, einen Teil davon zu teilen.

Wenn Sie sich jemals gefragt haben, ob es definitiv umfassende Antworten zum Stapelüberlauf gibt, dann ist hier etwas, das dem am nächsten kommt, das Sie sicher bekommen können (obwohl wir erwarten, dass jemand anderer Meinung ist).

Warum ist die Verarbeitung eines sortierten Arrays schneller als die Verarbeitung eines unsortierten Arrays?

Hinweis: Diese Frage ist die Nummer 1, die die meisten Stimmen zum Stapelüberlauf aller Zeiten erhalten hat.

Klingt nach einer Frage aus einem Interview. Es stimmt? Wie hast du das gewusst? Es ist schlecht, Fragen zur Effizienz zu beantworten, ohne vorläufige Messungen durchzuführen. Daher ist es wichtig zu wissen, wie man sie misst.
Also überprüfte ich einen Vektor von einer Million Ganzzahlen und bekam:

Ich habe das ein paar Mal ausgeführt, um sicherzugehen. Ja, dieses Phänomen ist real. Mein Hauptcode war:

void run(vector<int>& v, const string& label)
{
    auto t0 = system_clock::now();
    sort(v.begin(), v.end());
    auto t1 = system_clock::now();
    cout << label 
         << duration_cast<microseconds>(t1 — t0).count() 
         << " milliseconds\n";
}

void tst()
{
    vector<int> v(1'000'000);
    iota(v.begin(), v.end(), 0);
    run(v, "already sorted ");
    std::shuffle(v.begin(), v.end(), std::mt19937{ std::random_device{}() });
    run(v, "shuffled    ");
}

Zumindest ist dieses Phänomen bei diesem Compiler, der Standardbibliothek und den Optimierungseinstellungen real. Unterschiedliche Implementierungen können unterschiedliche Antworten geben (und geben). Tatsächlich hat jemand eine systematischere Studie durchgeführt (eine schnelle Suche im Internet hilft Ihnen dabei, sie zu finden), und die meisten Implementierungen zeigen diesen Effekt.

Einer der Gründe ist die Verzweigungsvorhersage: Die Schlüsseloperation im Sortieralgorithmus ist "if (v [i] <Pivot]) ..." oder das Äquivalent. Für eine sortierte Sequenz ist dieser Test immer wahr, während sich für eine zufällige Sequenz der ausgewählte Zweig zufällig ändert.

Ein weiterer Grund ist, dass wir die Elemente niemals an die richtige Position verschieben müssen, wenn der Vektor bereits sortiert ist. Die Wirkung dieser kleinen Details ergibt einen Faktor von ungefähr fünf oder sechs, den wir beobachtet haben.

Quicksort (und Sortieren im Allgemeinen) ist eine komplexe Studie, die einige der größten Köpfe der Informatik angezogen hat. Eine gute Sortierfunktion ist das Ergebnis der Auswahl eines guten Algorithmus und der Berücksichtigung der Geräteleistung während seiner Implementierung.
Wenn Sie effizienten Code schreiben möchten, müssen Sie die Architektur der Maschine berücksichtigen.
———————————————————————————————
Entschuldigung für die Intervention. Nur eine Erinnerung daran, dass der Stack Overflow-Podcast zurück ist! Schauen Sie vorbei und hören Sie ein Interview mit unserem neuen CEO.

Was ist der Operator -> in C ++?

Dies ist eine alte Trickfrage. In C ++ gibt es keinen Operator ->. Folgendes berücksichtigen:

if (p-->m == 0) f(p);

Dies sieht natürlich so aus, als gäbe es eine Art Operator -> und mit einer geeigneten Deklaration p und m können Sie dies sogar kompilieren und ausführen:

int p = 2;
int m = 0;
if (p-->m == 0) f(p);

Dies bedeutet tatsächlich: Sehen Sie, ob p-- größer als m ist (so wie es ist), und vergleichen Sie dann das Ergebnis (wahr) mit 0. Nun, wahr! = 0, also ist das Ergebnis falsch und f () wird nicht aufgerufen. Mit anderen Worten:

if ((p--) > m == 0) f(p);

Bitte verbringen Sie nicht zu viel Zeit mit solchen Fragen. Sie waren schon vor der Erfindung von C ++ beliebt, um Anfänger zu verwirren.

Die beste Anleitung und Liste der C ++ - Bücher

Leider gibt es keine kanonische Liste der C ++ - Bücher. Dies kann im Prinzip nicht sein. Nicht jeder benötigt die gleichen Informationen, nicht jeder hat die gleichen Erfahrungen, und die Best Practices für C ++ werden ständig weiterentwickelt.

Ich habe ein wenig im Internet recherchiert und eine erstaunliche Reihe von Empfehlungen gefunden. Viele waren ernsthaft veraltet und einige waren einfach schlecht. Ein Anfänger, der ein gutes Buch ohne Anleitung sucht, wird sehr verwirrt sein!

Sie brauchen wirklich ein Buch, da die Methoden, die C ++ effektiv machen, in mehreren Blogs zu bestimmten Themen nicht leicht zu finden sind und Blogs natürlich auch unter Fehlern, Veralterung und schlechten Erklärungen leiden. Oft konzentrieren sie sich auch auf fortgeschrittene neue Themen und ignorieren die Grundprinzipien.

Ich empfehle meine Programmierung: Grundsätze und Praxis der Verwendung von C ++ (2. Ausgabe) für Personen, die gerade erst mit dem Programmieren beginnen, und C ++ Tour (2. Ausgabe) für Personen, die bereits Programmierer sind und sich mit modernem C ++ vertraut machen müssen. Menschen mit einem starken mathematischen Hintergrund können mit der Entdeckung des modernen C ++ beginnen: Ein Intensivkurs für Wissenschaftler, Ingenieure und Programmierer Peter Gottschling.

Sobald Sie C ++ für real verwenden, benötigen Sie eine Reihe von Richtlinien, um zu unterscheiden, was getan werden kann und was eine gute Praxis ist. Dafür empfehle ich die C ++ Core Guidelines auf GitHub.

Für eine gute kurze Erläuterung der einzelnen Sprachmerkmale und -funktionen der Standardbibliothek empfehle ichwww.cppreference.com .

# 4. Was sind die Unterschiede zwischen einer Zeigervariablen und einer Referenzvariablen in C ++?

Weitere Informationen zu Links und Zeigern finden Sie unter Learn C ++ .

Beide werden im Speicher als Maschinenadresse dargestellt. Der Unterschied liegt in ihrer Verwendung.
Um den Zeiger zu initialisieren, geben Sie ihm die Adresse des Objekts:

int x = 7;
int* p1 = &x;
int* p2 = new int{9};

Zum Lesen und Schreiben eines Zeigers verwenden wir den Dereferenzierungsoperator (*):

*p1 = 9;       // write through p1
int y = *p2;   // read through p2

Wenn wir einen Zeiger einem anderen zuweisen, zeigen beide auf dasselbe Objekt:

p1 = p2;       //  p1  p2    int   9
*p2 = 99;      //  99  p2
int z = *p1;   //   p1, z  99 (  9)

Beachten Sie, dass ein Zeiger während seines Lebenszyklus auf verschiedene Objekte zeigen kann. Dies ist der Hauptunterschied zu Links. Der Link wird beim Erstellen an das Objekt angehängt und kann nicht in einen Link zu einem anderen konvertiert werden.

Für Referenzen ist die Dereferenzierung implizit. Sie initialisieren den Link mit dem Objekt und der Link erhält seine Adresse.

int x = 7;
int& r1 = x;
int& r2 = *new int{9};

Der neue Operator gibt einen Zeiger zurück, daher musste ich ihn vor der Zuweisung dereferenzieren, um den Link zu initialisieren.

Zum Lesen und Schreiben über einen Link verwenden wir einfach den Linknamen (ohne explizite Dereferenzierung):

r1 = 9;        //   r1
int y = r2;    //   r2

Wenn wir einen Link einem anderen zuweisen, wird der angegebene Wert kopiert:

r1 = r2;       //  p1  p2     9
r1 = 99;       //  99  r1
int z = r2;    //   r2, z  9 (  99)

Sowohl Referenzen als auch Zeiger werden häufig als Argumente für eine Funktion verwendet:

void f(int* p)

{
    if (p == nullptr) return;
    // ...
}

void g(int& r)
{
    // ...
}

int x = 7;
f(&x);
g(x);

Möglicherweise gibt es einen Zeiger nullptr, daher sollten wir prüfen, ob er auf etwas verweist. Über den Link können Sie zunächst annehmen, dass er sich auf etwas bezieht.

# 5. Wie iteriere ich über String-Wörter?

Verwenden Sie stringstream, aber wie definieren Sie ein "Wort"? Denken Sie: "Mary hatte ein kleines Lamm." Das letzte Wort ist "Lamm" oder "Lamm". Wenn es keine Interpunktion gibt, ist dies einfach:

vector<string> split(const string& s)
{
    stringstream ss(s);
    vector<string> words;
    for (string w; ss>>w; ) words.push_back(w);
    return words;
}

auto words = split("here is a simple example");   // five words
for (auto& w : words) cout << w << '\n';

oder einfach:

for (auto& w : split("here is a simple example")) cout << w << '\n';

Standardmäßig überspringt der Operator >> Leerzeichen. Wenn wir willkürliche Mengen von Trennzeichen benötigen, werden die Dinge etwas verwirrender:

template<typename Delim>
string get_word(istream& ss, Delim d)
{
    string word;
    for (char ch; ss.get(ch); )    //  
        if (!d(ch)) {
            word.push_back(ch);
            break;
        }
    for (char ch; ss.get(ch); )    //  
        if (!d(ch))
            word.push_back(ch);
        else
            break;
    return word;
}

d ist eine Operation, die angibt, ob das Zeichen ein Trennzeichen ist, und ich gebe "" (leere Zeichenfolge) zurück, um anzuzeigen, dass kein Wort zurückgegeben werden konnte.

vector<string> split(const string& s, const string& delim)
{
    stringstream ss(s);
    auto del = [&](char ch) { for (auto x : delim) if (x == ch) return true; return false; };

    vector<string> words;
    for (string w; (w = get_word(ss, del))!= ""; ) words.push_back(w);
    return words;
}

auto words = split("Now! Here is something different; or is it? ", "!.,;? ");
for (auto& w : words) cout << w << '\n';

Wenn Sie eine C ++ 20 Range-Bibliothek haben, müssen Sie so etwas nicht schreiben, aber Sie können split_view verwenden.

Bjarn Straustrup ist technischer Partner und Geschäftsführer von Morgan Stanley New York und Gastprofessor an der Columbia University. Er ist auch der Schöpfer von C ++.

Weitere Informationen zu C ++ 20 finden Sie unter: isocpp.org .

Das ist alles. Wir sehen uns auf dem Kurs !

Björn Straustrup beantwortet die Top 5 C ++ - Fragen mit Stapelüberlauf

More articles: