Ежедневный бит(е) C++ | Изучите современный C++ 3/N

Daily bit(e) of C++ #104 , Современный курс C++ (включая C++23), часть 3 из N

Добро пожаловать на третий урок из серии Learn Modern C++. Сегодня мы пройдем ускоренный курс по типам.

Если вы пропустили предыдущий урок, посмотрите его здесь:

Одним из отличительных аспектов C++ является то, что он рассматривает библиотечные типы (включая определяемые пользователем) как встроенные типы. Например, библиотечные типы могут определять, что происходит, когда одна переменная назначается другой, или как работают сравнения и арифметические операции.

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

Если вы выполнили домашнюю работу к предыдущему уроку, вы уже встречались с некоторыми базовыми типами, и я даже упомянул один из библиотечных типов (std::vector) в одном из примеров.

Буль

bool — это логический тип, имеющий только два допустимых значения: true и false.

True сопоставляется с 1, а false сопоставляется с 0. Такое поведение часто используется для различных трюков, которых вам следует избегать. Явный код всегда лучше.

#include <iostream>

bool x = true;

// std::boolalpha is a manipulator that sets the stream
// (in this case std::cout) to handle boolean values
// as true/false, not the corresponding integral values 1/0
std::cout << std::boolalpha << "x == " << x << "\n";
// the setting persists until unset
std::cout << std::noboolalpha << "x == " << x << "\n";

// Good example of boolean expressions are basic comparisons:
bool y = 3 < 1;
// y == false

// Do not rely on implicit conversions between bool
// and integral types (but since you may run into it):
int a = 42;
bool z = a;
// same as bool z = (a != 0);
// z == true

// You might also come across this trick:
int b = !!a;
// double negation and then coversion to integral turns 
// any non-zero value to 1

Откройте пример в Compiler Explorer.

Целочисленные типы

Целочисленные типы охватывают целые числа со знаком: int и целые числа без знака: unsigned int (или просто «без знака»). Вы уже видели оба на предыдущем уроке.

Целочисленные типы могут быть дополнительно изменены модификаторами: «short», «long» и «long long», создавая иерархию типов с увеличением количества битов. В этом курсе мы будем использовать целочисленный тип фиксированной ширины: int64_t.

Если вас интересует разрядность различных целочисленных типов, эта страница предлагает отличный обзор: https://en.cppreference.com/w/cpp/language/types#Properties.

Хотя технически это необязательный тип, тип int64_t будет отображаться на 64-битный целочисленный тип со знаком вашей локальной платформы.

#include <cstdint>
// int64_t comes from the cstdint header


int64_t a = 10;

Откройте пример в Compiler Explorer.

Плавающая запятая

Наконец, C++ предлагает три типа с плавающей запятой: float, double и long double. Кодировка соответствует стандарту IEEE-754, где поддерживается (большинство платформ).

#include <iostream>
#include <iomanip>

double x = 4.2;

// Default output skips trailing zeroes
std::cout << "x == " << x << "\n";
// output: "x == 4.2"

// Not all decimal numbers can be precisely represented
// by binary floating point representation.
float y = 0.1;

// Number of displayed decimal digits can be controlled through
// the std::setprecision manipulator.
std::cout << std::setprecision(10);

// std::fixed for fixed-width output
std::cout << std::fixed << "y == " << y << "\n";
// output: "y == 0.1000000015"

// std::scientific for scientific notation
std::cout << std::scientific << "y == " << y << "\n";
// output: "y == 1.0000000149e-01"

Откройте пример в Compiler Explorer.

Массивы

Для массивов мы должны перейти к нашему первому типу библиотеки: std::vector. Поскольку std::vector — это шаблон класса, нам нужно ввести новый синтаксис. Шаблоны фактически являются параметризованными типами. В данном случае нас интересует тип элемента.

#include <vector>
#include <cstdint>

// An array of integers, initialized with five elements:
std::vector<int64_t> data{1,2,3,4,5};

// Elements can be accessed using the operator []
// data[3] == 4

