В чем отличие vector от deque?
Ответ: Здесь вспоминают о наличии у deque методов push_front и pop_front. Но основное отличие в организации памяти, у vector она как у обычного Си-массива, т.е. последовательный и непрерывный набор байт, а у deque это фрагменты с разрывами. За счет этого отличия vector всегда можно привести к обычному массиву или скопировать целиком участок памяти, но зато у deque операции вставки/удаления в начало быстрее (O(1) против O(n)), ввиду того, что не нужно перемещать.
➡️ @cpp_geek
Ответ: Здесь вспоминают о наличии у deque методов push_front и pop_front. Но основное отличие в организации памяти, у vector она как у обычного Си-массива, т.е. последовательный и непрерывный набор байт, а у deque это фрагменты с разрывами. За счет этого отличия vector всегда можно привести к обычному массиву или скопировать целиком участок памяти, но зато у deque операции вставки/удаления в начало быстрее (O(1) против O(n)), ввиду того, что не нужно перемещать.
➡️ @cpp_geek
Для чего используется ключевое слово volatile?
Для указания компилятору, что доступ к переменной может осуществляться из мест, неподконтрольных ему. А как следствие, что работу с данной переменной не нужно подвергать разного рода оптимизациям.
Т.е. если volatile присутствует в каком-то условии, которое не меняется со временем, то компилятор может оптимизировать его, чтобы избежать ненужных проверок, при использовании volatile компилятор скорее всего не будет этого делать.
➡️ @cpp_geek
Для указания компилятору, что доступ к переменной может осуществляться из мест, неподконтрольных ему. А как следствие, что работу с данной переменной не нужно подвергать разного рода оптимизациям.
Т.е. если volatile присутствует в каком-то условии, которое не меняется со временем, то компилятор может оптимизировать его, чтобы избежать ненужных проверок, при использовании volatile компилятор скорее всего не будет этого делать.
➡️ @cpp_geek
Шаблон Voodoo
Вы можете настраивать шаблоны класса под конкретные значения или типы аргументов: так работает специализация шаблонов классов C++. Если это рекурсия, можно записывать базовые случаи, а затем определить общий шаблон как рекурсивную комбинацию этих случаев.
➡️ @cpp_geek
Вы можете настраивать шаблоны класса под конкретные значения или типы аргументов: так работает специализация шаблонов классов C++. Если это рекурсия, можно записывать базовые случаи, а затем определить общий шаблон как рекурсивную комбинацию этих случаев.
➡️ @cpp_geek
Вывод параметра шаблона класса
Довольно странное название функции, да? Её суть в том, что с C++17 компилятор может сам определять типы аргументов конструкторов стандартных классов. Раньше же это работало лишь для функций.
Для того, чтобы осознать удобство этой функции, нужно быть знакомыми с конструкторами классов в C++.
➡️ @cpp_geek
Довольно странное название функции, да? Её суть в том, что с C++17 компилятор может сам определять типы аргументов конструкторов стандартных классов. Раньше же это работало лишь для функций.
Для того, чтобы осознать удобство этой функции, нужно быть знакомыми с конструкторами классов в C++.
➡️ @cpp_geek
Программирование на С++ и URI в коде
Вы можете поместить URI в свой код на C++, и компилятор не выдаст ошибку. Любой идентификатор, за которым следует двоеточие, становится меткой goto в С++. Все, что следует за двойным слешем, воспринимается как комментарий. Именно поэтому в приведенном выше коде http – это метка, а //google.com/ – комментарий. Но компилятор может выдать предупреждение, так как заданная метка не используется.
➡️ @cpp_geek
Вы можете поместить URI в свой код на C++, и компилятор не выдаст ошибку. Любой идентификатор, за которым следует двоеточие, становится меткой goto в С++. Все, что следует за двойным слешем, воспринимается как комментарий. Именно поэтому в приведенном выше коде http – это метка, а //google.com/ – комментарий. Но компилятор может выдать предупреждение, так как заданная метка не используется.
➡️ @cpp_geek
Что такое чисто виртуальный метод и абстрактный класс?
Ответ: Чисто виртуальный метод — это метод, у которого отсутствует реализация. Абстрактный класс — это класс имеющий хотя бы один чисто виртуальный метод. Как следствие, экземпляр подобного класса не может быть создан т.к. отсутствует реализация виртуального метода.
➡️ @cpp_geek
Ответ: Чисто виртуальный метод — это метод, у которого отсутствует реализация. Абстрактный класс — это класс имеющий хотя бы один чисто виртуальный метод. Как следствие, экземпляр подобного класса не может быть создан т.к. отсутствует реализация виртуального метода.
➡️ @cpp_geek
Автовыведение типа
Несмотря на то, что ключевое слово auto было введено еще в C++11, многие программисты продолжают его игнорировать. А ведь автовыведение позволяет экономить время и делает код лаконичным.
Увидеть преимущества можно даже на примере стандартных типов STL.
➡️ @cpp_geek
Несмотря на то, что ключевое слово auto было введено еще в C++11, многие программисты продолжают его игнорировать. А ведь автовыведение позволяет экономить время и делает код лаконичным.
Увидеть преимущества можно даже на примере стандартных типов STL.
➡️ @cpp_geek
Сортировка пузырьком
Определите, сколько обменов сделает алгоритм пузырьковой сортировки по возрастанию для данного массива.
Формат входных данных:
На первой строке дано целое число n (1 ≤ n ≤ 1000) – количество элементов в массиве. На второй строке – сам массив. Гарантируется, что все элементы массива – различные целые числа, не превышающие по модулю 10^9.
Формат выходных данных:
Выведите одно число – количество обменов пузырьковой сортировки.
➡️ @cpp_geek
Определите, сколько обменов сделает алгоритм пузырьковой сортировки по возрастанию для данного массива.
Формат входных данных:
На первой строке дано целое число n (1 ≤ n ≤ 1000) – количество элементов в массиве. На второй строке – сам массив. Гарантируется, что все элементы массива – различные целые числа, не превышающие по модулю 10^9.
Формат выходных данных:
Выведите одно число – количество обменов пузырьковой сортировки.
➡️ @cpp_geek
This media is not supported in your browser
VIEW IN TELEGRAM
Дерево Фенвика
Довольно простая и быстрая, но совсем не очевидная в плане идеи и понимания структура данных. Позволяет находить сумму на префиксе и изменять отдельные элементы за O(log n). В следующем посте — реализация на C++.
➡️ @cpp_geek
Довольно простая и быстрая, но совсем не очевидная в плане идеи и понимания структура данных. Позволяет находить сумму на префиксе и изменять отдельные элементы за O(log n). В следующем посте — реализация на C++.
➡️ @cpp_geek
Структура представлена в виде массива f, в котором f[i] – сумма всех элементов от F[i] до i. Функция F(x) связана с битовым представлением аргумента. Вкратце можно описать так: F(x) заменяет группу единичных битов, находящихся в конце числа (младших) на нули. Если x заканчивается на нулевой бит, то F(x) = x. В битовых операциях F(x) задаётся так: F(x) = x & (x + 1).
Нам понадобятся три функции: прибавление x к элементу с индексом i, получение суммы дерева от 0до xи получение суммы на [a..b].
➡️ @cpp_geek
Нам понадобятся три функции: прибавление x к элементу с индексом i, получение суммы дерева от 0до xи получение суммы на [a..b].
➡️ @cpp_geek
Быстрая сортировка
Отсортируйте заданный массив с помощью быстрой сортировки.
Формат входных данных:
Первая строка входных данных содержит одно натуральное число nn (1 ≤ n ≤ 10^5) – количество элементов в массиве. В следующей строке находятся элементы массива – n целых чисел, не превосходящих по абсолютной величине 10^9.
Формат выходных данных:
Выведите элементы массива в порядке неубывания.
➡️ @cpp_geek
Отсортируйте заданный массив с помощью быстрой сортировки.
Формат входных данных:
Первая строка входных данных содержит одно натуральное число nn (1 ≤ n ≤ 10^5) – количество элементов в массиве. В следующей строке находятся элементы массива – n целых чисел, не превосходящих по абсолютной величине 10^9.
Формат выходных данных:
Выведите элементы массива в порядке неубывания.
➡️ @cpp_geek
Корень числа
Дано действительное число a и натуральное n. Вычислите корень n-й степени из числа a, используя вещественный бинарный поиск.
Формат входных данных:
С клавиатуры через пробел вводится два числа:
1. a – действительное, неотрицательное, не превосходит 1000, задано с точностью до 6 знаков после десятичной точки;
2. n – натуральное, не превосходящее 10.
Формат выходных данных:
Требуется вывести число с точностью не менее 6 знаков после запятой.
➡️ @cpp_geek
Дано действительное число a и натуральное n. Вычислите корень n-й степени из числа a, используя вещественный бинарный поиск.
Формат входных данных:
С клавиатуры через пробел вводится два числа:
1. a – действительное, неотрицательное, не превосходит 1000, задано с точностью до 6 знаков после десятичной точки;
2. n – натуральное, не превосходящее 10.
Формат выходных данных:
Требуется вывести число с точностью не менее 6 знаков после запятой.
➡️ @cpp_geek
Жадный алгоритм
Данный алгоритм на каждом шаге делает локально оптимальный выбор, надеясь в итоге получить глобально оптимальное решение.
Пример: Дробный Рюкзак
Задача состоит в том, чтобы выбрать, какие предметы, имеющие вес и стоимость, поместить в рюкзак ограниченной ёмкости W, да так, чтобы максимизировать общую ценность его содержимого. Мы можем определить соотношение стоимости предмета к его весу, т. е. с «жадностью» выбирать предметы, имеющие высокую стоимость, но в то же время маленький вес, а затем сортировать их по этим критериям. В задаче с дробным рюкзаком нам разрешено брать дробные части предмета.
Поскольку сортировка — самая дорогая операция, алгоритм работает за время O(n log n). Принимая в формате (стоимость, вес) три пары предметов — {(60, 10), (100, 20), (120, 30)} — и итоговую вместительность рюкзака W = 50, приведённый выше код выводит следующее:
жадный дробный рюкзак
максимальная ценность: 240.
➡️ @cpp_geek
Данный алгоритм на каждом шаге делает локально оптимальный выбор, надеясь в итоге получить глобально оптимальное решение.
Пример: Дробный Рюкзак
Задача состоит в том, чтобы выбрать, какие предметы, имеющие вес и стоимость, поместить в рюкзак ограниченной ёмкости W, да так, чтобы максимизировать общую ценность его содержимого. Мы можем определить соотношение стоимости предмета к его весу, т. е. с «жадностью» выбирать предметы, имеющие высокую стоимость, но в то же время маленький вес, а затем сортировать их по этим критериям. В задаче с дробным рюкзаком нам разрешено брать дробные части предмета.
Поскольку сортировка — самая дорогая операция, алгоритм работает за время O(n log n). Принимая в формате (стоимость, вес) три пары предметов — {(60, 10), (100, 20), (120, 30)} — и итоговую вместительность рюкзака W = 50, приведённый выше код выводит следующее:
жадный дробный рюкзак
максимальная ценность: 240.
➡️ @cpp_geek
Неиспользуемые переменные
Подобный макрос есть, например, в cocos2d-x, там он называется CC_UNUSED_PARAM. Из недостатков: теоретически, он может работать не на всех компиляторах. Тем не менее, в cocos2d-x он для всех платформ определен абсолютно одинаково.
Для чего? Этот макрос позволяет избежать предупреждения о неиспользуемой переменной, а читающему код он как бы говорит: «тот кто писал это — знал, что переменная не используется, все в порядке».
➡️ @cpp_geek
Подобный макрос есть, например, в cocos2d-x, там он называется CC_UNUSED_PARAM. Из недостатков: теоретически, он может работать не на всех компиляторах. Тем не менее, в cocos2d-x он для всех платформ определен абсолютно одинаково.
Для чего? Этот макрос позволяет избежать предупреждения о неиспользуемой переменной, а читающему код он как бы говорит: «тот кто писал это — знал, что переменная не используется, все в порядке».
➡️ @cpp_geek