🏐 🤜 ♠️ Björn Straustrup répond aux 5 meilleures questions C ++ avec débordement de pile 💇 ◾️ 🐁

En prévision du début du cours, "C ++ Developer" a préparé une traduction de matériel intéressant.

Marielle Frank et Sonny Lee, auteurs du cours Learn C ++ sur Codecademy, ont récemment eu l'occasion d'interviewer le Dr Bjorn Straustrup, le créateur de C ++.

Dans le cadre de cette interview, il a répondu aux questions C ++ qui ont recueilli le plus de votes sur Stack Overflow.Bien que toutes les interviews valent la peine d'être lues, Codecademy nous a généreusement permis d'en partager une partie.

Si vous vous êtes déjà demandé s'il y avait des réponses définitivement complètes sur Stack Overflow, alors voici quelque chose de plus proche que vous pouvez obtenir à coup sûr (bien que nous nous attendions à ce que quelqu'un ne soit pas d'accord).

Pourquoi le traitement d'un tableau trié est-il plus rapide que le traitement d'un tableau non trié?

Remarque: Cette question est le numéro 1 qui a reçu le plus de votes sur le débordement de pile de tous les temps.

Cela ressemble à une question d'une interview. C'est vrai? Comment saviez-vous que? Il est mauvais de répondre à des questions sur l'efficacité sans prendre de mesures préliminaires, il est donc important de savoir comment les mesurer.
J'ai donc vérifié un vecteur d'un million d'entiers et obtenu:

J'ai couru cela plusieurs fois pour m'en assurer. Oui, ce phénomène est réel. Mon code principal était:

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    ");
}

Au moins, ce phénomène est réel avec ce compilateur, la bibliothèque standard et les paramètres d'optimisation. Différentes implémentations peuvent donner (et donner) des réponses différentes. En fait, quelqu'un a fait une étude plus systématique (une recherche rapide sur Internet vous aidera à le trouver), et la plupart des implémentations montrent cet effet.

L'une des raisons est la prédiction de branche: l'opération clé dans l'algorithme de tri est «if (v [i] <pivot]) ...» ou l'équivalent. Pour une séquence triée, ce test est toujours vrai, tandis que pour une séquence aléatoire, la branche sélectionnée change de façon aléatoire.

Une autre raison est que lorsque le vecteur est déjà trié, nous n'avons jamais besoin de déplacer les éléments à la bonne position. L'effet de ces petits détails donne un facteur d'environ cinq ou six, ce que nous avons observé.

Quicksort (et le tri en général) est une étude complexe qui a attiré certains des plus grands esprits de l'informatique. Une bonne fonction de tri est le résultat du choix d'un bon algorithme et de l'attention portée aux performances de l'équipement lors de sa mise en œuvre.
Si vous voulez écrire du code efficace, vous devez prendre en compte l'architecture de la machine.
—————————————————————————————
Désolé pour l'intervention. Juste un rappel que le podcast Stack Overflow est de retour! Passez nous voir et écoutez une entrevue avec notre nouveau PDG.

Qu'est-ce que l'opérateur -> en C ++?

C'est une vieille question piège. En C ++, il n'y a pas d'opérateur ->. Considérer ce qui suit:

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

Bien sûr, cela ressemble à une sorte d'opérateur -> et avec une déclaration appropriée p et m, vous pouvez même compiler et exécuter ceci:

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

