Бьерн Страуструп отвечает на топ-5 вопросов по C++ со Stack Overflow

В преддверии старта курса «Разработчик С++» подготовили перевод интересного материала.

---

Мариэль Фрэнк и Сонни Ли, авторы курса Learn C++ на Codecademy, недавно получили возможность взять интервью у доктора Бьерна Страуструпа, создателя C++.

В рамках этого интервью он ответил на вопросы по C++, набравшие наибольшее количество голосов на Stack Overflow Хотя все интервью достойно полного прочтения, Codecademy великодушно разрешили нам поделиться его частью.

Если вы когда-нибудь задумывались, существуют ли на Stack Overflow определяюще исчерпывающие ответы, то вот нечто ближайшее к этому, что вы можете получить наверняка (хотя мы ожидаем, что кто-то может не согласиться).

Почему обработка отсортированного массива быстрее, чем обработка несортированного массива?

Примечание: Этот вопрос является номером 1, получившим наибольшее количество голосов на Stack Overflow за все время.

Звучит как вопрос с собеседования. Это правда? Как вы это узнали? Плохо отвечать на вопросы об эффективности, не проводя предварительных измерений, поэтому важно знать, как их измерять.
Итак, я проверял на векторе из миллиона целых чисел и получил:

Сортированный    32995 миллисекунд
Перемешанный          125944 миллисекунд

Сортированный     18610 миллисекунд
Перемешанный          133304 миллисекунд

Сортированный     17942 миллисекунд
Перемешанный          107858 миллисекунд

Я запускал это несколько раз для уверенности. Да, это явление реально. Мой основной код был:

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

По крайней мере, такое явление реально с этим компилятором, стандартной библиотекой и настройками оптимизатора. Разные реализации могут давать (и дают) разные ответы. Фактически, кто-то провел более систематическое исследование (быстрый поиск в Интернете поможет вам его найти), и большинство реализаций показывают этот эффект.

Одной из причин является предсказание ветвлений: ключевая операция в алгоритме сортировки — “if(v[i] < pivot]) …” или эквивалент. Для отсортированной последовательности этот тест всегда верен, тогда как для случайной последовательности выбранная ветвь изменяется случайным образом.

Другая причина заключается в том, что когда вектор уже отсортирован, нам никогда не нужно перемещать элементы в правильное положение. Эффект этих маленьких деталей дает коэффициент равный приблизительно пяти или шести, который мы наблюдали.

Quicksort (и сортировка в целом) — сложное исследование, которое привлекло некоторые из величайших умов информатики. Хорошая функция сортировки — это результат выбора хорошего алгоритма и внимания к производительности оборудования при его реализации.
Если вы хотите написать эффективный код, вам нужно принимать во внимание архитектуру машины.
———————————————————————————————
Простите за вмешательство. Просто напоминаем, что подкаст Stack Overflow возвращается! Заглядывайте к нам и услышите интервью с нашим новым генеральным директором.

Что такое оператор --> в C++?




Это старый вопрос с подвохом. В С ++ нет оператора -->. Рассмотрите следующее:

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

Это, конечно, выглядит так, как будто существует некий оператор --> и с подходящим объявлением p и m, вы даже сможете скомпилировать и запустить это:

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

Это фактически означает: посмотрите, больше ли p--, чем m (так оно и есть), а затем сравните результат (true) с 0. Что ж, true != 0, поэтому результат равен false и f() не вызывается. Другими словами:

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

Пожалуйста, не тратьте слишком много времени на такие вопросы. Они были популярны для сбивания с толку новичков еще до изобретения C++.

Лучшее руководство и список книг C++



К сожалению, нет канонического списка книг по C++. Такого в принципе не может быть. Не всем нужна одинаковая информация, не у всех одинаковый опыт, и лучшие практики C++ постоянно развиваются.

Я провел небольшое исследование в Интернете и нашел удивительный набор рекомендаций. Многие были серьезно устаревшими, а некоторые были просто плохими. Новичок, ищущий хорошую книгу без руководства, будет очень смущен!

Вам действительно нужна книга, потому что методы, которые делают C++ эффективным, нелегко найти в нескольких блогах по конкретным темам, и, конечно, блоги также страдают от ошибок, устаревания и плохих объяснений. Часто они также фокусируются на продвинутых новых темах и игнорируют основные принципы.

Я рекомендую свое Программирование: Принципы и Практика использования C++ (2-е издание) для людей, только начинающих учиться программировать, и Тур по C++ (2-е издание) для людей, которые уже являются программистами и которым необходимо ознакомиться с современным C++. Люди с сильным математическим образованием могут начать с Открытия современного C++: интенсивный курс для ученых, инженеров и программистов Питера Готшлинга.

Как только вы начнете использовать C++ по-настоящему, вам потребуется набор руководящих принципов, чтобы различать, что можно сделать, и что является хорошей практикой. Для этого я рекомендую C++ Core Guidelines на GitHub.

Для хороших кратких объяснений отдельных языковых особенностей и функций стандартной библиотеки я рекомендую www.cppreference.com.

#4. Каковы различия между переменной-указателем и ссылочной переменной в C++?



Чтобы узнать больше о ссылках и указателях, ознакомьтесь с Learn C++.

Обе представлены в памяти как машинный адрес. Разница в их использовании.
Чтобы инициализировать указатель, вы даете ему адрес объекта:

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

Для чтения и записи через указатель мы используем оператор разыменования (*):

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

Когда мы присваиваем один указатель другому, они оба будут указывать на один и тот же объект:

p1 = p2;       // теперь p1 и p2 оба указывают на int со значением 9
*p2 = 99;      // записываем 99 через p2
int z = *p1;   // считываем через p1, z становится 99 (а не 9)

Обратите внимание, что указатель может указывать на разные объекты в течение своего жизненного цикла. Это основное отличие от ссылок. Ссылка привязывается к объекту при его создании и не может быть переделана в ссылку на другой.

Для ссылок разыменование является неявным. Вы инициализируете ссылку с объектом, и ссылка получает его адрес.

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

Оператор new возвращает указатель, поэтому мне пришлось разыменовать его перед назначением, используя его для инициализации ссылки.

Для чтения и записи через ссылку мы просто используем имя ссылки (без явной разыменования):

r1 = 9;        // записываем через r1
int y = r2;    // считываем через r2

Когда мы присваиваем одну ссылку другой, указанное значение будет скопировано:

r1 = r2;       // теперь p1 и p2 обе имеют одинаковое значение 9
r1 = 99;       // записываем 99 через r1
int z = r2;    // считываем через r2, z становится 9 (а не 99)

И ссылки, и указатели часто используются в качестве аргументов функции:

void f(int* p)

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

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

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

Указатель может быть nullptr, поэтому мы должны проверять, указывает ли он на что-либо. Про ссылку можно изначально предположить, что она ссылается на что-то.

#5. Как итерировать по словам строки?




Используйте stringstream, но как вы определяете «слово»? Подумайте: «У Мэри был маленький ягненок.». Последнее слово «ягненок» или «ягненок.»? Если пунктуации нет, это легко:

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

или просто:

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

По умолчанию оператор >> пропускает пробелы. Если нам нужны произвольные наборы разделителей, все становится немного более запутанным:

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 — это операция, сообщающая, является ли символ разделителем, и я возвращаю "" (пустую строку), чтобы указать, что не было слова для возврата.

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

Если у вас есть библиотека C++20 Range, вам не нужно писать что-то подобное, но вы можете использовать split_view.

Бьярн Страуструп — технический партнер и управляющий директор Morgan Stanley в Нью-Йорке и приглашенный профессор Колумбийского Университета. Он также является создателем C++.

Для получения дополнительной информации о C++20 смотрите: isocpp.org.

На этом все. До встречи на курсе!