Давайте рассмотрим на первый раз простую задачу - итерирование вектора в обратном порядке, то есть от конца к началу. Для начала возьмем просто индекс:

    std::vector<int> v = {1,2,3,4,5};
    const std::vector<int>::size_type size = v.size();

    int i;
    for (i = size - 1; i != -1; --i) {
        std::cout << v[i]; // 54321
    }
    std::cout << std::endl << i << std::endl; // -1

Вроде бы все хорошо, но на моей машине в int максимум поместится 2147483647, тогда как в size_type вектора (обычно size_t) уже 18446744073709551615.
Давайте исправим ситуацию и возьмем size_t в качестве индекса:

    size_t j;
    for (j = size - 1; j != -1; --j) {
        std::cout << v[j]; // 54321
    }
    std::cout << std::endl << j << std::endl; // 18446744073709551615

А есть ли способ лучше, через итераторы? Да - реверсивный итератор перебирает контейнер с конца в начало. Для этого доступны rbegin/rend:

    for (auto it = v.rbegin(); it != v.rend(); ++it) {
        std::cout << *it;
    }

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

Так как реверсивный итератор перебирает контейнер от последнего элемента к первому, то смысл инкремента инвертирован: ++it переводит итератор на предыдущий элемент, а --it на следующий.

Для получения реверсивного итератора существуют rbegin()/rend(), а также константные аналоги crbegin()/crend(). rbegin указывает на последний элемент контейнера, а rend на элемент перед контейнером, аналогично обычным итераторам, просто наоборот. Изображение пояснит соотношение на векторе.

Возможно, вам покажется неправильным, что ++it идет на предыдущий элемент, но это позволяет использовать все стандартные алгоритмы задом наперед. Например, отсортируем вектор в порядке убывания:
std::sort(v.rbegin(), v.rend())

Заканчиваем с реверсивными итераторами. Допустим, что нам нужно найти первое и последнее слово в строке. С первым всё понятно, используем std::find с начала:

    std::string str = "One Two Three";
    auto space = std::find(str.cbegin(), str.cend(), ' ');
    std::cout 
        << std::string(str.cbegin(), space) // One
        << std::endl; 

Для поиска с конца ищем реверсивно с конца по начало, итератор правильно находится на 8-й позиции, но при получении подстроки слово будет задом наперед:

    auto rspace = std::find(str.crbegin(), str.crend(), ' ');

    std::cout 
        << str.crend() - rspace // at 8, correct
        << std::endl;

    std::cout
        << std::string(str.crbegin(), rspace) // eerhT
        << std::endl;

Почему? Потому что итератор идет в обратном направлении. Для перехода на прямое направление используем вызов base() у реверсивного итератора:

    std::cout
        << std::string(rspace.base(), str.cend()) // Three
        << std::endl;

Обратите внимание, что в паре с base() идет обычный итератор.

Боян, но все равно смешно)
https://stackoverflow.com/questions/1642028/what-is-the-operator-in-c-c?rq=2
#stackoverflow #юмор

std::list определяет несколько алгоритмов в качестве членов, например sort(), merge(), reverse(), unique(). Обобщенная версия std::sort (та, которая принимает итераторы) требует итераторы произвольного доступа, которых нет в list, поэтому std::sort нельзя использовать с list. Вместо этого следует вызывать член sort() у самого list.

Давайте ради интереса проверим скорость сортировки вектора и списка из 100 тысяч int-ов:

#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
#include <chrono>

constexpr int sortSize = 100'000;

int main()
{
    std::list<int> list;
    for (int i = sortSize; i > 0 ; --i) {
        list.push_back(i);
    }

    auto begin1 = std::chrono::steady_clock::now();

    //std::sort(list.begin(), list.end()); // не скомпилится
    list.sort(); // скомпилится

    auto end1 = std::chrono::steady_clock::now();

    std::vector<int> vector;
    vector.resize(sortSize);
    for (int i = sortSize; i > 0; --i) {
        vector[sortSize - i] = i;
    }

    auto begin2 = std::chrono::steady_clock::now();

    std::sort(vector.begin(), vector.end());

    auto end2 = std::chrono::steady_clock::now();

    auto it_l = list.begin();
    for (size_t i = 0; i < 10; ++i) {
        std::cout << *it_l++ << " "; // 1 2 3 4 5 6 7 8 9 10
    }

    std::cout << std::endl;

    auto it_v = vector.begin();
    for (size_t i = 0; i < 10; ++i) {
        std::cout << *it_v++ << " "; // 1 2 3 4 5 6 7 8 9 10
    }

    std::cout << std::endl;

    std::cout << "list:   "
        << std::chrono::duration_cast<std::chrono::microseconds>(end1 - begin1).count()
        << " mcs"
        << std::endl;

    std::cout << "vector: "
        << std::chrono::duration_cast<std::chrono::microseconds>(end2 - begin2).count()
        << " mcs"
        << std::endl;

    // list:   1717 mcs
    // vector : 958 mcs

    return 0;
}