// An array of arrays of integers follows the same pattern
std::vector<std::vector<int64_t>> second_dimension{
    {1,2,3},{2,3},{4,5,6},{7}};

// Same logic for accessing elements
// second_dimension[1][0] == 2
// second_dimension[2][2] == 6

// We can use element access to mutate the array
second_dimension[3] = {1,2,3,4,5};
second_dimension[1][0] = 42;

Откройте пример в Compiler Explorer.

Обратите внимание, что доступ к несуществующим элементам делает вашу программу искаженной, поэтому всегда проверяйте правильность индекса при доступе к элементам по индексу.

Именно из-за подобных ошибок мы тестируем домашнюю работу с конфигурациями «addrsan» и «ubsan», которые включают в себя дезинфицирующее средство адреса и дезинфицирующее средство неопределенного поведения. Например, средство очистки адресов обнаружит ошибку такого типа, и вывод будет выглядеть примерно так:

#include <vector>
#include <cstdint>

std::vector<int64_t> data{1,2,3,4,5};

// C-style for loop
for (int64_t idx = 0; idx < std::ssize(data); ++idx) {
    // access data[idx]
}

// range-for loop
for (int64_t v : data) {
    // access v
}

// Example of bad access caught by address sanitizier ->
data[5] = 0;
/* With errors, always start at the top. The important part here is:

WRITE of size 8 at 0x604000000038 thread T0
#0 0x4015ff in main /app/example.cpp:17

That is, we have an invalid write at line 17 in this file.
*/

Открыть пример в Compiler Explorer.

Как я уже упоминал, библиотечные типы могут определять поведение операторов (таких как оператор доступа к элементам); кроме того, они также могут обеспечивать операции манипулирования и запросов через функции-члены:

#include <vector>
#include <cstdint>

// Empty array
std::vector<int64_t> data;
// data.empty() == true, std::ssize(data) == 0

// Add new element to the back of the array.
data.push_back(42);
// data.empty() == false, std::ssize(data) == 1

// Remove an element from the back of the array.
data.pop_back();
// data.empty() == true, std::ssize(data) == 0

data = {1, 2, 3};
// Resize an array to the specified size (5)
// setting new elements to the provided value (0)
data.resize(5,0);
// data == {1, 2, 3, 0, 0}

// Remove all elements
data.clear();
// data.empty() == true, std::ssize(data) == 0

std::vector<int64_t> a{1,2};
std::vector<int64_t> b{1,2,3};
std::vector<int64_t> c{4,5};

// Lexicographical comparison
// a < b, b < c (also ==, !=, >, <=, >=)

Открыть пример в Compiler Explorer.

std::vector — это стандартный тип, который вы будете использовать постоянно. Поэтому я пропущу и упомяну важный аспект инвалидации std::vector: iterator.

Когда мы помещаем новые элементы в std::vector, может потребоваться увеличить внутреннюю память. Видимый побочный эффект заключается в том, что мы больше не используем итераторы, полученные до этого перераспределения, а цикл for-range полагается на итераторы для своей внутренней реализации.

Важный вывод — избегать изменения массива при его повторении. Помимо риска обращения к недопустимой памяти, также обычно сложно рассуждать о циклах, которые изменяют структуру, по которой они перебираются.

#include <vector>
#include <cstdint>

int main() {
    std::vector<int64_t> data{1,2,3,4,5};

    for (int64_t v : data) {
        data.push_back(v); // BOOM
    }  
}
/*
ERROR: AddressSanitizer: heap-use-after-free
READ of size 8 at 0x604000000018 thread T0
    #0 0x40155b in main /app/example.cpp:7
*/

Открыть пример в Compiler Explorer.

станд::массив

В редких случаях сложность std::vector может оказаться слишком большой. В таком случае мы можем использовать статический размер std::array.

Второй основной вариант использования std::array — это программирование во время компиляции, особенно когда нам нужно передать массивы из части кода во время компиляции в часть во время выполнения; однако это сложная тема.

