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

Как известно, на данный момент официальным стандартом С++ является ISO/IEC 14882:2011, или же, проще говоря, С++11. Поддерживается он не на всех серверах, но со временем, думаю, ситуация изменится. Codeforces, например, идет в ногу со временем. C++0x, доступный здесь, фактически ничем от С++11 не отличается, просто другое наименование ("рабочее" название в ходе работы над будущим стандартом на самом деле). По крайней мере, начиная с GCC 4.7, установленного здесь, это так. Сразу скажу, что я буду опираться на GCC, ибо в Visual C++ практически все новые фичи появляются только в 10 и, в основном, 11 версии, которые не шибко то распространены.

Тем не менее, если просмотреть многие посылки на КФ, то заметно, что мало кто пользуется нововведениями. Это вполне естественно, учитывая, что спортивное программирование — это, прежде всего, математика да алгоритмы. Знание языка же роли большой не играет. Имея циклы, массивы и if, можно решить любую олимпиадную задачу. Если, конечно, это не Python, ибо только Иисус поможет вам запихнуть задачу на нем в строгий TL. Однако же, хорошее знание языка может сэкономить кучу времени при написании решения (один из основных аргументов тех же питонщиков), да и в будущем пригодится.

Опираясь на свой достаточно богатый опыт участия в олимпиадах, я собрал здесь нововведения С++11, которые могут пригодиться в спортивном программировании, например, непосредственно здесь, на Codeforces. Нововведений этих очень много, но я постарался выбрать лишь то, что может быть интересно олимпиаднику, не более. Например, я не буду описывать следующее:
- Расширение механизма шаблонов. Variadic templates, например, и вытекающий из этого класс Tuple.
- Все, что касается ООП.
- Объединения, перечисления со строгой типизацией.
- "Умные" указатели.
- Определяемые пользователем строковые литералы.
- constexpr (хотя рекомендую все же почитать про это)
Ну и многое другое... Достаточно подробный список с краткими описаниями можно найти на википедии.
Помимо кратких характеристик, для новых структур данных я также провел замеры времени работы. Там, где это нужно, также приводятся ссылки на подробные описания. Мне было лень в примерах писать префикс std, но я думаю понятно, что он неявно подразумевается. Начнем с новых фич самого языка, а потом уже перейдем к стандартной библиотеке.

1. Rvalue references и move constructors

Предположим, что вы написали класс длинной арифметики Lint и определили, например, оператор +, возвращающий Lint в качестве результата. Пусть a,b и C — объекты типа Lint. А теперь представьте, что вы пишете: C = a + b. "Holy Shit!" — воскликнет компилятор, и не зря, ведь здесь 2 раза происходит копирование длинного числа. Первый раз — при конструировании временного объекта, который будет использоваться в качестве возврата из функции. Второй раз — при присваивании этого результата C. И если первое копирование, скорее всего, компилятор при оптимизации уберет, то вот со вторым ничего он поделать не сможет. А если эту конструкцию вы используете в цикле, а числа достаточно длинные, то это просто беда. Временный же объект получается никому не нужным, его содержимое скопируется, а для объекта вслед за этим вызовется деструктор. Идея в том, что было бы круто просто перекинуть для С указатели на этот временный объект, ведь к этому временному объекту никогда больше не будет обращений, а значит его смело можно использовать "через" C. Раньше так делать было нельзя, потому что C++ не мог различать ссылки на временные объекты и на остальные. Теперь же введены так называемые Rvalue references, обозначемые, как &&. Ну и соответствующие виды конструкторов, называемые move constructors. И да, все стандартные контейнеры обзавелись такими конструкторами, поэтому можно смело возвращать какой-нибудь vector из функции и чему-то присваивать.
Подробное и понятное описание с примерами можно найти здесь: ссылка.

2. Лямбда — функции