На MSVC на моей тачке (x86_64) получилось, что сортировка списка в 1.8 раза медленней сортировки вектора (если я нигде не обосралась). А почему так, думаю догадаются многие 😁.

Начиная с C++17 if может быть с инициализатором`if (init; condition)` (подобно for). Переменная доступна только внутри if :

#include <iostream>
#include <cstdlib>
#include <vector>

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

    // C++17 if statement with initializer
    // if (init; condition) {
    if (auto it = std::find(v.begin(), v.end(), 5); it != v.end()) {
        std::cout << *it << std::endl;
    }

    srand(time(NULL));

    if (int random = rand(); random % 2 == 0) {
        std::cout << random << " is an even number" << std::endl;
    } else {
        std::cout << random << " is an odd number" << std::endl;
    }

    return 0;
}

Во втором примере показано, что переменная также доступна в else.

#cpp17

Классический пример использования ассоциативного контейнера std::map - подсчет числа слов в строке.

#include <iostream>
#include <map>
#include <string>
#include <sstream>
#include <iomanip>

int main() 
{
    std::string str = 
        "the only person with whom you have to"
        " compare yourself is you in the past";

    std::stringstream stream(str);

    // счетчик числа слов: string - ключ, size_t - значение
    std::map<std::string, size_t> wordCount;

    std::string word;
    while (stream >> word) { // разделяем слова по пробелам
        ++wordCount[word]; // добавляем слово или берем уже сущ.
    }

    std::cout << wordCount["the"] << std::endl; // 2

    for (auto w : wordCount) { // w - pair
        std::cout << std::setw(10) << w.first << ": " 
            << w.second << std::endl;
    }

    //       with: 1
    //        you: 2
    //        ...

    return 0;
}

Для ассоциативного контейнера нужно задать типы ключа (строка - слово) и значения (число слов).
Вызов wordCount[word] добавит слово в мапу со значением 0, если такого слова нет.
++wordCount[word] увеличит значение в мапе на 1.
wordCount["the"] вернет количество the.

При итерации по словарю будет возвращен std::pair, гдe first - это ключ, а second - значение.

На собеседованиях по алгоритмам часто спрашивают, как обратить список. Ответ: вызывать метод reverse() 😆

#include <iostream>
#include <list>

int main() 
{
    std::list<int> l;
    for (int i = 0; i < 5; ++i) l.push_back(i);

    // 0 1 2 3 4
    for (int i : l) std::cout << i << " ";
    std::cout << std::endl;

    l.reverse();

    // 4 3 2 1 0
    for (int i : l) std::cout << i << " ";
    std::cout << std::endl;

    return 0;
}

#юмор

А давайте теперь сравним время работы (MSVC 64 bit) обобщенной версии remove_if и встроенной в std::list на примере удаления всех четных элементов из списка на 100 тысяч int-ов:

#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
#include <chrono>

int main()
{
    std::list<int> list;
    for (int i = 0; i < 100'000; ++i) {
        list.push_back(i);
    }

    // сделаем копии
    std::list<int> list_copy1 = list;
    std::list<int> list_copy2 = list;

    auto begin1 = std::chrono::steady_clock::now();

    std::remove_if(
        list_copy1.begin(), 
        list_copy1.end(), 
        [](int n) { return n % 2 == 0; });

    auto end1 = std::chrono::steady_clock::now();

    auto begin2 = std::chrono::steady_clock::now();

    list_copy2.remove_if([](int n) { return n % 2 == 0; });

    auto end2 = std::chrono::steady_clock::now();

    auto it1 = list_copy1.begin();
    for (size_t i = 0; i < 10; ++i) {
        std::cout << *it1++ << " "; // 1 3 5 7 9 11 13 15 17 19
    }

    std::cout << std::endl;

    auto it2 = list_copy2.begin();
    for (size_t i = 0; i < 10; ++i) {
        std::cout << *it2++ << " "; // 1 3 5 7 9 11 13 15 17 19
    }

    std::cout << std::endl;

    std::cout << "1: " 
        << std::chrono::duration_cast<std::chrono::microseconds>(end1 - begin1).count() 
        << " mcs"
        << std::endl;

    std::cout << "2: "
        << std::chrono::duration_cast<std::chrono::microseconds>(end2 - begin2).count()
        << " mcs"
        << std::endl;

    // 1: 710 mcs
    // 2: 1631 mcs

  return 0;
}