#include <array>
#include <cstdint>

// Two template arguments, type of elements and number of elements
std::array<int64_t,5> data{1,2,3,4,5};

// We get a similar interface to std::vector
// however, since std::array is statically sized
// no push/pop operations
data[3] = 42;
// data == {1, 2, 3, 42, 5}

Открыть пример в Compiler Explorer.

Струны

Строки в C++ — довольно сложная тема. В этом курсе мы будем использовать строки ASCII.

C++ поддерживает Unicode; однако правильная обработка Unicode (даже с языковой поддержкой) является сложной темой, и вывод в формате Unicode C++23 еще не реализован в компиляторах.

Строки ASCII имеют тип std::string. Он предлагает тот же интерфейс, что и std::vector, но с дополнительными операциями, характерными для работы со строками:

#include <string>

std::string greeting = "Hello!";

// Same supported operations as std::vector
greeting.pop_back();
// greeting == "Hello"

// Append
greeting += " World!";
// greeting == "Hello World!"

// Prefix and suffix queries
if (greeting.starts_with("Hello")) { }
if (greeting.ends_with("World!")) { }

// Content query
if (greeting.contains("or")) { }

// Substring: starting index, number of characters
std::string food = greeting.substr(0,5);
// food == Hello

food[0] = 'J'; // Element manipulation, same as std::vector
// character type is char, its literals are single-quoted
// food == Jello

Открыть пример в Compiler Explorer.

уголь

Я пропустил тип символа, когда обсуждал основные типы, так как вы не будете использовать его изолированно. Однако вы должны знать об этом, так как это тип элемента std::string.

#include <string>
#include <cstdint>

char x = '?'; // Single character (in this case questionmark)
char y = '\n'; // special characters use a backslash (newline)

char a = '\''; // If we want to represent a single quotation, we need
               // to escape it using a backslash
std::string b = "\""; // Similar for string, we need to escape
                      // a double quotation

std::string text = "The quick brown fox jumps over the lazy dog";

for (int64_t idx = 0; idx < std::ssize(text); ++idx) {
    // iterate over all characters in the string
    // text[idx] is of type char
}

for (char c : text) {
    // iterate over all characters in the string
}

Открыть пример в Compiler Explorer.

Типы пользователей: агрегаты

Мы закончим сегодняшний урок с первой категорией типов пользователей. Агрегаты (что неудивительно) объединяют несколько переменных в одну сущность.

Несмотря на простоту, этот тип пользователя удобен, когда мы хотим сгруппировать определенные данные и рассматривать их как единое целое.

#include <cstdint>
#include <vector>

// Introduces a new type named "Position"
struct Position {
    int64_t x; // first member named x of type int64_t
    int64_t y; // second member named y of type int64_t
};

Position pos{10,22};
// pos == {10, 22}, that is: pos.x == 10, pos.y == 22

int64_t a = pos.x; // access the member
// a == 10

// Array of positions
std::vector<Position> positions{{1,2}, {4,4}, {5,3}, {-7,-9}};
// e.g. positions[2].y == 3

Открыть пример в Compiler Explorer.

Шаблоны

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

#include <vector>
#include <cstdint>

template <typename A, typename B>
struct Custom {
    A x;
    std::vector<B> y;
};

Custom<int64_t, double> a;
// a.x (type int64_t)
// a.y (type std::vector<double>)

a.x = 10;
a.y = {2.4, 0.3, -4.7777};

Открыть пример в Compiler Explorer.

Шаблоны пригодятся при создании универсальных типов, собирающих структурную информацию. Например, операции над массивом ведут себя одинаково независимо от типа элемента (с некоторыми предостережениями экспертов C++).

Пример с комментариями

В сегодняшнем примере с комментариями мы найдем путь в лабиринте, используя поиск в глубину. Если вы перейдете в Compiler Explorer, вы сможете поиграть с вводом лабиринта и изучить, как изменяется вывод.

#include <cstdint>
#include <vector>
#include <string>
#include <iostream>

