New C++ Features

Note: Considering the realities of algorithm competitions, this article will not study the syntax comprehensively; it only discusses the parts that may be useful in algorithm competitions.

The syntax in this article follows the C++11 standard. When semantics differ, C++11 is used as the standard; C++14, C++17, and other syntax is mentioned as appropriate and specially marked.

The auto type specifier

The auto type specifier is used to automatically deduce the type of variables and so on. For example:

auto a = 1;        // a is of type int
auto b = a + 0.1;  // b is of type double

Note that auto removes references. If you do not want the overhead of copying, you need to specify the reference manually:

int a = 1;
int& b = a;
auto c = b;   // c is of type int; has copy overhead
auto& e = a;  // e is of type int&; has no copy overhead

The decltype specifier

decltype can deduce a type from an entity or an expression. Note that the deduction methods differ; incorrect use may cause a dangling reference. It is not commonly used in contests, so only a rough introduction is given here.

#include <iostream>
#include <vector>

int main() {
  int a = 1926;
  decltype(a) b;                 // Deduce from an entity; b is of type int
  decltype(1 + 1) c;             // Deduce from an expression; c is of type int
  decltype((a)) d = a;           // Deduce from an expression; d is of type int&!
  std::vector<decltype(b)> vec;  // Deduce from an entity; vec is of type std::vector <int>
  return 0;
}

constexpr

See also Constant Expressions constexpr (C++11)

Range-based for loops

A range-based for loop traverses an iterable object, with the same efficiency as traversal using iterators. Both are generally more efficient than index-based traversal because they do not need to address elements by index.

The syntax of a simple range-based for loop is as follows:

for (item_declaration : range_initializer) statement

For example:

std::array<int, 4> arr = {1, 2, 3, 4};
for (int x : arr) {
  std::cout << x << std::endl;
}

The code produced by the syntax above is equivalent in effect to the following code:

std::array<int, 4> arr = {1, 2, 3, 4};
for (auto px = arr.begin(), ed = arr.end(); px != ed; ++px) {
  std::cout << *px << std::endl;
}

item-declaration

Declare a variable to receive an element from the container on the right. The variable type must match the type of the container's elements. You can use auto to deduce the type automatically; for complex types, auto& is commonly used to avoid copy overhead.

range-initializer

The range initializer can be any iterable object (such as an array or a class object that defines begin and end member functions). If an expression is supplied, the expression is evaluated only once.

Example:

int a[] = {1, 1, 4, 5, 1, 4};
std::vector<int> b{1, 1, 4, 5, 1, 4};
std::map<std::string, int> c{{"114", 114}, {"514", 514}};
for (int i : a) std::cout << i;
for (auto i : b) std::cout << i;
// The type of i below is std::pair<const std::string, int>&
for (auto& i : c) std::cout << i.first << i.second;
for (auto i : {1, 1, 4, 5, 1, 4}) std::cout << i;

Supporting range-based for for custom types

Simply provide begin and end member functions whose return type supports comparison, increment, and dereference (the * operator).

Here is an example:

#include <iostream>

struct C {
  int a[4];

  int* begin() { return a; }

  int* end() { return a + 4; }
};

int main() {
  C c = {1, 9, 2, 6};
  for (auto i : c) std::cout << i << " ";
  std::cout << std::endl;
  // output: 1 9 2 6
  return 0;
}

Init-statement (C++20)

In C++20, an init-statement can also be used to implement some functionality, such as a loop counter:

#include <iostream>
#include <vector>

int main() {
  std::vector<int> v = {0, 1, 2, 3, 4, 5};

  for (int counter = 0; auto i : v)  // the init-statement (C++20)
    std::cout << counter++ << ' ' << i << std::endl;
}

Structured bindings (C++17)

Structured binding is syntactic sugar provided by C++17 that makes it convenient to extract subelements or references to subelements, as follows:

struct C {
  int x{1}, y{2};
};

int arr[]{4, 5, 6};

auto [c1, c2] = C{};       // c1=1,c2=2; type int
auto& [a1, a2, a3] = arr;  // a1=arr[0],a2=arr[1],a3=arr[2]; type int&