Обобщенный в 2 раза быстрее, что?😱

std::set - это ассоциативный контейнер, который хранит отсортированный набор уникальных объектов (то есть отсортированное множество).

Для проверки наличия элемента во множестве предназначен метод find(), который вернет end(), если такого элемента нет.

Однако начиная с c++20 доступен сахар в виде метода contains(), который более читаем:

#include <iostream>
#include <set>

int main() 
{
    std::set<int> setOfInts{ 1, 2, 3, 4, 5};

    if (setOfInts.find(7) == setOfInts.end()) {
        std::cout << "Set doesn't contain 7" << std::endl;
    }

    // Начиная с C++20:
    if (setOfInts.contains(3)) {
        std::cout << "Set contains 3" << std::endl;
    } else {
        std::cout << "Set doesn't contain 3" << std::endl;
    }

    return 0;
}

Оба метода — log(N)
#cpp20

std::set хранит ключи в отсортированном виде. Сортируются сами значения, а не порядок их добавления! Ниже показаны два примера с целочисленными и строковыми множествами.
std::unordered_set не хранит ключи в каком-то определенном порядке, разницу с std::set можно увидеть ниже (результат может отличаться).

#include <iostream>
#include <set>
#include <unordered_set>
#include <vector>
#include <string>

void print_int_set()
{
    std::set<int> s{ 5, 3, 1, 4, 2, 1 };

    s.insert(0);

    for (auto i : s) { // 0 1 2 3 4 5
        std::cout << i << " ";
    }
    std::cout << std::endl;
}

void print_str_set()
{
    std::vector<std::string> v{ "b", "c", "a" };
    std::set<std::string> sv(v.cbegin(), v.cend());

    for (auto is : sv) { // a b c
        std::cout << is << " ";
    }
    std::cout << std::endl;
}

void print_unordered_int_set()
{
    std::unordered_set<int> us{ 5, 3, 1, 4, 2, 1 };
    us.insert(0);

    for (auto i : us) { // 5 3 1 4 2 0 - may differ!
        std::cout << i << " ";
    }
    std::cout << std::endl;
}

int main() 
{
    print_int_set();
    print_str_set();
    print_unordered_int_set();

    return 0;
}

10 архитектурных стилей программного обеспечения и их паттерны

https://systems.education/software_styles_and_patterns_with_cheatsheet

#архитектура #паттерны

Структурное связывавание (structured binding) - начания с C++17 позволяет распаковать сложные типы данных. Рассмотрим пример получения значений переменных кортежа (tuple) без использования std::tie:

#include <iostream>
#include <tuple>

std::tuple<char, int, bool> getTuple()
{
    return std::make_tuple('a', 777, true);
}

int main()
{
    auto [a, i, b] = getTuple();

    std::cout << a << " " << i << " " << b; // a 777 1

    return 0;
}

Кстати, определение функции можно также сократить через auto:

auto getTuple2()
{
    return std::make_tuple('b', 123, false);
}

#cpp17

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

#include <iostream>

struct Size {
    size_t width = 0;
    size_t height = 0;
};

Size getSize()
{
    return { 1920, 1080 };
}

int main()
{
    auto [w, h] = getSize();

    std::cout << w << " " << h; // 1920 1080

    return 0;
}

#cpp17