Очень крутая штука. Наконец можно написать краткую функцию непосредственно там, где она нужна, и не думать над тем, как дать ей очередное никчемное имя (а потом еще и вспоминать его). Что не может не радовать, так это достаточно удобный синтаксис и широкие возможности. Вот, например, как можно отсортировать массив строк по индексу первого вхождения в некоторую строку s:
sort(a,a+n,[&s] (const string& x,const string& y) {return s.find(x)<s.find(y);});
Можно использовать и переменные, доступные в текущей области видимости. Причем можно захватывать их как посредством копирования, так и с помощью ссылок. Например, в примере выше s передается по ссылке. Лямбда-функции столь же эффективны, что и обычные функции или функторы. Если захвата внешних переменных не происходит, то компилятор создает простую встраиваемую функцию, в противном случае создается класс с вашей лямбда-функцией в качестве операции () и захваченными переменными в качестве членов этого класса (т.е. фактически функтор). Вот отличное описание лямбда-функций: ссылка.

3. Range-based for loops

Сразу приведу простой код (v это list <int>):

for(int i: v)
  cout<<i<<" ";
cout<<"\n";
for(auto it=v.begin();it!=v.end();++it) //об этом в следующем пункте
  cout<<(*it)<<" ";

Первая часть примера демонстрирует новый вид цикла for для удобного итерирования по стандартным контейнерам (в данном случае выводится содержимое), типа string, vector, list и т.д.. В общем случае, чтобы иметь возможность таким образом бегать по всяким неведомым структурам, необходимо следующее:
- Определить методы (или функции, принимающие в качестве аргумента контейнер) begin() и end(), которые возвращают итератор на соответственно начало контейнера и на элемент, следующий за последним.
- Для самого итератора перегрузить операторы * (разыменование), != и префиксный ++.
Разумеется, все контейнеры с итераторами стандартной библиотеки предоставляют такую возможность. Также можно "бегать" с помощью ссылки, чтобы модифицировать содержимое контейнера. Подробнее тут: ссылка. Следует отметить, что for_each из algorithm в сочетании с лямбда-функциями предоставляет куда бОльшую функциональность.

4. auto и decltype

Вам тоже надоело каждый раз писать, что-то вроде set <int>::iterator it=s.lower_bound(x)? С++11 позволяет наконец убрать эти страшные конструкции. Вторая часть предыдущего примера демонстрирует использование auto: компилятор сам определит тип it. (Для использования const_iterator стандартные контейнеры теперь предоставляют также методы cbegin() и cend()). Думаю, не стоит говорить, насколько это порою удобно. Разумеется, чтобы это работало, необходимо предоставить компилятору определение переменной, иначе говоря auto x; компилироваться не будет. decltype это почти то же:

int some_function() {...}
...
decltype(some_function()) x;

Здесь x имеет тот же тип, что и возврат some_function(), т.е. int. decltype обозначает "того же типа, что и аргумент". И это совсем необязательно функция. Подробнее можно почитать здесь: ссылка.

5. Списки инициализации

Вернулись из старого доброго С. Да, они были доступны и в С++, но теперь это полноценный класс. Более того, в С++ нельзя инициализировать списком класс, для которого определен хоть какой-нибудь конструктор. Теперь же можно определить специальный конструктор, принимающий initializer_list в качестве параметра. Вот простой пример:

class Array
{
    int a[100],sz;
public:
    Array(initializer_list <int> b)
    {
        sz=0;
        for(auto it=b.begin();it!=b.end();it++)
            a[sz++]=*it;
    }
};
...
Array a={1,2,3,4};

Как я уже упомянул, теперь это полноценный шаблонный тип, предоставляющий собственный конструктор, итераторы на begin() и end() и классический метод size(). Причем все за константное время (в том числе и создание объекта). Находится в пространстве имен std в заголовочном файле initializer_list. Его также можно передавать в функции. Очевидное применение — удобная инициализация вектора, например vector <int> b={1,2,3,4};. Такие же конструкторы предоставляются и для остальных стандартных контейнеров. Забыл упомянуть, что такой конструктор имеет приоритет над остальными, т.е. если у вас есть конструктор, например, от int, то, написав Array a{4}, вы вызовете тот, который списочный. Несмотря на то, что объект типа initializer_list может содержать только константные объекты (и сам изменяться не может) одного типа, возможность инициализации в С-стиле сохраняется:

