Ответы пользователя по тегу C++
  • Почему переопределение метода без virtual -- это не переопределение?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Это получается не переопределение, а просто метод у другого типа с таким же названием. Изначальный метод все еще можно вызвать у объекта класса (если привести тип). Также изначальный меотд доступен внутри класса потомка.

    Суть переопределения в том, что это ПЕРЕопределение. Замена одной функциональности на другую. Без virtual этого не происходит.

    Можно же объявить функцию fn у двух совсем не связанных классов, вызвать ее у двух экземпляров и увидеть разный результат, правда? Но тут нет никакого переопределения. Концептуально у вас тут то же самое.
    Ответ написан
    7 комментариев
  • Как вернуть несколько значений из функции?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Кроме параметров функции, можно возвращать структуру с именованными значениями или std::vector или std::touple.
    Ответ написан
    5 комментариев
  • Как не обрезать стркоу после \0?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Все sendto, что я знаю, принимают указатель и размер в байтах. Именно из-за возможности нулевых байт.
    Ответ написан
    Комментировать
  • Почему возникает ошибка 'std::out_of_range'?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Запустите программу в дебагерре и у вас покажется, где именно выскачило исключение.
    Если прочитать текст и перевести на русский, то получается, что у вас есть какой-то пустой вектор и вы обращаетесь к нулевому элементу.

    Скорее всего, это происходит на строчке:
    result = num.at(0);
    Ответ написан
    Комментировать
  • Почему в С++ появляется Segmentation fault?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    head - указатель, который вы инициализируете 0. Потом вы пытаетесь обратиться к полю sizeOfChild по этому указателю, вот тут все и падает. Потому что поля нет, как нет и всего head - вы же под него память не выделяли.
    Ответ написан
    Комментировать
  • Как пару в очередь добавить?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    q.push(make_pair(x,y));
    // или эффективнее.
    q.emplace(x,y);
    Ответ написан
    3 комментария
  • Проблема с преобразование с char в int?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Проблема с win api: https://learn.microsoft.com/en-us/windows/win32/in...

    Оно ожидает вот такие коды. И, если для заглавных английских букв оно еще совпадает с кодами ascii, то для строчных букв - нет.
    Ответ написан
  • Ошибка unresolved external symbol с конструктором/деструктором в классе?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Как компилируете-то? Пока похоже, что вы пытаетесь собрать исполнительный файл прямо из main.cpp, где через include обхявлен класс, но определение все лежит в другом модуле трансляции, который вообще в команде не учавствует.

    Или пользуйтесь системой сборки (cmake, visual studio, ninja, и т.д...) или вручную запускайте 3 команды: сделать объектник из main.cpp, сдлеать объектник из EcsSystems.cpp, собрать из объектников исполняемый файл.
    Ответ написан
    Комментировать
  • Как понять запись кода?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Этот код считает в массиве number, сколько раз каждое число встретилось в массиве moda. Да, числа из массива Moda используются как индексы в number. В результате, в number по каждому индексу будет лежать количество вхождений этого индекса в исходный массив.
    Ответ написан
    2 комментария
  • Как найти бинарное дерево с заданной структурой в изначальном дереве?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Судя по комментариям, вам надо найти полное совподение поддерева: Так что поддерево вершины имеет ровно столько же точно также расставленных вершин, как и второе дерево.

    Умное и быстрое решение, к сожалению, будет сложно написать без std::unordered_map. Такое решение будет работать за O(n). Самостоятельно хеш таблицу писать будет сложно. Но если без хеш таблицы, то решение будет работать также медленно, как и тупое рекурсивное прикладывание, поэтому приведу тут все решение.

    Основная идея - надо классифицировать все вершины по форме их поддеревьев. Назначить каждой форме номер. Потом остается только найти вершины с тем же номером, что и корень второго дерева.

    Для нумерации форм надо рекурсивно получить номера для двух детей и потом проверить, а встречали ли вы раньше вершину с двумя такими детьми. Если да - то вы знаете ее номер. Если нет - то назначьте новый номер. Вот тут и нужена хеш таблица, она же unordered_map.

    Пустые вершины всегда имеют какой-то номер, допустим, 0.

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

    void Match(Tree *stack, Tree *needle) {
      std::unordered_map<std::pair<int, int>, int> shapes;
      int needle_shape = ClassifyShape(needle, shapes, -1);
      ClassifyShape(stack, shapes, needle_shape);
    }
    
    int ClassifyShape(Tree *tree, std::unordered_map<std::pair<int, int>, int> &shape, int find_shape) {
      if(!tree) return 0;
      int l = ClassifyShape(tree->left);
      int r = ClassifyShape(tree->right);
      auto pat = make_pair(l, r);
      auto it =  shapes.find(pat);
      int this_shape = -1;
      if (it == shapes.end()) {
        this_shape = shapes.size();
        shapes[pat] = this_shape;
      } else {
        this_shape =  it->second;
      }
      if (this_shape == find_shape) {
        std::cout << "Found match at node " << tree->value << std::endl;
      }
      return this_shape;
    }


    В нивном решении надо заменить unordered_map shapes на массив пар чисел (или массив структур или два массива чисел). Циклом в нем проищите текущую пару l, r, если не нашли, то допишите в конец.

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

    Но, возможно вашему преподу такое будет слишком заумно. Тогда вам нужна аккуратная рекурсивная функция сравнения:
    bool Compare(Tree* a, Tree *b) {
      if (a->left && !b->left) return false;
      if (a->right && !b->right) return false;
      return (!a->left || Compare(a->left, b->left)) && (!a->right || Compare(a->right, b->right));
    }


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

    А дальше вам надо рекурсивно пройтись по первому дереву и вызвать вот эту Compare для текущей вершины и корня второго дерева. Если совпало - то выводите текущую вершину.
    Ответ написан
  • Существует ли быстрый алгоритм поиска общих подстрок во множестве больших строк?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Пока главная проблема, что надо сравнивать все строки со всеми. Если бы их поделить на какие-то части, когда сравнивается не так много строк, пусть даже этих частей много, то задача решается Гораздо проще.

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

    Вот построили вы деревья для всех строк, дальше надо их попарно сравнить простым рекурсивным обходом. Если оба дерева содержат переход по какому-то символу, рукурсивно идите по нему. Если дошли до глубины N - вы нашли совпадение. Можно вообще идти пока не обломитесь и взять максимальную глубину. Такой обход обойдет дерево один раз для каждой пары строк. Да, еще надо будет хорошенько потрахаться с хранением дерева на диске и подгрузкой его кусками, ибо в оперативку оно все не поместится никак.

    Второй вариант, возможно более подходящий для таких объемов данных - это полиномиальные хеши. Можно для каждой строки вычислить L-N+1 хешей для всех подстрок длины N. Первый хеш считается тупо по формуле, а дальше дописывание одного символа справа и удаление одного символа слева можно за 2 операции пересчитать. Вот так вы быстро, за линейное время, можете построить все хеши для одной строки. Запишите их в файл, отсортируйте его (гуглите - известная задача сортировки очень большого файла). А потом операцией слияния можно найти повторяющиеся числа во всех файлах.

    Более того, можно не сравнивать каждый файл с каждым, а выполнять слияние сразу на всех файлах. Для этого надо завести приоритетную очередь, она же куча, она же heap, в которую складывать текущие числа из всех файлов (по одному из файла) вместе с указателем на сам файл. Вам надо из этой очереди вынуть минимальное число, и потом вынимать дальше, пока минимум в очереди не изменился. Т.е. вынуть все одинаковые минимальные числа. Файлы, на которые они указывают - это строки с совпадениями. Пометьте это где-то, и для каждого файла прочитайте следующее число и положите его в очередь.

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

    Если совпадений не очень много это будет работать довольно быстро, отлично параллелится (сортировка разных файлов).

    Если все-таки надо искать совпадения по всем строкам глобально, то придется помучиться. Разбейте ваши данные на K частей примерно одинакового размера так, что каждый компьютер может обработать по 2 части, а хранить хотя бы по 3 части.

    В идеале у вас должно быть еще и K/2 компьютеров, иначе схема усложняется.

    Надо будет провести K-1 раундов. На первом раунде части 1 и 2 лежат на компьютере 1, части 3 и 4 на втором, и т.д. На втором раунде вы храните части 2 и 3 на компе 1, 4 и 5 на компе 2 ... K и 1 на последнем. При переходе между раундами каждый комп отдает одну часть куда-то, и одну откуда-то получает. На третьем и четвертом раунде вы обрабатываете все пары, в которых вторая часть имеет номер на 2 больше первой части (если брать по модулю K). И так далее. На последнем раунде будут обрабатываться пары, где одно число больше другого на (K-1)/2.

    Например, для K=4 вы получаете такие пары на компах:
    1. (1,2) (3,4)
    2. (2,3) (4,1)
    3. (1 3) (2 4)


    Тут надо порисовать и составить схему так, чтобы поменьше данных перекладывалось. Для некоторых K так красиво не получится, и какие-то компы будут простаивать на каких-то раундах.

    По поводу оптимизаций - узкое место будет загрузка данных с диска и передача их по сети. Ассемблером баловаться тут смысла нет особо. Запускайте кучу потоков, чтобы диск не простаивал. Еще репликацию данных можно запускать параллельно с обработкой предыдущего куска, если места хватает.
    Ответ написан
    Комментировать
  • Можно ли вызвать деструктор void*?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Нет. Компилятору же надо знать, что там за деструктор вызывать. Что вы в void* на самом деле положили - он знать не может. Более того, там не только деструкторы, там и delete у указателей вызван не будет. Руками придется сначала привести к правильному типу и потом отчистить память (что вызовет деструктор).
    Ответ написан
  • Как создать цикл для того чтоб заменять 0 на 1 и 1 на 0?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Подсказка: в c++ в цикле for не обязательно использовать i++. Можно, например, i+=10.
    Ответ написан
    Комментировать
  • Не работает код C++?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Размер результирующего массива тоже arrSize. Не надо его делить на 3.
    Еще инициализация массива у вас не "значение элемента массива равно его порядковому номеру". Вы там тупо единицами все инициализируете.

    Ну и вывод в цикле будет весьма спамный.
    Ответ написан
    Комментировать
  • Тип с точностью до 4 знаков C++?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Есть. Называется int. Вам надо хранить количество десятитысячных в числе. Иными словами, вы вместо x храните в int x*10000. При выводе делите на 10000 (и установите выводить 4 знака).

    Такие числа можно просто складывать и вычитать. При умножении надо будет результат поделить нацело на 10000 (или округлить к ближайшему, делящемуся на 10000 и потом отбросить 4 нуля). При делении - наоборот. Надо сначала домножить числитель на 10000, а потом поделить нацело на знаменатель (возможно стоит подумать об округлении к ближайшему целому).

    Upd: И вообще, раз уж разговор о C++, то можно реализовать свой класс. Там можно даже отдельно хранить целую часть и 4 знака после запятой. Если вам встроенной точности int/int64_t не хватает. Все математические операции можно переопределить и работать, как со встроенным типом. Вообще, по-умному, это называется fixed point numbers.
    Ответ написан
    Комментировать
  • Как написать на С++?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Там, где вы берете максимум из трех чисел, надо складывать количества путей для тех из них, которые равны максимуму.
    Ответ написан
    Комментировать
  • Как сделать захват фото/видео с веб-камеры без использования высокоуровневых библиотек?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Есть несоклько системных АПИ.

    Например, DirectShow или MediaFoundation.

    MediaFoundation поновее, побыстрее, поэффективнее и чуть поудобнее. Но криворукие разработчики драйверов его не всегда хорошо поддерживают. Всякие, особенно интегированные в лаптопах, камеры с ним глючат или не работают вообще. Плюс всякие виртуальные камеры, типа OBS не видны через MediaFoundation, потому что разработчикам влом по-нормальному реализовывать виртуальную камеру. Ну и оно только с windows 7 доступно.

    Если вы не планируете открывать камеру, а вам надо только информацию о ней собрать, или вы работаете с определенным устройством, то MediaFoundation вам подойдет лучше.

    Иначе смотрите DirectShow.

    Можно найти много примеров кода в интернете.
    Ответ написан
    2 комментария
  • В строке все элементы в десятичной системе счисления заменить в шестнадцатеричной системе?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Тут есть 5 подзадач:
    1) разбить строку на слова
    2) определить по слову, является ли оно числом в десятичной системе счисления
    3) Перевести слово в число
    4) перевести число из десятичной системы счисления в 16-ричную
    5) Записать число в 16-ричной системе в строку

    1,3,4 и 5 - стандартны и гуглятся.
    2 - подсказка: проверьте, что слово состоит только из символов '0'-'9' и не начинается с '0'. По идее, надо бы еще разрешить слово "0", но ноль, он и в 16-ричной системе будет ноль, поэтому такое слово можно не учитывать в вашей задаче. Символы 0..9 имеют коды ascii подряд, поэтому в программе достаточно записать с >= '0' && c <= '9'.
    Ответ написан
    Комментировать
  • Как перевести с python на c++?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Это копирование массива. На C++, если используете vector, то можно присвоение использовать. Там произойдет копия.
    Ответ написан
    Комментировать
  • Как можно вывести слово из текста s1, в котором встречается строка s2(Например, s1="qwe rtyu iopas", s2="ty", вывод "rtyu")?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Тут фактически 2 задачи:
    1) Разбить строку на слова. Тут вам поможет string::substr
    2) Проверить, что сторка s2 встречается в тексте. Вы уже умеете пользоваться string::find.
    Ответ написан
    Комментировать