// Aggregate to represent a position
struct Position {
    int64_t row;
    int64_t col;
};


// Maze representation
std::vector<std::string> maze{
    "#S#################",
    "#                 #",
    "# ############### #",
    "# #             # #",
    "# # ############# #",
    "# # #             #",
    "# # ############# #",
    "# #               #",
    "# #################",
    "#                 #",
    "#### ############ #",
    "#        #        #",
    "######## # ########",
    "#        #        #",
    "#################E#",
};


// Initial scan, find start and end, and print the maze:
std::cout << "Searching for a path in this maze:\n";
Position start, end;
for (int64_t row = 0; row < std::ssize(maze); ++row) {
    for (int64_t col = 0; col < std::ssize(maze[row]); ++col) {
        if (maze[row][col] == 'S')
            start = {row, col};
        if (maze[row][col] == 'E')
            end = {row, col};
        std::cout << maze[row][col];
    }
    std::cout << "\n";
}
std::cout << "\n";

// Find a path through the maze using DFS
// We use a std::vector as a stack data structure
std::vector<Position> stack;
// We start at start
stack.push_back(start);
// Change the end into an empty space so we don't have 
// to check maze[row][col] == ' ' || maze[row][col] == 'E'
maze[end.row][end.col] = ' ';

while (!stack.empty()) {
    // Grab the top element from the stack
    Position pos = stack.back();
    // If it is the end, we are done
    if (pos.row == end.row && pos.col == end.col) break;

    // Try to go up (taking care of valid indexes)
    if (pos.row != 0 && maze[pos.row-1][pos.col] == ' ') {
        // Mark as visited
        maze[pos.row-1][pos.col] = '.';
        // Add it to the stack
        stack.push_back({pos.row-1, pos.col});
        // Jump to the next loop iteration, exteding the path
        // from {pos.row-1,pos.col}
        continue;
    }

    // Same as above, but left
    if (pos.col != 0 && maze[pos.row][pos.col-1] == ' ') {
        maze[pos.row][pos.col-1] = '.';
        stack.push_back({pos.row, pos.col-1});
        continue;
    }

    // Same as above, but down
    if (pos.row + 1 < std::ssize(maze) && 
        maze[pos.row+1][pos.col] == ' ') {
        maze[pos.row+1][pos.col] = '.';
        stack.push_back({pos.row+1, pos.col});
        continue;
    }

    // Same as above, but right
    if (pos.col + 1 < std::ssize(maze[pos.row]) && 
        maze[pos.row][pos.col+1] == ' ') {
        maze[pos.row][pos.col+1] = '.';
        stack.push_back({pos.row, pos.col+1});
        continue;
    }

    // We are on a space which is a dead-end, 
    // remove it from the stack
    stack.pop_back();
}

// The stack is empty, meaning that all reachable spaces
// are dead-ends, i.e. there is no path
if (stack.empty()) {
    std::cout << "No path was found.\n";
    return 0;
}

std::cout << "Found a path, drawn using '@',"
   " '.' represent visited spaces:\n";

// The stack has our full path from start to end
while (!stack.empty()) {
    // Grab the tail of the path
    Position pos = stack.back();
    // Draw it onto the maze
    maze[pos.row][pos.col] = '@';
    // Remove from stack
    stack.pop_back();
}

// Draw the maze
for (int64_t row = 0; row < std::ssize(maze); ++row) {
    for (int64_t col = 0; col < std::ssize(maze[row]); ++col)
        std::cout << maze[row][col];
    std::cout << "\n";
}

Открыть пример в Compiler Explorer.

Домашнее задание

Репозиторий шаблонов с домашними заданиями для этого урока находится здесь: https://github.com/HappyCerberus/daily-bite-course-03.

Как и во всех домашних заданиях, вам понадобятся VSCode и Docker, установленные на вашем компьютере, и следуйте инструкциям из первого урока.

Цель состоит в том, чтобы все тесты прошли, как описано в файле readme.