Жадный алгоритм
Данный алгоритм на каждом шаге делает локально оптимальный выбор, надеясь в итоге получить глобально оптимальное решение.
Пример: Дробный Рюкзак
Задача состоит в том, чтобы выбрать, какие предметы, имеющие вес и стоимость, поместить в рюкзак ограниченной ёмкости 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
В чем отличие malloc от new?
Ответ: malloc — выделение блока памяти в стиле Си, опасное с точки зрения приведения типов (non-typesafe), т.к. возвращает void * и требует обязательного приведения. new — выделение блока памяти и последующий вызов конструктора, безопасное с точки зрения приведения типов (typesafe), т.к. тип возвращаемого значения определен заранее.
➡️ @cpp_geek
Ответ: malloc — выделение блока памяти в стиле Си, опасное с точки зрения приведения типов (non-typesafe), т.к. возвращает void * и требует обязательного приведения. new — выделение блока памяти и последующий вызов конструктора, безопасное с точки зрения приведения типов (typesafe), т.к. тип возвращаемого значения определен заранее.
➡️ @cpp_geek
Могут ли статичные функции быть виртуальными в С++?
В C++ статическая функция-член класса не может быть виртуальной. Виртуальные функции вызываются, когда у вас есть указатель или ссылка на экземпляр класса. Статические функции не привязаны к экземпляру класса, но они привязаны к самому классу. C++ не имеет указателей на класс, поэтому нет сценария, в котором вы могли бы виртуально вызвать статическую функцию.
Например, программа с картинки в примере 1 выдаст ошибку во время компиляции.
Кроме того, статическая функция-член класса не может иметь одновременно идентификаторы const и volatile. Код из примера 2 тоже не скомпилируется.
➡️ @cpp_geek
В C++ статическая функция-член класса не может быть виртуальной. Виртуальные функции вызываются, когда у вас есть указатель или ссылка на экземпляр класса. Статические функции не привязаны к экземпляру класса, но они привязаны к самому классу. C++ не имеет указателей на класс, поэтому нет сценария, в котором вы могли бы виртуально вызвать статическую функцию.
Например, программа с картинки в примере 1 выдаст ошибку во время компиляции.
Кроме того, статическая функция-член класса не может иметь одновременно идентификаторы const и volatile. Код из примера 2 тоже не скомпилируется.
➡️ @cpp_geek
В чем разница между указателем и ссылкой в C++?
Указатель может быть переназначен n-раз, в то время как ссылка не может быть переназначена после бинда. Указатели могут указывать в NULL, тогда как ссылка всегда ссылается на объект. Программист не может получить адрес ссылки, как это возможно с указателями, но можно взять адрес объекта, на который указывает ссылка, и выполнить действия с ним.
➡️ @cpp_geek
Указатель может быть переназначен n-раз, в то время как ссылка не может быть переназначена после бинда. Указатели могут указывать в NULL, тогда как ссылка всегда ссылается на объект. Программист не может получить адрес ссылки, как это возможно с указателями, но можно взять адрес объекта, на который указывает ссылка, и выполнить действия с ним.
➡️ @cpp_geek
Функция all_of
Эта функция работает со всем диапазоном элементов массива и может сэкономить время на запуск цикла для проверки каждого элемента по одному. Она проверяет заданное свойство для каждого элемента и возвращает true, когда каждый элемент в диапазоне удовлетворяет указанному свойству, иначе возвращает false.
В приведенном выше коде отрицательный элемент -6 отрицает условие и возвращает false.
➡️ @cpp_geek
Эта функция работает со всем диапазоном элементов массива и может сэкономить время на запуск цикла для проверки каждого элемента по одному. Она проверяет заданное свойство для каждого элемента и возвращает true, когда каждый элемент в диапазоне удовлетворяет указанному свойству, иначе возвращает false.
В приведенном выше коде отрицательный элемент -6 отрицает условие и возвращает false.
➡️ @cpp_geek
Cтрого-типизированный enum
У «традиционных» перечислений в С++ есть некоторые недостатки: они экспортируют свои значения в окружающую область видимости (что может привести к конфликту имен), они неявно преобразовываются в целый тип и не могут иметь определенный пользователем тип.
Эти проблемы устранены в С++11 с введением новой категории перечислений, названных strongly-typed enums. Они определяются ключевым словом enum class. Они больше не экспортируют свои перечисляемые значения в окружающую область видимости, больше не преобразуются неявно в целый тип и могут иметь определенный пользователем тип (эта опция так же добавлена и для «традиционных» перечислений").
➡️ @cpp_geek
У «традиционных» перечислений в С++ есть некоторые недостатки: они экспортируют свои значения в окружающую область видимости (что может привести к конфликту имен), они неявно преобразовываются в целый тип и не могут иметь определенный пользователем тип.
Эти проблемы устранены в С++11 с введением новой категории перечислений, названных strongly-typed enums. Они определяются ключевым словом enum class. Они больше не экспортируют свои перечисляемые значения в окружающую область видимости, больше не преобразуются неявно в целый тип и могут иметь определенный пользователем тип (эта опция так же добавлена и для «традиционных» перечислений").
➡️ @cpp_geek
Что за оператор −−> в С++?
Это старый хитрый вопрос. В С++ нет оператора −−>.
Рассмотрим такой код:
if (p−−>m == 0) f(p);
Выглядит так, как будто и правда есть оператор −−>, и если правильно объявить переменные p и m, то код даже скомпилируется и запустится:
int p = 2;
int m = 0;
if (p−−>m == 0) f(p);
Это означает: если p−− больше чем m (а это так), то надо сравнить результат (true) с нулём. Ну, true != 0, так что результат всего выражения — false, и функция f() не вызовется. Другими словами:
if ((p−−) > m == 0) f(p);
Пожалуйста, не тратьте много времени на подобные вопросы. Они сбивали с толку новичков ещё до того, как появился С++.
➡️ @cpp_geek
Это старый хитрый вопрос. В С++ нет оператора −−>.
Рассмотрим такой код:
if (p−−>m == 0) f(p);
Выглядит так, как будто и правда есть оператор −−>, и если правильно объявить переменные p и m, то код даже скомпилируется и запустится:
int p = 2;
int m = 0;
if (p−−>m == 0) f(p);
Это означает: если p−− больше чем m (а это так), то надо сравнить результат (true) с нулём. Ну, true != 0, так что результат всего выражения — false, и функция f() не вызовется. Другими словами:
if ((p−−) > m == 0) f(p);
Пожалуйста, не тратьте много времени на подобные вопросы. Они сбивали с толку новичков ещё до того, как появился С++.
➡️ @cpp_geek
nullptr
Раньше, для обнуления указателей использовался макрос NULL, являющийся нулем — целым типом, что, естественно, вызывало проблемы (например, при перегрузке функций). Ключевое слово nullptr имеет свой собственный тип std::nullptr_t, что избавляет нас от бывших проблем. Существуют неявные преобразования nullptr к нулевому указателю любого типа и к bool (как false), но преобразования к целочисленных типам нет.
➡️ @cpp_geek
Раньше, для обнуления указателей использовался макрос NULL, являющийся нулем — целым типом, что, естественно, вызывало проблемы (например, при перегрузке функций). Ключевое слово nullptr имеет свой собственный тип std::nullptr_t, что избавляет нас от бывших проблем. Существуют неявные преобразования nullptr к нулевому указателю любого типа и к bool (как false), но преобразования к целочисленных типам нет.
➡️ @cpp_geek
Инициализатор в if и switch
Вам должна понравиться такая возможность из С++17. Теперь вы можете выполнять инициализацию переменных и проверять условие внутри if или switch. Это даёт сделать код более лаконичным и чистым. Общая форма:
if (init-statement(x); condition(x)) {
// some code
}
else { // в else тоже видно x
// some more code
}
➡️ @cpp_geek
Вам должна понравиться такая возможность из С++17. Теперь вы можете выполнять инициализацию переменных и проверять условие внутри if или switch. Это даёт сделать код более лаконичным и чистым. Общая форма:
if (init-statement(x); condition(x)) {
// some code
}
else { // в else тоже видно x
// some more code
}
➡️ @cpp_geek
Что такое класс хранения?
Класс, который определяет срок существования, компоновку и расположение переменных/функций в памяти.
В C ++ поддерживаются такие классы хранения: auto, static, register, extern и mutable.
Обратите внимание, что register устарел для C++11. Для C++17 он был удален и зарезервирован для будущего использования.
➡️ @cpp_geek
Класс, который определяет срок существования, компоновку и расположение переменных/функций в памяти.
В C ++ поддерживаются такие классы хранения: auto, static, register, extern и mutable.
Обратите внимание, что register устарел для C++11. Для C++17 он был удален и зарезервирован для будущего использования.
➡️ @cpp_geek
Кортежи
Как и пара, кортеж представляет собой набор значений фиксированного размера для различных типов данных.
Иногда удобнее использовать std::array вместо кортежа. Такой массив подобен обычному массиву в Си вместе с несколькими функциями стандартной библиотеки C++. Эта структура данных была добавлена в 11 версии C++.
➡️ @cpp_geek
Как и пара, кортеж представляет собой набор значений фиксированного размера для различных типов данных.
Иногда удобнее использовать std::array вместо кортежа. Такой массив подобен обычному массиву в Си вместе с несколькими функциями стандартной библиотеки C++. Эта структура данных была добавлена в 11 версии C++.
➡️ @cpp_geek
this удобно использовать для цепочных вызовов
Мы можем вернуть ссылку на объект, на котором мы вызываем метод класса:
Foo &set(int x) { this->x = x; return *this; }
Здесь метод set возвращает ссылку на объект класса Foo(Foo&). Такая реализация метода позволяет нам писать код, подобный этому:
obj.set(2).set(8);
Это возможно, поскольку первый вызов метода set возвращает указатель на объект obj. Второй метод вызывается на объекте obj, т. е. можно переписать код так:
obj = obj.set(2);
obj = obj.set(8);
➡️ @cpp_geek
Мы можем вернуть ссылку на объект, на котором мы вызываем метод класса:
Foo &set(int x) { this->x = x; return *this; }
Здесь метод set возвращает ссылку на объект класса Foo(Foo&). Такая реализация метода позволяет нам писать код, подобный этому:
obj.set(2).set(8);
Это возможно, поскольку первый вызов метода set возвращает указатель на объект obj. Второй метод вызывается на объекте obj, т. е. можно переписать код так:
obj = obj.set(2);
obj = obj.set(8);
➡️ @cpp_geek
Различие локальной переменной и поля класса с одинаковым именем
Указатель this может быть полезен в случае, когда локальная переменная в методе имеет то же самое имя, что и поле объекта:
void set(int x) { this->x = x; }
Здесь в методе set мы присваиваем полю класса x значение локальной переменной this. Чтобы различить поле класса x и локальную переменную с тем же именем мы используем запись this->x при обращении к полю класса.
➡️ @cpp_geek
Указатель this может быть полезен в случае, когда локальная переменная в методе имеет то же самое имя, что и поле объекта:
void set(int x) { this->x = x; }
Здесь в методе set мы присваиваем полю класса x значение локальной переменной this. Чтобы различить поле класса x и локальную переменную с тем же именем мы используем запись this->x при обращении к полю класса.
➡️ @cpp_geek