Блог пользователя Igorjan94

Автор Igorjan94, история, 7 лет назад, перевод, По-русски

C++17 уже доступен на codeforces, сообщество хочет новую версию C++ tricks, которую написал HosseinYousefi, так что, начнем!
Disclaimer: Я сделал всего лишь немного примеров новых фич, которые по моему мнению относятся к спортивному программированию. Если у Вас есть примеры лучше или Вам что-то непонятно, или нужно больше объяснений каких-то фич  —  пишите в комментах)

Fold expressions (Свертки)

  • Я думаю все знают, что такое reduce и свертка, но все-таки приведу пример из c++11:
vector<int> v = {1, 3, 5, 7};
int res = accumulate(v.begin(), v.end(), 0, [](int a, int b) { return a + b; });
cout << res; // 16
  • Начиная с C++17 есть поддержка свертки для шаблонного списка со следующим синтаксисом:
(pack op ...)
(... op pack)
(pack op ... op init)
(init op ... op pack)
  • Для примера напишем функцию, которая принимает переменное число аргументов и считает их сумму. До С++17 мы не могли этого сделать без явной передачи первого аргумента:
//C++14
auto Sum()
{
    return 0;
}

template<typename Arg, typename... Args>
auto Sum(Arg first, Args... rest)
{
    return first + Sum(rest...);
}

cout << Sum(1, 2, 3, 4, 5); // 15
//C++17
template<typename... Args>
auto Func(Args... args)
{
    return (args + ...);
}

cout << Func(1, 2, 3, 4, 5); // 15
  • Это особенно полезно, когда мы в качестве op используем запятую:
// C++17
template<typename T, typename... Args>
void pushToVector(vector<T>& v, Args&&... args)
{
    (v.push_back(forward<Args>(args)), ...);
    //Этот код раскрывается в последовательность выражений через запятую:
    //  v.push_back(forward<Args_1>(arg1)),
    //  v.push_back(forward<Args_2>(arg2)),
    //  ....
}

vector<int> v;
pushToVector(v, 1, 4, 5, 8);
  • И мой любимый пример:
//C++17
template<typename... Args>
void readln(Args&... args)
{
    ((cin >> args), ...);
}

template<typename... Args>
void writeln(Args... args)
{
    ((cout << args << " "), ...);
}

int x;
double y;
readln(x, y); // enter 100 500.1234
writeln(x, "some string", y); // 100 some string 500.1234
  • Note: скобки значимы!

Class template argument deduction (Вывод шаблонных типов)

template<typename T>
struct point
{
    T x;
    T y;
    point(T x, T y) : x(x), y(y) {}
};

//C++11
pair<int, double> p1 = {14, 17.0}
point<int> u = {1, 2};

//C++17
pair p2 = {14, 17.0}
point v = {1, 2};

Если структура сложная, то есть возможность указать правило вывода самим, например так:

template<typename T, typename U>
struct S
{
    T first;
    U second;
};

// Мой вывод типа
template<typename T, typename U>
S(const T &first, const U &second) -> S<T, U>;

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

*this capture in lambda expressions (Захват *this в лямбда-функциях)

Я не думаю, что это особо полезно в спортивном программировании, но кто знает:

struct someClass
{
    int x = 0;

    void f() const
    {
        cout << x << '\n';
    }

    void g()
    {
        x++;
    }

    // C++14
    void func()
    {
        auto lambda1 = [self = *this]() { self.f(); };
        auto lambda2 = [self = *this]() mutable { self.g(); };
        lambda1();
        lambda2();
    }

    // C++17
    void funcNew()
    {
        auto lambda1 = [*this]() { f(); };
        auto lambda2 = [*this]() mutable { g(); };
        lambda1();
        lambda2();
    }
};

Статья о ключевом слове mutable.

Structured bindings (Структурные связывания?)

  • Самое полезное нововведение  —  синтаксический сахар для декомпозиции объектов.
template<typename T>
struct point
{
    T x;
    T y;
    point(T x, T y) : x(x), y(y) {}
};

vector<point<int>> points = {{0, 0}, {1, 0}, {1, 1}, {1, 0}};
//C++11
for (auto& point : points)
{
    int x, y;
    tie(x, y) = point;
    //...Какая-то сложная логика с x и y
}

//C++17
for (auto& [x, y] : points)
{
    //...Какая-то сложная логика с x и y
}
  • Итерирование по map'у:
map<int, string> m;
for (auto [key, value] : m)
    cout << "key: " << key << '\n' << "value: " << value << '\n';
  • Хорошим примером использования может служить задача 938D - Покупка билетов. Код со структурным связыванием (Алгоритм Дейкстры) становится намного понятнее и читаемее: сравните 35474147 и 35346635.
while (!q.empty())
{
    auto [dist, u] = *q.begin();
    q.erase(q.begin());
    used[u] = true;
    for (auto& [w, v] : g[u])
        if (!used[v] && d[v] > dist + 2 * w)
            q.erase({d[v], v}),
            d[v] = dist + 2 * w,
            q.insert({d[v], v});
}