Cela signifie en fait: voyez si p-- est supérieur à m (tel qu'il est), puis comparez le résultat (vrai) avec 0. Eh bien, vrai! = 0, donc le résultat est faux et f () n'est pas appelé. En d'autres termes:

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

Veuillez ne pas consacrer trop de temps à ces questions. Ils étaient populaires pour confondre les débutants avant même l'invention du C ++.

Le meilleur guide et liste de livres C ++

Malheureusement, il n'y a pas de liste canonique de livres C ++. Cela, en principe, ne peut pas l'être. Tout le monde n'a pas besoin des mêmes informations, tout le monde n'a pas la même expérience et les meilleures pratiques C ++ évoluent constamment.

J'ai fait une petite recherche sur Internet et trouvé un ensemble étonnant de recommandations. Beaucoup étaient sérieusement dépassés et certains étaient tout simplement mauvais. Un débutant à la recherche d'un bon livre sans guide sera très confus!

Vous avez vraiment besoin d'un livre parce que les méthodes qui rendent C ++ efficace ne sont pas faciles à trouver sur plusieurs blogs sur des sujets spécifiques, et bien sûr les blogs souffrent également d'erreurs, d'obsolescence et de mauvaises explications. Souvent, ils se concentrent également sur de nouveaux sujets avancés et ignorent les principes de base.

Je recommande mon Programmation: principes et pratiques d'utilisation du C ++ (2e édition) pour les personnes qui commencent tout juste à apprendre à programmer, et de la visite C ++ (2e édition) pour les personnes qui sont déjà programmeurs et qui ont besoin de se familiariser avec le C ++ moderne. Les personnes ayant une solide formation en mathématiques peuvent commencer par Découvrir le C ++ moderne: un cours intensif pour les scientifiques, les ingénieurs et les programmeurs Peter Gottschling.

Une fois que vous commencez à utiliser C ++ pour de vrai, vous aurez besoin d'un ensemble de directives pour faire la distinction entre ce qui peut être fait et ce qui est une bonne pratique. Pour cela, je recommande les directives de base C ++ sur GitHub.

Pour une bonne brève explication des caractéristiques et fonctions de chaque langue de la bibliothèque standard, je recommandewww.cppreference.com .

# 4. Quelles sont les différences entre une variable pointeur et une variable de référence en C ++?

Pour en savoir plus sur les liens et les pointeurs, consultez Learn C ++ .

Les deux sont représentés en mémoire comme une adresse machine. La différence réside dans leur utilisation.
Pour initialiser le pointeur, vous lui donnez l'adresse de l'objet:

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

Pour lire et écrire à travers un pointeur, nous utilisons l'opérateur de déréférence (*):

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

Lorsque nous attribuons un pointeur à un autre, ils pointeront tous deux vers le même objet:

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

Notez qu'un pointeur peut pointer vers différents objets au cours de son cycle de vie. C'est la principale différence avec les liens. Le lien est attaché à l'objet lors de sa création et ne peut pas être converti en lien vers un autre.

Pour les références, le déréférencement est implicite. Vous initialisez le lien avec l'objet et le lien obtient son adresse.

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

Le nouvel opérateur renvoie un pointeur, j'ai donc dû le déréférencer avant l'affectation, en l'utilisant pour initialiser le lien.

Pour lire et écrire via un lien, nous utilisons simplement le nom du lien (sans déréférencement explicite):

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

Lorsque nous attribuons un lien à un autre, la valeur spécifiée sera copiée:

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

Les références et les pointeurs sont souvent utilisés comme arguments d'une fonction:

void f(int* p)

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

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

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

Il peut y avoir un pointeur nullptr, nous devons donc vérifier s'il indique quelque chose. À propos du lien, vous pouvez initialement supposer qu'il fait référence à quelque chose.

# 5. Comment parcourir les mots chaîne?

Utilisez stringstream, mais comment définissez-vous un "mot"? Pensez: "Marie avait un petit agneau." Le dernier mot est «agneau» ou «agneau».? S'il n'y a pas de ponctuation, c'est facile:

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';

ou simplement:

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

Par défaut, l'opérateur >> saute les espaces. Si nous avons besoin d'ensembles de délimiteurs arbitraires, les choses deviennent un peu plus confuses:

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 est une opération indiquant si le caractère est un délimiteur, et je renvoie "" (chaîne vide) pour indiquer qu'il n'y a pas de mot à renvoyer.

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';

Si vous avez une bibliothèque de plages C ++ 20, vous n'avez pas besoin d'écrire quelque chose comme ça, mais vous pouvez utiliser split_view.

Bjarn Straustrup est partenaire technique et directeur général de Morgan Stanley New York et professeur invité à Columbia University. Il est également le créateur de C ++.

Pour plus d'informations sur C ++ 20, voir: isocpp.org .

C'est tout. Rendez-vous sur le parcours !

Björn Straustrup répond aux 5 meilleures questions C ++ avec débordement de pile

More articles: