Бьерн Страуструп отвечает на наши топ пять вопросов по C++

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

---

Мариэль Фрэнк и Сонни Ли, авторы курса 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.

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