Инициализатор в if и switch

set<int> s;

if (auto [iter, ok] = s.insert(42); ok)
{
    //...
}
else
{
    //`ok` и `iter` доступны в этой области видимости
}
//А здесь недоступны

Новые атрибуты

  • [[fallthrough]] атрибут сообщает о том, что break в данном месте пропущен намеренно:
int requests, type;
cin >> requests;
for (int q = 0; q < requests; ++q)
    switch (cin >> type; type) //Используем инициализатор в switch
    {
        case 1:
            int l, r;
            cin >> l >> r;
            //Обработаем запрос первого типа
            break;
        case 2:
            [[fallthrough]];
            //Предупреждение компилятора будет подавлено!
        case 3:
            int value;
            cin >> value;
            //Обработаем запрос второго и третьего типа.
    }
  • [[nodiscard]] атрибут используется, чтобы показать, что возвращаемое значение функции не может быть отброшено. Может использоваться на типах.

std::optional

optional<int> findPath(graph g, int from, int to)
{
    //Find path from `from` to `to`
    if (d[to] != INF)
        return d[to];
    return {}
}

//Проверим, что путь существует
if (auto dist = findPath(...); dist.hasValue())
    cout << dist.value(); //Получим его
else
    cout << -1;

//Или сразу используем defaultValue, если значение не было установлено
cout << findPath(...).value_or(-1); //Выводит расстояние если оно найдено и -1 иначе

Неконстантное(ый?, ая?) string::data

Для любителей С:

string str = "hello";
char *p = str.data();
p[0] = 'H';
cout << str; // Hello

Свободные функции std::size, std::data и std::empty

В добавку к уже существующим свободным функциям std::begin, std::end и другим, появились новые, такие как: std::size, std::data и std::empty:

vector<int> v = { 3, 2, 5, 1, 7, 6 };

size_t sz = size(v);
bool empty = empty(v);
auto ptr = data(v);

std::clamp

Возвращает x, если оно попало в интервал [low, high] и ближайшее значение иначе:

cout << clamp(7, 0,  10); //7
cout << clamp(7, 0,  5);  //5
cout << clamp(7, 10, 50); //10

Я думаю, что это полезная функция, но будет сложно вспомнить как она называется в течение контеста :)

GCD and LCM! (НОД и НОК)

cout << gcd(24, 60); // 12
cout << lcm(8, 10);  // 40

Возвращаемое значение у emplace_back

vector<int> v = { 1, 2, 3 };

auto &r = v.emplace_back(10);
r = 42;
//v теперь содержит {1, 2, 3, 42}

Функции в std::map:

  • Extract (можно даже поменять ключ!!!)
map<int, string> myMap{ { 1, "Gennady" }, { 2, "Petr" }, { 3, "Makoto" } };
auto node = myMap.extract(2);
node.key() = 42;
myMap.insert(move(node));

// myMap: {{1, "Gennady"}, {42, "Petr"}, {3, "Makoto"}};

Note: Extract  —  единственный способ поменять ключ элемента map'а без reallocation(реаллокации?)

Асимптотика:
extract(key): doc
extract(iterator): O(1) amortized doc

  • Merge
map<int, string> m1{ { 1, "aa" }, { 2, "bb" }, { 3, "cc" } }; 
map<int, string> m2{ { 4, "dd" }, { 5, "ee" }, { 6, "ff" } };
m1.merge(m2);
// m1: { {1, "aa"}, {2, "bb"}, {3, "cc"}, {4, "dd"}, {5, "ee"}, {6, "ff"} }
// m2: {}

Асимптотика: doc

  • Раньше, чтобы понять, произошла вставка в map или обновление, необходимо было сначала найти элемент, а потом использовать operator[]. Теперь появилась функция insert_or_assign:
map<int, string> m;
m.emplace(1, "aaa");
m.emplace(2, "bbb");
m.emplace(3, "ccc");

auto [it1, inserted1] = m.insert_or_assign(3, "ddd");
cout << inserted1; // 0

auto [it2, inserted2] = m.insert_or_assign(4, "eee");
cout << inserted2; // 1

Асимптотика: doc

Более строгий порядок вычисления выражений

В C++17 появились новые правила, более строго определяющие порядок вычисления выражений:

  • Постфиксные выражения вычисляются слева направо (в том числе вызовы функций и доступ к членам объектов)
  • Выражения присваивания вычисляются справа налево.
  • Операнды операторов << и >> вычисляются слева направо.

Таким образом, как указывается в предложении к стандарту, в следующих выражениях теперь гарантированно сначала вычисляется a, затем b, затем c:

a.b
a->b
a->*b
a(b1, b2, b3)
b @= a
a[b]
a << b << c
a >> b >> c

Note: Порядок вычисления b1, b2, b3 все еще не определен.

P.S.: Все материалы адаптированы мной с примерами отсюда

  • Проголосовать: нравится
  • +415
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +59 Проголосовать: не нравится

Thank goodness for clamp. No more max of min of max of...

»
7 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
//C++17
template<typename... Args>
void readln(Args&... args)
{
    ((cin >> args), ...);
}

