Написать пост

Создатель C++ ответил на 5 самых популярных вопросов по C++ со Stack Overflow

Аватар Алексей Михайлишин

Почему отсортированный массив обрабатывается быстрее, чем не отсортированный? Что за оператор −−>? Есть ли исчерпывающий список книг по C++? Чем отличаются ссылки от указателей? Как пройтись по словам в строке? — Отвечает Бьёрн Страуструп.

Бьёрн Страуструп (дат. Bjarne Stroustrup) — технический сотрудник и управляющий директор Morgan Stanley в Нью-Йорке, профессор Колумбийского Университета и создатель C++.

Авторы курса 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    ");
}
		

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

Первая причина такого поведения лежит в механизме предсказания ветвлений (branch prediction): основная операция в алгоритме сортировки — сравнение if (v[i] < 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:

— Чем отличаются ссылки от указателей в С++?

Посмотреть этот вопрос на 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 вместо того, чтобы писать это всё самостоятельно.

Следите за новыми постами
Следите за новыми постами по любимым темам
16К открытий16К показов