Note the following:

• The number of variables declared on the left must match the number of subelements of the object on the right
• The type declaration must use auto
• & can be used to obtain a reference

You can write the following when traversing a map container:

std::map<std::string, int> m = {{"k1", 1}, {"k2", 2}};

// Use "auto&"; there is no copy overhead
for (auto& [k, v] : m) {
  // The type of k is const std::string&, because the key has a const qualifier
  // The type of v is int&
  std::cout << k << ' ' << v << std::endl;
}

std::tuple

Tuples are defined in the <tuple> header. They generalize std::pair and can store values of multiple different types. Here is an example:

#include <iostream>
#include <tuple>
#include <vector>

constexpr auto expr = 4 - 1;  // expr = 3

int main() {
  std::vector<int> vec = {1, 9, 2, 6, 0};
  std::tuple<int, int, std::string, std::vector<int>> tup =
      std::make_tuple(817, 114, "514", vec);

  // Use get<> to obtain subelements; the angle brackets must contain an integral constant expression
  for (auto i : std::get<expr>(tup)) std::cout << i << " ";
  // The first element is numbered 0, so std::get<3> gives us a std::vector<int>
  return 0;
}

After C++17, structured bindings can be used to extract values, as follows:

std::vector<int> vec = {1, 9, 2, 6, 0};
std::tuple<int, int, std::string, std::vector<int>> tup =
    std::make_tuple(817, 114, "514", vec);

auto& [a, b, c, d] = tup;  // C++17 Structured binding
std::cout << a << ' ' << b << c << std::endl;
std::cout << d.size() << ' ' << d[2] << std::endl;

Member functions

Example:

constexpr std::tuple<int, int> tup = {1, 2};
std::tuple<int, int> tupA = {2, 3}, tupB;
tupB = tup;
tupB.swap(tupA);

Non-member functions

Example:

std::tuple<int, int> tupA = {2, 3}, tupB;
tupB = std::make_tuple(1, 2);
std::swap(tupA, tupB);
std::cout << std::get<1>(tupA) << std::endl;
int x;
std::tie(x, std::ignore) = tupB;
std::cout << x << std::endl;

std::tie assigns tuple elements to existing variables; std::ignore can be used to skip unnecessary elements. Structured bindings directly declare new variables (supporting value/reference binding) and must accept all elements.

Function objects

An object that can use the function-call operator operator() is called a function object (FunctionObject).

This is not a language feature but a concept or requirement that is widely used in the standard library.

Function objects can be roughly divided into two categories:

1. Function pointers
2. Class objects that overload the operator() operator

lambda is a typical function object of the second category. It stores captured contents in member variables and overloads the function-call operator.

Lambda expressions

Please refer to the Lambda expressions page.

std::function

std::function is a general-purpose function wrapper defined in the <functional> header.

An instance of std::function can store, copy, and call any Callable object, including Lambda expressions, pointers to member functions, or other function objects.

If std::function does not contain any callable object (for example, after default construction), calling it throws a std::bad_function_call exception.

#include <functional>
#include <iostream>

struct Foo {
  Foo(int num) : num_(num) {}

  void print_add(int i) const { std::cout << num_ + i << '\n'; }

  int num_;
};

void print_num(int i) { std::cout << i << '\n'; }

struct PrintNum {
  void operator()(int i) const { std::cout << i << '\n'; }
};

int main() {
  // Store a free function
  std::function<void(int)> f_display = print_num;
  f_display(-9);

  // Store a Lambda
  std::function<void()> f_display_42 = []() { print_num(42); };
  f_display_42();

  // Store a call to a member function
  std::function<void(const Foo&, int)> f_add_display = &Foo::print_add;
  const Foo foo(314159);
  f_add_display(foo, 1);
  f_add_display(314159, 1);

  // Store a call to a data-member accessor
  std::function<int(Foo const&)> f_num = &Foo::num_;
  std::cout << "num_: " << f_num(foo) << '\n';

  // Store a call to a function object
  std::function<void(int)> f_display_obj = PrintNum();
  f_display_obj(18);
}