struct pt
{
    int x;
    double y;
};
...
pt a={1,2.0};

В данном примере, класс initializer_list не используется. Это классический список инициализации. Ссылка на соответствующий класс.

6. Новые функции

Появление некоторых вызвано тем, что long long int отныне официально поддерживается С++. Например, появились atoll, аналог atoi, только возвращающая long long, llabs (не в cmath!) и так далее...
Контейнер map обзавелся методом at, который ведет себя аналогично find, но, не найдя ключ, генерирует исключение. Это может быть удобным при дебаге.
Функция is_sorted с синтаксисом, аналогичным sort, проверяет, отсортирована ли заданная последовательность. Мелочь, а приятно.
Функция iota заполняет заданную последовательность арифметической прогрессией с шагом 1.
Функция max (как и min) теперь может принимать список инициализации в качестве аргумента. Наконец-то это случилось.
Кое-что и убрано. Макроса M_PI в cmath больше нет. Спецификатор lf в printf отныне не поддерживается. Однако, спецификатор f отлично справляется с выводом double.

7. Random

С рандомом вообще вышло довольно забавно. Вспомним, как обстояло дело раньше. Еще со времен С была единственная функция rand(), возвращавшая обычно 15-битовое целое (используется линейный конгруэнтный метод, а в качестве возврата 15 старших бит), а также единственная функция srand() для инициализации генератора. Поскольку 32767 – это максимум из того, что может выдать rand(), а числа обычно нужны намного больше, то появились велосипедные генераторы а-ля rand()^(rand()<<15). Если же нужно случайное число, меньшее N, то к велосипеду прикручивалось третье колесо в виде взятия по модулю N. Получается замечательный генератор, работающий в 3 раза дольше обычного. Если же это не олимпиадная задача, а серьезный проект, то дело заканчивалось либо копипастой хорошего генератора с википедии, либо скачиванием Boost и ему подобного.

То ли дело теперь: разработчики запилили туеву хучу генераторов и видов распределений. Стало очень похоже на вышеупомянутый Boost, кстати. Другое дело, что, как я подозреваю, мало кто будет всем этим пользоваться. Мне, например, немного лень разбираться в бесчисленных параметрах, да и вообще random вышел немного запутанным на мой взгляд. Но если вкратце, то:

• Есть несколько основных генераторов, а также множество их специализаций (64-битные, например). Из основных я бы отметил линейный, вихрь Мерсенна и недетерминированный random_device, использующий (не знаю, откуда он их берет) стохастические процессы. Последний работает не всегда. Если система не может предоставить подобный генератор, то генерируется исключение, что у меня на винде и происходит.
• Ну и собственно распределения. Наконец можно и вещественные числа генерировать нормально.

Ну и парочка примеров. Используем линейный генератор:

minstd_rand gen(chrono::system_clock::now().time_since_epoch().count());
uniform_int_distribution <int> dist(1,1e6);
cout<<dist(gen);

Это выведет случайное целое от 1 до 1e6. Здесь заодно видно, что появился новый заголовочный файл для работы со временем: chrono. Но можно использовать и уже известный time(0).
А вот так можно генерировать целое от 0 до 1e16 с помощью вихря Мерсенна:

mt19937_64 gen(chrono::system_clock::now().time_since_epoch().count());
uniform_int_distribution <long long> dist(0,1e16);
cout<<dist(gen);

Разумеется, привожу ссылку на полное описание всех возможностей: random.

8. Regex

