Бьёрн Страуструп (дат. Bjarne Stroustrup) — технический сотрудник и управляющий директор Morgan Stanley в Нью-Йорке, профессор Колумбийского Университета и создатель C++.
Авторы курса Learn C++ из Codecademy взяли у Страуструпа интервью. В отдельном материале можно почитать его рассуждения про значимость языка и советы всем начинающим программистам. А здесь мы перевели его ответы на 5 самых популярных вопросов по C++ за всё время.
— Очень похоже на вопрос с собеседования. Это и правда так? Как это можно проверить? Отвечать на вопрос про производительность, не проведя перед этим измерения — плохая идея, так что нам важно понять, как проводить эти измерения.
Итак, я проверил сортировку массива миллиона целых чисел:
Already sorted 32995 milliseconds
Shuffled 125944 milliseconds
Already sorted 18610 milliseconds
Shuffled 133304 milliseconds
Already sorted 17942 milliseconds
Shuffled 107858 milliseconds
Прим. перев. В оригинальном вопросе автор находил сумму элементов массива и на отсортированных данных это получалось почти в 10 раз быстрее. Страуструп вместо сложения взял ещё одну сортировку и проверил, что быстрее отсортируется: уже упорядоченный массив или рандомный. Звучит глупо, но на самом деле ответ универсальный и применим к любым операциям с массивами. Если данные упорядочены, то работать, скорее всего, будет быстрее.
Я запустил код несколько раз, чтобы убедиться. Действительно, то, о чём говорится в вопросе — правда. Я использовал следующий код:
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 ");
}
По крайней мере это правда для моего компилятора, стандартной библиотеки С++ и моих настроек оптимизатора. Разные реализации могут привести и приведут к разным результатам. Есть исследование на эту тему (должно легко гуглиться), и в большинстве реализаций компилятора С++ будет наблюдаться такой же эффект.
https://tproger.ru/jobs/udaljonnyj-razrabotchik-s/?utm_source=in_text
Первая причина такого поведения лежит в механизме предсказания ветвлений (branch prediction): основная операция в алгоритме сортировки — сравнение if (v < pivot]) ... или его эквивалент. Для упорядоченной последовательности это сравнение будет всегда истинно, тогда как в рандомном массиве выбор ветки будет случайным.
Другая причина в том, что если массив уже упорядочен, нам не нужно перемещать элементы на правильные позиции. Из-за этих небольших деталей мы и получаем разницу во времени в 5 или 6 раз.
Алгоритм быстрой сортировки (да и алгоритмы сортировки вообще) — это целое исследование, которым занимались величайшие умы computer science. Хорошая функция для сортировки подразумевает как выбор правильного алгоритма, так и учёт особенностей реализации железа.
Если вы хотите писать эффективный код, вам нужно хотя бы немного знать об архитектуре компьютеров.
— Это старый хитрый вопрос. В С++ нет оператора −−>.
Рассмотрим такой код:
if (p−−>m == 0) f(p);
Выглядит так, как будто и правда есть оператор −−>, и если правильно объявить переменные p и m, то код даже скомпилируется и запустится:
int p = 2;
int m = 0;
if (p−−>m == 0) f(p);
Это означает: если p−− больше чем m (а это так), то надо сравнить результат (true) с нулём. Ну, true != 0, так что результат всего выражения — false, и функция f() не вызовется. Другими словами:
if ((p−−) > m == 0) f(p);
Пожалуйста, не тратьте много времени на подобные вопросы. Они сбивали с толку новичков ещё до того, как появился С++.
— К сожалению, такого списка нет. И не может быть. Разным людям нужна разная информация, у них разный бэкграунд, а сам язык С++ постоянно развивается.
Я поискал в интернете — там целый набор подобных списков, это сбивает столку. Одни серьёзно устарели, другие изначально плохи. Беспомощный новичок запутается в поисках хорошей книги.
Вам и правда нужна именно книга для изучения С++, потому что техники, которые делают этот язык эффективным, не очень-то легко почерпнуть из отдельных заметок в блогах. И, конечно, информация там бывает ошибочной, устаревшей, с плохим объяснением. Кроме того, там часто фокусируются на продвинутом материале о нововведениях и пропускают необходимые основы.
Рекомендую мою книгу «Программирование. Принципы и практика с использованием C++» для тех, кто только начинает изучать программирование, и «A Tour of C++» для тех, кто уже программирует и хочет больше узнать о современном С++. Люди с хорошей математической базой могут начать с книги Питера Готтшлинга «Современный C++. Для программистов, инженеров и ученых».
Когда вы начнёте использовать C++ по-настоящему, вам понадобится набор правил, чтобы научиться лучшим практикам. Для этого на гитхабе есть C++ Core Guidelines.
За короткими ёмкими объяснениями отдельных особенностей языка и функций стандартной библиотеки рекомендую идти на сайт cppreference.
***
Бьёрн Страуструп: не существует исчерпывающего списка книг по C++, это бред.
Тем временем редакторы Tproger:
https://tproger.ru/books/cpp-books-beginners/
— И ссылка, и указатель хранят в памяти машинный адрес. Разница в том, как они используются.
Чтобы инициализировать указатель, вы даёте ему адрес объекта:
int x = 7;
int* p1 = &x;
int* p2 = new int{9};
Чтобы считывать и записывать значение через указатель, надо использовать оператор разыменования (*):
*p1 = 9; // записать 9 по указателю p1
int y = *p2; // считать значение по указателю p2
Если присвоить одному указателю другой, они оба будут указывать на один и тот же объект:
p1 = p2; // теперь p1 и p2 указывают на то же самое целое число 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; // теперь r1 и r2 содержат одно и то же значение 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, так что нам нужно следить за тем, чтобы он в принципе на что-то указывал. А ссылка всегда относится к какому-то объекту.
Надо использовать stringstream. Но как определить, что такое «слово»? Скажем, в предложении «Я устал переводить эту статью.» последнее слово «статью» или «статью.»?
Прим. перев. Перевели строки в коде на кириллицу, компилируется на C++14 (clang 8.0).
Если пунктуации нет вообще, то всё просто:
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("вот вам очень простой пример"); // пять слов
for (auto& w : words) cout << w << '\n';
Или даже так:
for (auto& w : split("вот вам очень простой пример")) 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("Ты дочитал до конца статьи; молодец! ", "!.,;? ");
for (auto& w : words) cout << w << '\n';
Если у вас есть библиотека Range из C++20, можете использовать split_view вместо того, чтобы писать это всё самостоятельно.
Источник статьи: https://tproger.ru/translations/answers-to-most-popular-questions-cpp/
Авторы курса Learn C++ из Codecademy взяли у Страуструпа интервью. В отдельном материале можно почитать его рассуждения про значимость языка и советы всем начинающим программистам. А здесь мы перевели его ответы на 5 самых популярных вопросов по C++ за всё время.
— Почему отсортированный массив обрабатывается быстрее, чем не отсортированный?
Посмотреть этот вопрос на Stack Overflow, на русском Stack Overflow— Очень похоже на вопрос с собеседования. Это и правда так? Как это можно проверить? Отвечать на вопрос про производительность, не проведя перед этим измерения — плохая идея, так что нам важно понять, как проводить эти измерения.
Итак, я проверил сортировку массива миллиона целых чисел:
Already sorted 32995 milliseconds
Shuffled 125944 milliseconds
Already sorted 18610 milliseconds
Shuffled 133304 milliseconds
Already sorted 17942 milliseconds
Shuffled 107858 milliseconds
Прим. перев. В оригинальном вопросе автор находил сумму элементов массива и на отсортированных данных это получалось почти в 10 раз быстрее. Страуструп вместо сложения взял ещё одну сортировку и проверил, что быстрее отсортируется: уже упорядоченный массив или рандомный. Звучит глупо, но на самом деле ответ универсальный и применим к любым операциям с массивами. Если данные упорядочены, то работать, скорее всего, будет быстрее.
Я запустил код несколько раз, чтобы убедиться. Действительно, то, о чём говорится в вопросе — правда. Я использовал следующий код:
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 ");
}
По крайней мере это правда для моего компилятора, стандартной библиотеки С++ и моих настроек оптимизатора. Разные реализации могут привести и приведут к разным результатам. Есть исследование на эту тему (должно легко гуглиться), и в большинстве реализаций компилятора С++ будет наблюдаться такой же эффект.
https://tproger.ru/jobs/udaljonnyj-razrabotchik-s/?utm_source=in_text
Первая причина такого поведения лежит в механизме предсказания ветвлений (branch prediction): основная операция в алгоритме сортировки — сравнение if (v < pivot]) ... или его эквивалент. Для упорядоченной последовательности это сравнение будет всегда истинно, тогда как в рандомном массиве выбор ветки будет случайным.
Другая причина в том, что если массив уже упорядочен, нам не нужно перемещать элементы на правильные позиции. Из-за этих небольших деталей мы и получаем разницу во времени в 5 или 6 раз.
Алгоритм быстрой сортировки (да и алгоритмы сортировки вообще) — это целое исследование, которым занимались величайшие умы computer science. Хорошая функция для сортировки подразумевает как выбор правильного алгоритма, так и учёт особенностей реализации железа.
Если вы хотите писать эффективный код, вам нужно хотя бы немного знать об архитектуре компьютеров.
— Что за оператор −−> в С++?
Посмотреть этот вопрос на Stack Overflow, на русском Stack Overflow— Это старый хитрый вопрос. В С++ нет оператора −−>.
Рассмотрим такой код:
if (p−−>m == 0) f(p);
Выглядит так, как будто и правда есть оператор −−>, и если правильно объявить переменные p и m, то код даже скомпилируется и запустится:
int p = 2;
int m = 0;
if (p−−>m == 0) f(p);
Это означает: если p−− больше чем m (а это так), то надо сравнить результат (true) с нулём. Ну, true != 0, так что результат всего выражения — false, и функция f() не вызовется. Другими словами:
if ((p−−) > m == 0) f(p);
Пожалуйста, не тратьте много времени на подобные вопросы. Они сбивали с толку новичков ещё до того, как появился С++.
— Исчерпывающий список книг по С++
Посмотреть этот вопрос на Stack Overflow, на русском Stack Overflow— К сожалению, такого списка нет. И не может быть. Разным людям нужна разная информация, у них разный бэкграунд, а сам язык С++ постоянно развивается.
Я поискал в интернете — там целый набор подобных списков, это сбивает столку. Одни серьёзно устарели, другие изначально плохи. Беспомощный новичок запутается в поисках хорошей книги.
Вам и правда нужна именно книга для изучения С++, потому что техники, которые делают этот язык эффективным, не очень-то легко почерпнуть из отдельных заметок в блогах. И, конечно, информация там бывает ошибочной, устаревшей, с плохим объяснением. Кроме того, там часто фокусируются на продвинутом материале о нововведениях и пропускают необходимые основы.
Рекомендую мою книгу «Программирование. Принципы и практика с использованием C++» для тех, кто только начинает изучать программирование, и «A Tour of C++» для тех, кто уже программирует и хочет больше узнать о современном С++. Люди с хорошей математической базой могут начать с книги Питера Готтшлинга «Современный C++. Для программистов, инженеров и ученых».
Когда вы начнёте использовать C++ по-настоящему, вам понадобится набор правил, чтобы научиться лучшим практикам. Для этого на гитхабе есть C++ Core Guidelines.
За короткими ёмкими объяснениями отдельных особенностей языка и функций стандартной библиотеки рекомендую идти на сайт cppreference.
***
Бьёрн Страуструп: не существует исчерпывающего списка книг по C++, это бред.
Тем временем редакторы Tproger:
https://tproger.ru/books/cpp-books-beginners/
— Чем отличаются ссылки от указателей в С++?
Посмотреть этот вопрос на Stack Overflow, на русском Stack Overflow— И ссылка, и указатель хранят в памяти машинный адрес. Разница в том, как они используются.
Чтобы инициализировать указатель, вы даёте ему адрес объекта:
int x = 7;
int* p1 = &x;
int* p2 = new int{9};
Чтобы считывать и записывать значение через указатель, надо использовать оператор разыменования (*):
*p1 = 9; // записать 9 по указателю p1
int y = *p2; // считать значение по указателю p2
Если присвоить одному указателю другой, они оба будут указывать на один и тот же объект:
p1 = p2; // теперь p1 и p2 указывают на то же самое целое число 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; // теперь r1 и r2 содержат одно и то же значение 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, так что нам нужно следить за тем, чтобы он в принципе на что-то указывал. А ссылка всегда относится к какому-то объекту.
— Как пройтись по словам в строке С++?
Посмотреть этот вопрос на Stack Overflow, на русском Stack Overflow прямого аналога не нашлиНадо использовать stringstream. Но как определить, что такое «слово»? Скажем, в предложении «Я устал переводить эту статью.» последнее слово «статью» или «статью.»?
Прим. перев. Перевели строки в коде на кириллицу, компилируется на C++14 (clang 8.0).
Если пунктуации нет вообще, то всё просто:
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("вот вам очень простой пример"); // пять слов
for (auto& w : words) cout << w << '\n';
Или даже так:
for (auto& w : split("вот вам очень простой пример")) 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("Ты дочитал до конца статьи; молодец! ", "!.,;? ");
for (auto& w : words) cout << w << '\n';
Если у вас есть библиотека Range из C++20, можете использовать split_view вместо того, чтобы писать это всё самостоятельно.
Источник статьи: https://tproger.ru/translations/answers-to-most-popular-questions-cpp/