template<typename... Args>
void writeln(Args... args)
{
    ((cout << args << " "), ...);
}

int x;
int y;

Alternatively if you don't want to overkill too hard:

copy(istream_iterator<T>(cin), istream_iterator<T>(), back_inserter(input));

copy(output.begin(), output.end(), ostream_iterator<T>(cout, " "));


Were there some issues hindering __gcd? Or is it just compiler dependent so they introduced gcd as the standard instead?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    No, unfortunately ostream_iterator must be instantiated with type:

    vector<int> myvector;
    copy(myvector.begin(), myvector.end(), ostream_iterator<int>(cout, " "));
    

    But my implementation works with different types without any type-mentioning:

    int x;
    double d;
    vector<int> v(10); //and overloaded ostream& operator<<(ostream& os, vector<T> a) and operator>>
    readln(x, d, v);
    writeln(x, d, v);
    
»
7 лет назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится

“community wants new edition of C++ tricks by Swift,...”

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

What is the complexity of merging two maps?

»
7 лет назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится

Can you add the complexity of the new functions?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Added complexity of new map functions

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится -22 Проголосовать: не нравится

      What about others :size(),empty(),data(),gcd(),lcm(),clamp()

      I know than I can find the answer by googling but it wouldn't be better if you added them

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        :size(), empty(), data() are only wrappers, so they have no complexity: complexity is in usual functions .size() and so on
        clamp is literally two comparisons
        gcd is literally __gcd and usual euclidean algo
        lcm is literally one multiplication and division
        So, nothing strange and breaking in these functions, only shortness and convenience

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится -22 Проголосовать: не нравится

          Thanks for explaining that. We should always check the complexity of the new methods.

          Imagine if clamp was using linar search. It would be a TLE tool. (I know that's using two comparisons as you said).

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Если уж мы про олимпиадный подход, то как же ты забыл о новых поисковых алгоритмах? :-) http://en.cppreference.com/w/cpp/algorithm/search

Теперь быстрый поиск уже встроен в кресты: Бойер-Мур и Бойер-Мур-Хорспулл. Реализации ожидаемо должны быть похожи на те, что есть в Boost.Algorithm.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Я не забыл, я специально пропустил, потому что "it has O(nm) in the worst case", а в спортивном программировании всегда worst case :)

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится -13 Проголосовать: не нравится

      Но мы оба прекрасно понимаем, что это БМ и БМХ, так что не стоит так сильно бояться и всё таки можно юзать :-)

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Да ладно, если кому-то совсем лень самому написать префикс- или z- функцию, что займёт жалких три строчки, можно использовать обычный string::find. Его сложность хоть и unspecified, но я пока задач, где он валится не встречал.

        Бойер-Мур это вообще ни разу не олимпиадный подход.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Why long is of 4 bytes in Codeforces(C++17) while it is of 8 bytes in Codechef(C++14) ?
               Codeforces           Codechef
            (C++17)(4 bytes)    (C++14)(8 bytes)
LONG_MIN :   -2147483648       -9223372036854775808
LONG_MAX :    2147483647        9223372036854775807
ULONG_MAX:    4294967295       18446744073709551615
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

A typical benefit of deduction guide is that we can directly write tuple(x, y, z) instead of make_tuple(x, y, z), and pair(x, y) instead of make_pair(x, y). Five less characters and the new version looks more compact ;)

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

    But we can just write {x,y,z} instead of make_tuple(x, y, z) and {x,y} instead of make_pair(x, y) and that's 10 and 9 characters less respectively.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +15 Проголосовать: не нравится

      not in every context

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Would You mind giving an example of such a context?It will be helpful.Thank you.

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится

          Case 1:

          auto p = {1, 2};
          cout << p.first << " " << p.second << "\n"; // c++ treats p as an initializer_list<int> and fails in finding its "first" field
          

          Case 2:

          auto p = pair{1, 2};
          cout << p.first << " " << p.second << "\n"; // stdout: 1 2
          

          Case 3:

          auto p = pair(1, 2);
          cout << p.first << " " << p.second << "\n"; // stdout: 1 2
          
          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
            Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

            Thanks a lot for pointing out
            When i was writing above comment what i had in my mind was

            pair p={1,2};//Only in c++17 by template argument deduction
            cout << p.first <<" "<<p.second<<"\n"; // stdout: 1 2
            


        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          Comparisons

          if (p == {x, y}) ... 
          

          doesn't work

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем Igorjan94 (предыдущая версия, новая версия, сравнить).

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Igorjan94 (previous revision, new revision, compare).

»
4 года назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

Is space required in structure binding? I noted the different behavior on AtCoder between for(auto [x, y]:vii) and for(auto [x,y]: vii). It's so weird. See 2 submissions: 18566943 vs. 18566919.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I was wondering which part of C++17 would be appropriate to use for competitive programming, which gave me a good answer :)

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Also I think try_emplace() method in map is also useful. Using this, coord-compression could be written as

for (auto i : a) {
    compress.try_emplace(i, compress.size());
}