Variadic function templates

Before C++11, both class templates and function templates could accept only a fixed number of template parameters. C++11 allows any number and any type of template parameters.

This section only briefly introduces variadic function templates.

The function template fun declared by the following code can accept any number and any type of template parameters as its template arguments.

template <typename... Clazz>
void fun(Clazz... paras) {}

paras is a function parameter pack that accepts zero or more function arguments. Clazz is a template parameter pack that accepts zero or more template arguments (non-type, type, or template); when marked with typename, it accepts only types.

It can be understood simply as follows:

• Template parameter packs are generally some type names (but compile-time constants or template names can also be used)
• Function parameter packs are generally some variable names

The fun function can now be called as follows:

fun();
fun(1);
fun(1, 2, 3);
fun(1, 0.0, "abc");

Parameter pack expansion

Parameter pack expansion syntax

Parameter pack expansion is very simple: use ..., with , inserted as the separator. For example:

template <class A, class... C>
void func(A arg1, C... arg2) {
  // C is a template parameter pack
  tuple();  // Expanded into tuple<int, int, double, bool>();

  // arg2 is a function parameter pack
  func(arg2...);  // Expanded into func( 2, 1.1, true );
}

func(1, 2, 1.1, true);

Operations can also be applied during parameter pack expansion, for example:

template <class A, class... C>
void func(A arg1, C... arg2) {
  func((arg2 + 1)...);
  // Expanded into func( (2+1) , (1.1+1), (2.1f+1) );
}

func(1, 2, 1.1, 2.1f);

Terminating function

The function above cannot run because the number of parameters keeps decreasing, eventually becoming zero and causing an error.

We need to specify a termination condition by providing an ordinary function, as follows:

void func() {}

template <class A, class... C>
void func(A arg1, C... arg2) {
  std::cout << arg1 << std::endl;
  func((arg2 + 1)...);
}

func(1, 2, 1.1, 2.1f);

Thus, when the number of parameters is not 0, the template is called; when there are no parameters, the ordinary function is called, and the program runs normally.

Fold expressions (C++17)

C++17 provides convenient syntax for handling function parameter packs. Its syntax is as follows (parentheses are required):

1. ( pack op ... ), which becomes (E1 op (... op (EN-1 op EN)))
2. ( ... op pack ), which becomes (((E1 op E2) op ...) op EN)
3. ( pack op ... op init ), which becomes (E1 op (... op (EN−1 op (EN op I))))
4. ( init op ... op pack ), which becomes ((((I op E1) op E2) op ...) op EN)

A simple demonstration makes this easier to understand:

template <class... C>
void func(C... args) {
  (std::cout << ... << args) << std::endl;
  // Syntax 4, equivalent to ↓
  // ( ( ( std::cout << 1 ) << 2.1 ) << true ) << std::endl;
  // Output: 12.11  Note that true is output as 1 because boolalpha is not specified here

  std::cout << (args && ...) << std::endl;
  // Syntax 1, equivalent to ↓
  // std::cout << ( 1 && ( 2.1 && true ) ) ) << std::endl;
  // Output: 1
}

func(1, 2.1, true);

Abbreviated function templates (C++20)

Starting from C++20, auto ... can be used directly as the parameter type to abbreviate a function template:

void func(auto... args) { (std::cout << ... << args) << std::endl; }

It is still essentially a function template and is equivalent to the following:

template <class... T>
void func(T... args) {
  (std::cout << ... << args) << std::endl;
}

Ranges library (C++20)

The ranges library is an extension of the iterator and generic algorithm libraries. It makes iterators and algorithms more powerful through composition and reduces errors.

A range is a traversable sequence, including arrays, containers, views, and so on.

When complex operations need to be performed on containers and other ranges, the ranges library can make algorithms easier and clearer to write.

View

A view is a lightweight object that implements some algorithms through specific mechanisms (such as custom iterators), providing ranges with more ways to traverse them to meet requirements.

