C++17, competitive programming edition

Правка en1, от Igorjan94, 2018-02-13 02:50:33

C++17 is now available on codeforces, community wants new edition of C++ tricks by HosseinYousefi, so, let's start!

  • Fold expressions

I think that everybody knows, what reduce or fold means, but a c++11 example: 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

In C++17 there is also folding support for a template parameters list. It has the following syntax: (pack op ...) (... op pack) (pack op ... op init) (init op ... op pack) Before C++17, to implement a template function that takes a variable number of parameters and calculates their sum: ``` //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

This is useful, when we use comma as op: ``` // C++17 template<typename T, typename... Args> void pushToVector(vector& v, Args&&... args) { (v.push_back(forward(args)), ...); //This code is expanded into a sequence of expressions separated by commas as follows: // v.push_back(forward(arg1)), // v.push_back(forward(arg2)), // .... }

vector v; pushToVector(v, 1, 4, 5, 8); ```

And my favourite example: ``` //C++17 template<typename... Args> void readln(Args&... args) { ((cin >> args), ...); }

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

int x; int y; readln(x, y); // enter 100 500 writeln(x, "some string", y); // 100 some string 500 ``` Note that brackets are meaningfull

  • Class template argument deduction ``` template 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 u = {1, 2};

//C++17 pair p2 = {14, 17.0} point v = {1, 2}; If struct is complex, there is a possibility to write deduction guides ourselves, for instance: template<typename T, typename U> struct S { T first; U second; };

// My deduction guide template<typename T, typename U> S(const T &first, const U &second) -> S<T, U>; ``` Note: the compiler is able to create deduction guide automatically from a constructor, but in this example, the structure S has no constructor, so, we define deduction guide manually.

  • *this capture in lambda expressions I don't think this is useful in CP, but who knows: ``` 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(); } }; `` [Article](https://arne-mertz.de/2017/10/mutable/) aboutmutablekeyword. [Статья](https://habrahabr.ru/company/infopulse/blog/341264/) о ключевом словеmutable`.

  • Structured bindings

The most useful syntax sugar for decomposition of objects. ``` template struct point { T x; T y; point(T x, T y) : x(x), y(y) {} };

vector<point> points = {{0, 0}, {1, 0}, {1, 1}, {1, 0}}; //C++11 for (auto& point : points) { int x, y; tie(x, y) = point; //...Some compex logic with x and y }

//C++17 for (auto& [x, y] : points) { //...Some compex logic with x and y } ```

Or iterating over map: map<int, string> m; for (auto [key, value] : m) cout << "key: " << key << '\n' << "value: " << value << '\n';

  • Initializer in if and switch ``` set s;

if (auto [iter, ok] = s.insert(42); ok) { //... } else { //ok and iter are available here } //But not here ```

  • New attributes

[[fallthrough]] attribute indicates that the break operator inside a case block is missing intentionally: int requests, type; cin >> requests; for (int q = 0; q < requests; ++q) switch (cin >> type; type) //Initializer in switch { case 1: int l, r; cin >> l >> r; //proceed request of first type break; case 2: [[fallthrough]]; //Compiler warning will be supressed case 3: int value; cin >> value; //Proceed requests of second and third types. }

[[nodiscard]] attribute is used to indicate that the return value of the function should not be ignored and can be also applied to data types.

  • 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 {}
}

//We can check if value exists
if (auto dist = findPath(...); dist.hasValue())
    cout << dist.value(); //And get it
else
    cout << -1;

//Or use defaultValue if value is not set
cout << findPath(...).value_or(-1); //Prints distance if path exists and -1 otherwise
  • Non-constant string::data For C-lovers: string str = "hello"; char *p = str.data(); p[0] = 'H'; cout << str; // Hello

  • Free functions std::size, std::data and std::empty In addition to the already existing free functions std::begin, std::end and others, some new free functions appeared, such as: std::size, std::data and std::empty: ``` vector v = { 3, 2, 5, 1, 7, 6 };

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

  • std::clamp Returns x if it is in the interval [low, high] or, otherwise, the nearest value: cout << clamp(7, 0, 10); //7 cout << clamp(7, 0, 5); //5 cout << clamp(7, 10, 50); //10 I think that it is convenient function, but it'll be difficult to call it in mind during contest :)

  • GCD and LCM! cout << gcd(24, 60); // 12 cout << lcm(8, 10); // 40

  • The return value from emplace_back ``` vector v = { 1, 2, 3 };

auto &r = v.emplace_back(10); r = 42;

//v now contains {1, 2, 3, 42} ```

  • std::map functions:

** Extract (and even change key!!!) ``` 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"}}; ```

** 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: {}

** To figure out if the insert or update occurred, we had to first look for the element, and then apply the operator[] ``` 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 ```

  • More rigorous evaluation order of expressions

And in general c++17 introduces new rules, defining more strictly the evaluation order of expressions:

** Postfix expressions are evaluated from left to right (including function calls and access to objects members) ** Assignment expressions are evaluated from right to left. ** Operands of operators << and >> are evaluated from left to right. ** Thus, as it is mentioned in the proposal for the standard, in the following expressions a is now guaranteed to be evaluated first, then b, then c:

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

Note that the evaluation order between b1, b2, b3 is still not defined.

P.S. All materials are adopted with my example from here

Теги c++, c++14, c++17

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский Igorjan94 2018-02-19 18:15:04 499
ru4 Русский Igorjan94 2018-02-19 18:14:21 516
ru3 Русский Igorjan94 2018-02-13 18:30:49 10 асимптотика ** fix
en6 Английский Igorjan94 2018-02-13 18:29:39 482 compexity of map methods added
ru2 Русский Igorjan94 2018-02-13 18:26:15 504 добавлена асимптотика в мапе
en5 Английский Igorjan94 2018-02-13 15:39:29 266
ru1 Русский Igorjan94 2018-02-13 15:38:33 8977 Первая редакция перевода на Русский
en4 Английский Igorjan94 2018-02-13 03:24:22 31
en3 Английский Igorjan94 2018-02-13 03:21:47 0 (published)
en2 Английский Igorjan94 2018-02-13 03:18:35 837 Tiny change: 'n[cut]\n\nBefore' -> 'n[cut]\n\n\n\nBefore'
en1 Английский Igorjan94 2018-02-13 02:50:33 8433 Initial revision (saved to drafts)