А давайте теперь сравним время работы (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

Вводная статья про CPU, системные вызовы, планировщики ОС, запуск процесса линухом, ELF, виртуальная память, fork.

Местами, правда, перебор с деталями (можно смело пропускать код).

Из действительно нового, что я узнала из статьи, это про 5й уровень подкачки.

https://habr.com/ru/articles/755638/

Хм, так и сеть притащат...
https://www.youtube.com/watch?v=-UXHMlAMXNk

По умолчанию, при невозможности выделить память, оператор new возбуждает исключение std::bad_alloc. Однако, избежать исключения можно использовав размещающий оператор new (placement new), передав ему std::nothrow. В таком случае, исключения не будет, но new вернет нулевой указатель (как в Си).

#include <iostream>
#include <new> // std::bad_alloc. std::nothrow

int main()
{
    int* i1;
    try {
       i1 = new int;
    }  catch (const std::bad_alloc & ex) {
        std::cout << "bad alloc";
    }

    int* i2 = new (std::nothrow) int; // nullptr on fail
    if (i2 == nullptr) {
        std::cout << "no memory, use rosmarinus";
    }

    delete i1;
    delete i2;

    return 0;
}

Интересно, что nothrow - это пустой класс и использование его в placement new (который вообще не для этого) выглядит как костыль.

При вызове оператора new объекты инициализируются по умолчанию. То есть как для int i; в результате будет мусор, так и для new int; в результате будет мусор. А вот например new string вызовет конструктор по умолчанию, то есть создаст пустую строку.
Для заполнения динамического значения нулем, следует использовать круглые скобки, при этом круглые скобки можно использовать и с динамическими массивами (что создаст массив из нулей):

#include <iostream>

void fill_heap_with_garbage()
{
    // повышаем вероятность мусора, а не 0
    int* intp = new int(99);
    delete intp;

    int* arrp = new int[42];
    for (size_t i=0; i<42; ++i) arrp[i] = i;
    delete[] arrp;
}

int main()
{

    fill_heap_with_garbage();

    {
        int* i1 = new int; // мусор
        int* i2 = new int(); // 0
        int* i3 = new int(42); // 42

        std::cout << *i1 << " " << *i2 << " " << *i3
                  << std::endl; // 1660576172 0 42

        delete i1;
        delete i2;
        delete i3;
    }

    {
        int* a1 = new int[42]; // мусор
        int* a2 = new int[42](); // нули

        std::cout << a1[10] << " " << a2[10]<< std::endl; // 10 0

        delete[] a1;
        delete[] a2;
    }

    return 0;
}

Интересно, что передать ненулевое значение для единичного объекта можно, а для массива нельзя:

new int(42); // можно, будет 42
new int[100](42) // нельзя

Определить массив нулевой длины в C++ нельзя, sizeof такого массива будет 0. Однако же, динамически выделить массив нулевой длины можно:

#include <iostream>

int main()
{
    constexpr size_t size = 0;

    int a1[0]; // нельзя
    int * a2 = new int[size]; // можно

    std::cout << sizeof(a1) << " " << size_t(a2) << std::endl; // 0 94376700628656

    for (int* i = a2; i != a2 + size; ++i ) {
        std::cout << *i;
    }

    delete[] a2;

    return 0;
}

Такой указатель на пустой массив не будет нулевым, но он будет похож на указатель на элемент после конца массива.
Такой указатель можно сравнивать, добавить и вычесть 0, вычесть из себя. Поэтому цикл выше вполне валиден (он кстати не выполнится).
Конечно же, обращаться к значению такого указателя нельзя.

Немного юмора (осторожно, мат).
https://www.youtube.com/watch?v=Qz1gPxn9mu0
#юмор

Как правило, конструктор копирования (copy constructor) принимает как параметр константную ссылку на свой же тип: Class(const Class & other).
В реальности же, первый параметр может быть обычной (не константной) ссылкой на свой тип (хотя смысла в этом обычно нет). Более того, конструктор копирования может принимать и другие аргументы, главное чтоб они имели значение по умолчанию. Пример:

#include <iostream>

class A
{
public:
    A() = default;
    A(A & other, int i = 10)
    {
        std::cout << "copy ctor " << i << std::endl;
    }
};

void f(A a) // makes copy
{}


int main()
{
    A a;
    f(a);

    return 0;
}

И тут возникает вопрос, а может и ссылка не обязательна? Что если передавать первый аргумент по значению: Class(Class other) ?
Но так делать нельзя, так как для создания копии параметра конструктора копии понадобится вызвать этот же конструктор копии, то есть будет рекурсия. Поэтому первый параметр должен передаваться по ссылке.

Тут на собеседовании спросили какие умные указатели бывают, конечно же unique_ptr, shared_ptr и weak_ptr, про это все знают.
Зачем же нужны weak_ptr? Давайте посмотрим на такой вроде бы игрушечный пример:

#include <iostream>
#include <memory>

class A
{
public:
    std::shared_ptr<A> parent;
    std::shared_ptr<A> callback;
    ~A() 
    {
        std::cout << "~A" << std::endl;
    }
};

void shared_cycle()
{
    std::shared_ptr<A> parent = std::make_shared<A>();
    std::shared_ptr<A> child = std::make_shared<A>();
    child->parent = parent;
    parent->callback = child; // без этой строчки будет ~A ~A
}

int main()
{
    shared_cycle();
    return 0;
};

Из-за циклической зависимости двух объектов деструктор не вызовется!
Конечно же в реальности объекты могут не находиться в коде "рядом" или цикл может быть подлиннее.
Спасением может оказаться weak_ptr, если мы поменяем одну из переменных с shared на weak:
std::weak_ptr<A> callback;

На реддите пишут, что на собесах иногда спрашивают про CRTP. А вы знали, что это такое?)