Настоящая беда. Очередное доказательство того, что регулярные выражения плохо приживаются в языках вроде С++. Вообще, regex — это шаблон с великим множеством различных специализаций. Вряд ли пригодится вам на олимпиадах, а если уж и нужны регулярки, то проще сделать это на Python. Но для интересующихся: добро пожаловать. Также появились так называемые "сырые" строковые литералы (raw string literal). Питонщики прекрасно знают, что это. Внутри них не нужно экранировать специальные символы, например printf(R"(I just want to print \n)"); выведет I just want to print \n. Хотя, кроме как в регулярных выражениях, вряд ли это нужно где-то еще.

9. forward_list
Не прошло и 10 лет, как в С++ появился обыкновенный односвязный список. Используется практически так же, как и list, за тем исключением, что теперь нет по понятным причинам reverse_iterator. Также нет методов push_back и pop_back. Подробнее можно почитать здесь: forward_list. И да, вот результаты некоторых моих тестирований этого контейнера:

Как показывает практика, forward_list не сильно отличается в плане эффективности от двусвязного list, как в скорости, так и в объеме потребляемой памяти. Вначале производилось N push_front'ов, а затем N раз рандомно либо push_front, либо pop_front (указывается время работы/объем памяти в мегабайтах):

    N       list     forward_list
  10^6  | 0.194/24  | 0.183/16  |
  10^7  | 1.777/236 | 1.754/158 |

Хотя некоторый выигрыш в памяти все же есть. Когда списков много, разница тоже не очень большая. Например, при использовании списков в хеш-таблицах. Я использовал 500009 списков для хранения 2e6 интов. Результаты следующие:

  forward_list:  1.361/42
  list:          1.561/62

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

10. unordered_map/unordered_set

Аналоги map и set, реализованные посредством хеш-таблиц, поэтому ожидаемое время доступа — O(1). На практике же все намного хуже. Я, конечно, понимаю, что нельзя так просто взять и написать эффективную динамическую хеш-таблицу (кстати, коллизии здесь разрешаются методом цепочек), но тот факт, что эти контейнеры работают почти так же, как и обычные, а иногда и медленнее(!), огорчает. Причем не помогает даже ручное выставление количества вставляемых элементов (reserve) и количества используемых корзин (rehash). Возможно, стоит поиграться с load_factor или же предоставлять свою функцию хеширования. Но проще уже тогда написать свою таблицу, благо писать строчек 30. На всякий случай: ссылка на подробное описание. Я сравнил производительность map, unordered_map и своей хеш-таблицы (на forward_list'ах, 300007 корзин) при работе с int, а также с std::string. Тестирование set/unordered_set, как мне кажется, бессмысленно, т.к. они в стандартной библиотеке реализованы точно так же, как и их map-аналоги.

Вначале производится вставка 10^6 интов, потом 10^6 раз вызывается find рандомно — либо ищется случайный ранее вставленный ключ, либо просто случайный ключ.

unordered_map:  1.585/37
map:            1.330/36
мой вариант:    0.618/29

А вот аналогичный тест для строк длиной в 10 символов:

unordered_map:  2.512/96
map:            2.924/99
мой вариант:    1.653/92

Со строками unordered_map справляется все же лучше, чем map, но не намного. Возможно, к выходу С++14 unordered-контейнеры будут улучшены, но я в этом сильно сомневаюсь...

В С++11 на данный момент есть практически все синтаксические средства и средства стандартной библиотеки, предоставляемые каким-нибудь питоном (кроме длинки :)), только раз в десять более эффективные. Для спортивного программирования большего и не нужно. Конечно же, обновления не ограничиваются тем, что я изложил выше. Возможно, я добавлю еще что-нибудь. Но, по-моему, этого пока достаточно. Если же я упустил что-то важное или где-то ошибся, буду рад увидеть соответствующий комментарий. Я упоминал питон с не очень хорошей стороны в тексте, но это не значит, что язык плохой. Просто мне непонятно то чрезмерное внимание, которое уделяется ему в олимпиадном программировании (Не знаю, как в промышленном. Но даже если там это так, то скорее всего это оправдано). Поэтому можете воспринимать эту статью как своего рода "рекламу" С++11.