Структурное связывание можно использовать для упрощения итерирования по std::map, например вместо использования std::pair c first и second, можно написать for (const auto&[key, value] : map) {

#include <iostream>
#include <iomanip>
#include <map>
#include <string>


int main()
{
    std::map<std::string, int> olivie = {
        {"potato"     , 4},
        {"carrot"     , 1},
        {"eggs"       , 4},
        {"canned peas", 1},   // cans
        {"mayo"       , 3},   // spooons
        {"sausage"    , 300}, // grams
        {"pickles"    , 4}
    };

    for (const auto& item : olivie) {
        std::cout << std::setw(15) << item.first // key
                  << " x " << item.second; //value
        std::cout << std::endl;
    }

    std::cout << std::endl;

    for (const auto& [key, value] : olivie) {
        std::cout << std::setw(15) << key
                  << " x " << value;
        std::cout << std::endl;
    }

    return 0;
}

Начиная с с++17 можно опустить типы шаблона при вызове конструктора:

#include <iostream>
#include <utility> // pair
#include <string>


int main()
{
    std::pair<int, std::string> p1{1, "abc"};

    std::cout << p1.first << " " << p1.second << std::endl;

    // с++17
    std::pair p2{1, "abc"};

    std::cout << p1.first << " " << p1.second;

    return 0;
}

Кстати, std::pair объявлен в <utility>

std::binary_search осуществляет бинарный поиск по контейнеру, поэтому:
1) требует отсортированный контейнер
2) имеет логарифмическую сложность

Внезапная особенность его работы в том, что возвращает он не итератор (т.е. не позицию), а bool - есть ли элемент в контейнере. Получить позицию с помощью binary_search не получится.
Ниже пример работы на отсортированном и неотсортированном векторе (во втором случае поиск работает некорректно).

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

int main()
{
    std::vector<int> primes = { 
        2, 3, 5, 7, 11, 13, 17, 19, 
        23, 29, 31, 37, 41, 43, 47, 
        53, 59, 61, 67, 71, 73, 79, 
        83, 89, 97 };

    if (std::binary_search(primes.begin(), primes.end(), 42))
        std::cout << "42 is a prime number" << std::endl;
    else
        std::cout << "42 is not a prime number," // <= туть
                     " how it could be the answer?" << std::endl;

    std::vector notSorted = { 1,2,3,5,6,7,4,8,9 };

    // WRONG! not sorted
    if (!std::binary_search(notSorted.begin(), notSorted.end(), 4)) {
        std::cout << "4 not found" << std::endl; // <= туть
    }

    return 0;
}

​Удаленные функции

Упоминали об этом вскользь, но, думаю, что стоит подсветить эту тему отдельно.

Все мы знаем, что, если нам нужно запретить объекту копироваться, то нужно пометить его копирующий конструктор и копирующий оператор присваивания как =delete;

Но помечать удаленной можно вообще любую функцию!

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

Допустим, у вас есть класс Duration(зачем он вам нужен это большой вопрос, но для примера покатит). Он отвечает за репрезентацию разницы в датах в миллисекундах. Легко можно представить необходимость переопределить оператор + для этого класса, чтобы эту длительность увеличивать за счет обычного числа. Итак пишем:

Duration& Duration::operator+(int num) {
duration_ += num;
return *this;
}

Все хорошо. А если мы туда передадим 5.5? Дробное число неявно преобразуется к инту и мы получим не совсем тот ответ, который могли бы ожидать. И единственный способ запретить такое поведение - объявить нежелательные перегрузки, как =delete.

Duration& Duration::operator+(double num) = delete;
Duration& Duration::operator+(bool num) = delete;

Удаление первой перегрузки также отбросит и float варинт, так как компилятор предпочтет преобразовать float к double, а не к int.

Какая-то выдуманная проблема, скажите вы, и решить ее можно через sfinae. Просто через шаблон запретить подстановки ненужных типов. Благо с 17-х плюсов пользоваться шаблонами стало попроще с помощью CTAD и не надо никакие шаблонные аргументы указывать. Давайте посмотрим, как это выглядит:

template<class T, typename std::enable_if<std::is_integral<T>::value, int>::type = 0>
Duration& Duration::operator+(T num) {
duration_ += num;
return *this;
}

Здесь проверяется, что тип должен быть числом, и только тогда метод сможет инстанцироваться. В чем проблема? Проблема в том, что bool - тоже целочисленный тип. Как же быть? Ровно так же:

template<>
Duration& Duration::operator+(bool num) = delete;

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

Какова мораль. Используйте удаленные функции, когда это необходимо. И шаблонную, и обычную, и виртуальную функцию можно удалить. Это очень гибкий инструмент, предотвращающий неправильное использование вашего класса.

Stay safe. Stay cool

#cpp11 #cpp17 #goodpractice