CRTP (Curiously Recurring Template Pattern, "любопытный повторяющийся шаблон") - это идиома C++, в которой класс наследуется от реализации шаблонного метода, используя сам себя в качестве шаблонного аргумента.
Пример (из википедии 😁) :

template <class T> 
struct Base
{
    void interface()
    {
        // ...
        static_cast<T*>(this)->implementation();
        // ...
    }
};

struct Derived : Base<Derived>
{
    void implementation();
};

Как видим, Derived наследует Base и передает сам себя в качестве шаблона. Отсюда и рекурсия. Немного напоминает class Derived : public std::enable_shared_from_this<Derived>.

Зачем это нужно? Так можно достигнуть поведения, аналогичного виртуальным функциям, но без динамического полиморфизма.

Дальнейшее объяснение слишком длинное, предлагаю для подробностей обратиться к хабру.

shared_ptr обычно реализуется через подсчет ссылок - количества объектов, которые ссылаются на указатель. При копировании shared_ptr количество увеличивается на 1, деструктор уменьшает количество на 1. При достижении числа 0 вызывается deleter (по-умолчанию delete).

Для иллюстрации воспользуемся методом use_count():

#include <iostream>
#include <memory>

int main()
{
    std::shared_ptr<int> shared = std::make_shared<int>(100);

    std::cout << shared.use_count() << std::endl; // 1

    {
        auto shared2 = shared;
        std::cout << shared.use_count() << std::endl; // 2
    }

    std::cout << shared.use_count() << std::endl; // 1

    std::weak_ptr<int> weak = shared;

    std::cout << shared.use_count() << std::endl; // 1

    if (auto shared3 = weak.lock()) { // получить shared_ptr из weak_ptr
        std::cout << shared.use_count() << std::endl; // 2
    }

    std::cout << shared.use_count() << std::endl; // 1

    shared.reset(); // чистим

    std::cout << shared.use_count() << std::endl; // 0

    auto shared4 = weak.lock();
    if (shared4 == nullptr) {
        std::cout << "can't lock";
    }

    return 0;
}

// Output:
// 1
// 2
// 1
// 1
// 2
// 1
// 0
// can't lock

Как видим, weak_ptr создается из shared_ptr, но не увеличивает число shared_ptr, указывающих на этот объект. На самом деле, для weak_ptr имеется отдельный счетчик ссылок, он изменяется при создании "слабой" ссылки.

Для получения указателя из weak_ptr необходимо вызвать метод lock(), который вернет соответствующий shared_ptr, что увеличит число ссылок. Другого способа аналогичного методу get() для получения значения указателя из weak_ptr нет.

weak_ptr может спокойно пережить свой shared_ptr и это безопасно с ним работать после удаления соотв. указателя, но в таком случае lock() вернет указатель на nullptr.

Давайте углубимся в детали реализации shared_ptr и может быть немного повторимся.

В типичной реализации, shared_ptr содержит 2 указателя:
- собственно хранимый указатель (тот, что вернет метод get())
- указатель на управляющий блок (control block)

Управляющий блок - это динамически выделяемый объект, который содержит:
- или указатель на управляемый объект (да да, еще один указатель) или сам управляемый объект (подробности дальше)
- deleter
- аллокатор
- число shared_ptr-ов, которые владеют управляемым объектом
- число weak_ptr ("слабый" счетчик), которые владеют управляемым объектом

Когда shared_ptr создается с помощью std::make_shared(), то память под управляющий блок и сам объект создается одним выделением. Управляемый объект создается "на месте" в самом управляющем блоке. Если же создавать shared_ptr через конструктор, то управляемый блок и управляемый объект выделяются отдельно и управляющий блок хранит указатель на объект.

Кстати, вот что пишет Скотт Мэйерс про счетчик ссылок weak_ptr: "На практике значение слабого счетчика не всегда совпадает с количеством указателей std::weak_ptr, ссылающихся на управляющий блок, поскольку разработчики библиотеки нашли способы добавлять в слабый счетчик дополнительную информацию, которая упрощает генерацию лучшего кода". И да, для проверки просроченности указателя, weak_ptr пользуется "обычным" счетчиком ссылок, а не "слабым".

А вот сейчас жесть: указатель, хранимый shared_ptr непосредственно - это тот, который вернется методом get(), тогда как указатель, хранимый управляющим блоком, этот тот, который будет удален когда число шарных указателей достигнет нуля. Эти указатели необязательно равны (хотя с такой ситуацией вы вряд ли столкнетесь)! Если вы ничего не поняли, то это ок , но детали тут.

Деструктор шарного указателя уменьшает число шарных владельцев в контрольном блоке. Если это число падает до нуля, то контрольный блок вызывает деструктор управляемого объекта. Контрольный блок не удаляет сам себя до тех пор. пока и число weak_ptr не упадет до нуля (если weak_ptr не было, то их число сразу 0 и контрольный блок уничтожится).