The ranges library has implemented some commonly used views, roughly divided into two types:

1. Range factories, used to construct special ranges. These factories avoid the need to construct a container manually, reduce overhead, and directly generate a range.
2. Range adaptors, providing varied traversal support. They can be called like functions and can also be connected with the pipe operator | to implement chained calls.

Range adaptors, as range adaptor closure objects, are also function objects. They overload operator|, allowing them to be assembled like a pipeline.

Even under complex operations, good readability can be maintained. The following properties hold:

If A, B, and C are range adaptor closure objects, R is a range, and the other letters are possible valid arguments, the expression

R | A(a) | B(b) | C(c, d)

is equivalent to

C(B(A(R, a), b), c, d)

Here ranges::take_view and ranges::iota_view are used as examples:

#include <iostream>
#include <ranges>

int main() {
  const auto even = [](int i) { return 0 == i % 2; };

  for (int i : std::views::iota(0, 6) | std::views::filter(even))
    std::cout << i << ' ';
}

1. The range factory std::views::iota(0, 6) generates a range of the integer sequence from 0 to 5
2. The range adaptor std::views::filter(even) filters the preceding range and generates a range containing only even numbers
3. The two operations are linked using the pipe operator

The code above does not need to allocate additional heap space to store the range generated at each step. The actual generation and filtering occur during traversal (more specifically, in the construction, increment, and dereference of the internal iterators), which is zero overhead.

At the same time, the lifetime of the externally supplied range is equivalent to the lifetime of the internal elements of the range adaptor. If the external range (such as a container or range factory) has already been destroyed, traversing these views has the same effect as dereferencing a dangling pointer and is undefined behavior.

To avoid the situation above, the lifetime of an adaptor should be strictly required to be within the lifetime of every range it uses.

#include <iostream>
#include <ranges>
#include <vector>

using namespace std;

int main() {
  auto view = [] {
    vector<int> vec{1, 2, 3, 4, 5};
    return vec | std::views::filter([](int i) { return 0 == i % 2; });
  }();

  for (int i : view) cout << i << ' ';  // runtime undefined behavior

  return 0;
}

Constrained Algorithm

C++20 provides constrained versions of most algorithms in the std::ranges namespace. A range can be specified as an iterator-sentinel pair or as a single range argument, and projections and callable objects that point to members are supported. In addition, the return types of most algorithms have been changed to return all potentially useful information calculated during execution.

These algorithms can be understood as improved versions of algorithms in the old standard library. They are all function objects and provide friendlier overloads and argument type checking (based on concept). First, let us compare std::sort and ranges::sort as an example.

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {
  vector<int> vec{4, 2, 5, 3, 1};

  sort(vec.begin(), vec.end());  // {1, 2, 3, 4, 5}

  for (const int i : vec) cout << i << ", ";
  cout << '\n';

  ranges::sort(vec, ranges::greater{});  // {5, 4, 3, 2, 1}

  for (const int i : vec) cout << i << ", ";

  return 0;
}

The algorithm implementations of ranges::sort and sort are the same, but the former provides range-based overloads, making argument passing more concise. Most of the other algorithms in the std namespace also have corresponding range-overload versions in the ranges namespace.

Using these range arguments together with the views from the previous section allows us to perform complex operations while keeping the code readable. Consider the following example:

#include <algorithm>
#include <array>
#include <iostream>
#include <ranges>

using namespace std;

int main() {
  const auto& inputs = views::iota(0u, 9u);  // Generate the integer sequence from 0 to 8
  const auto& chunks = inputs | views::chunk(3);  // Divide the sequence into chunks of 3 elements each
  const auto& cartesian_product =
      views::cartesian_product(chunks, chunks);  // Compute the Cartesian product of the chunks with themselves

  for (const auto [l_chunk, r_chunk] : cartesian_product)
    // Compute the sum of the two chunk integers under the Cartesian product
    cout << ranges::fold_left(l_chunk, 0u, plus{}) +
                ranges::fold_left(r_chunk, 0u, plus{})
         << ' ';
}

References

1. C++ reference manual