Задать вопрос
  • Корректно ли вызывать метод у временного объекта?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    DeepSeek галлюционирует. Временные объекты живут до конца выражения. unique_ptr начнет уничтожение после выполнения всего выражения.

    Вот ссылки на стандарт:

    make_unique<> является prvalue: https://en.cppreference.com/w/cpp/language/value_c...
    prvalue: a function call or an overloaded operator expression, whose return type is non-reference


    В момент вызова происходит материализация временного объекта: https://en.cppreference.com/w/cpp/language/lifetime

    Temporary objects are created ... in the following situations:
    when performing member access on a class prvalue.


    Там же написано:
    All temporary objects are destroyed as the last step in evaluating the full-expression


    Т.е. возвращенный make_unique объект будет уничтожен только в конце строки.
    Ответ написан
    Комментировать
  • Как симулировать комбинаторные сочетания (C(k, n)) за O(1) памяти?

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

    Edit: Если, все-таки, хочется именно случайно сочетание сгенерировать, то вот алгоритм, основанный на reservoir sampling:

    int taken = 0;
    for (int i = 0; i < n; ++i) {
      if (rand()*(n-i) < k-taken) {
        ++taken;
        // Взять элемент i.
      }
    }
    Ответ написан
  • Как лучше восстановить индексы в n-мерном рюкзаке с точным весом?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Для восстановления вам нужен второй массив, где вы храните одно из 3 значений - в какой из трех наборов идет i-ая гиря. Когда считаете dp и пишите, что можно составить i, w1, w2 вы же эти значения получили куда-то поместив последний элемент. У вас или к w1 что-то было прибавлено, или к w2, или никуда. Это 3 варианта.

    При восстановлении начните с N, sum/3, sum/3 и в цикле вычитайте 1 из первого индекса и вес i-й гири или не вычитайте или вычитайте из одного из весов, в зависимости от сохраненного знаяения во втором массиве.

    Можно вместо второго массива в dp хранить 0, если это состояние невозможно и или номер кучки для последней гири.
    Ответ написан
    Комментировать
  • Когда передавать копию callable, а когда через rvalue reference?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    В дизайне интерфейса можно передавать и копию и rvalue refernce. Что выбрать - решать вам, как создателю интерфейса. Если у вас предполагаются использование функций/лямбд без тяжелого состояния (связанные аргументы по значению), то копирование дешевое и не надо его вводить. rvalue reference всегда дешево, но у вас нельзя будет переиспользовать предикат между разными вызовами.

    В функциях из algorithm используется передача по значению, что бы не ограничивать пользователя. Вы можете один раз написать нужный вам предикат и передавать его во все вызовы. Плюс исторически так сложилось. Когда оно все созадавалось, никаких rvalue reference и не было. Потом их добавлять и не стали, потому что в самом частом случае, если лямбду прямо в аргументах задавать, то она практически бесплатно передастся.

    Там не используется передача по ссылке (lvalue reference), потому что это не так универсально в шаблоне. Если у вас какой-то const предикат, вы его в reference не передадите. А делать const & в интерфейсе нельзя, вдруг у вас предикат не константный?

    И, если вы все-таки хотите передать ссылку, то можно передать std::ref(pred), тогда в шаблоне выведется передача по ссылке.
    Ответ написан
    Комментировать
  • Как научиться решать алгоритмические задачи?

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

    Хорошие книги: Кнут "искусство програмирования", Кормен "алгоритмы. Построение и анализ", Бхаргава "Грокаем алгоритмы". Старайтесь прорешивать все упражнения в этих книгах. Но прочитав их вы задачи решать не научитесь, а лишь подтянете базу.
    Ответ написан
    Комментировать
  • Правильно понимаю из статьи про умные указатели?

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

    Тут автор считает, что сначала выполнится new A(), потом new B(), потом конструктор unique_ptr. Если исключение бросит B(), то действительно будет утечка памяти. Объект A, полученный через new умрет еще до оборачивания в unique_ptr. Такой сырой указатель автоматически не удалится.

    Такая последовательность невозможна c С++17:
    In a function call, value computations and side effects of the initialization of every parameter are indeterminately sequenced with respect to value computations and side effects of any other parameter.


    Evaluations of A and B are indeterminately sequenced : they may be performed in any order but may not overlap: either A will be complete before B, or B will be complete before A. The order may be the opposite the next time the same expression is evaluated.


    Но до C++17, действительно, компилятор может перемешать вычисления аргументов как угодно.
    Ответ написан
    Комментировать
  • Как отсортировать список из массивов?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Зависит от возможных значений чисел. Если числа не очень большие, то RadixSort будет самым быстрым вариантом. В противном случае самая обычная стандартная сортировка будет достаточно быстрая. Просто надо как-то ей передать функцию сравнения двух массивов, которая смотрит на первый элемент, а потом на второй. Что-то вроде a[0] < b[0] || (a[0] == b[0] && a[1] < b[1]). Не специалист по C#, но возможно массивы уже так и сравниваются там.
    Ответ написан
    Комментировать
  • Код при самостоятельном тестировании работает корректно, а при проверке тестировщиком программа выдает ошибку. В чем может быть проблема?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    У вас неинициализированные переменные mini и maxi. И они используюся такими в сравнениях. Это Undefined Behavior и на разных компьютерах может вести себя по разному. И если вам не повезет и, например, mini окажется каким-то очень маленьким числом, то у вас выдаст не правильный ответ.
    Ответ написан
  • Как из длины массива и максимального количества потоков узнать индексы, которые будет обрабатывать поток?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Вам надо разбить массив на K как можно более равных частей?

    Если длина массива N, то все куски будут длиной хотя бы floor(N/K), и ровно N%K будут иметь на 1 элемент больше. Вроде, если у вас 10 элементов надо на 3 потока разделить, то будут длины {4, 3, 3}. А если 15 на 4, то {4, 4, 4, 3}

    Так что i-ый кусок будет начинаться с позиции (N/K)*i + min(i, N%K) и иметь длину N/K + ((i < N%K) ? 1 : 0).

    Чуть проще формулы, если вы эти позиции явно в массиве получите, а не будете каждую отдельно считать:
    int start[K], end[K];
    int prev = -1;
    for (int i = 0; i < K; ++i) {
      int len = N/K + ((i < N%K) ? 1 : 0);
      start[i] = prev + 1;
      end[i] = start[i] + len;
      prev = end[i];
    }
    Ответ написан
    Комментировать
  • Как называется такая структура данных?

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

    И вообще, у вас тут намудрено, почему нельзя сделать просто:
    let objects: HashMap<Uuid, Object>;

    Тут все такой же O(1) доступ к элементу по id. Зачем вам массив? Вы там добились простой и cache-friendly итерации по всем объектам? Не факт, что это уже не реализовано внутри HashMap. По крайней мере во многих языках можно проитерироваться по всем объектам в стандартной хеш-таблице.

    Зато у вас там удаление элемента - это что-то сложное. Особенно, если вы не хотите избежать фрагментации и неиспользованного места в массиве.
    Ответ написан
    4 комментария
  • Как реализовать алгоритм на С++?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Используйте std::vector. Их можно присваивать как переменные. При этом там под капотом не будет никакого копирования, а просто изменение указателей в данном случае (так как правая часть - временное значение).
    std::vector<int> a, b;
    a = a0;
    b = F(a);
    for (int i = 1; i <= n; ++i) {
      a = G(b);
      b = F(a);
    }


    Если вас напрягает, что функции G и F выделяют память внутри, то можно сделать, чтобы они получали vector, в который надо вернуть значения:
    void F(const vector<int> &a, vector<int>& res);
    void G(const vector<int> &b, vector<int>& res);
    
    std::vector<int> a, b;
    a = a0;
    b = F(a);
    for (int i = 1; i <= n; ++i) {
      G(b, a);
      F(a, b);
    }
    Ответ написан
    Комментировать
  • Почему без std::remove_reference_t не работает?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Вообще, не вижу противоречия. У вас же там tfunc&&, его вы пытаетесь к void* привести и к нему применяете remove reference.

    Попробуйте в ваш static assert добавить std::move и он обвалится.
    Ответ написан
    Комментировать
  • Могут ли возникнуть проблемы при одновременном чтении и записи в разных потоках переменной?

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

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    В правильном решении dp[i][k][t] должно обозначать максимальную возможную стоимость объектов, среди превых i, такое что суммарная энергия и время у них t и k. Или -inf, если такое набрать невозможно.

    Пересчет: dp[i][k][t] = max(dp[i-1][k][t], dp[i-1][k-K[i-1]][t - T[i-1]]) (второй вариант считаем, только если k>= K[i-1], t>= T[i-1].

    База: dp[0][0][0] = 0, dp[0][k][t] = -inf.

    Ну и ответ - max_{k, t} Dp[n][k][t].

    Раз надо выводить и сами объекты, то надо еще запоминать, откуда был переход, т.е. еще один трехмерный массив bool, Где вы будете хранить True, если пересчитали через + x['v'].
    Ответ написан
    Комментировать
  • Как правильно написать partition?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    https://en.m.wikipedia.org/wiki/Quicksort
    Смотрите секцию algorithm. Там аж 2 варианта с объяснением и кодом.
    Ответ написан
    Комментировать
  • Что лучше: static методы или функции?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Посмотрите в этот allStatic: https://github.com/openjdk/jdk/blob/496641955041c5...

    Там написано, почему используются статические методы: Почему-то авторы какого-то проекта HotSpot решили, что плодить namespac'ы плохо. Так что это вызвано соглашениями по стилю в конкретном проекте. Их право.

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

    Еще логично сделать функцию членом класса, если она именно с классом работает. Например, функции фабрики.

    Кроме этого я не вижу особо причин использовать статические методы вместо функций.
    Ответ написан
    2 комментария
  • Какой бонус лучше выбрать при броске 20-гранной кости?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Вам надо подсчитать вероятности успеха. Просто с бонусом все элементарно. Если бонус b, то у вас выпадают очки b+1,b+2,b+3...,b+20 с равной вероятностью. Считаете сколько их больше нужного количества очков m и делите на 20: (20-(m-b)+1)/20. Вот вероятность выиграть с этим бонусом.

    Проблема с двумя кубиками. Тут не сумма, а максимум. Если составить таблицу результатов, например для костей с 3 гарнями, то мы получим вот это:

    * 1 2 3
      -----
    1|1 2 3
    2|2 2 3
    3|3 3 3


    Т.е. 1 выпадет в 1 исходе, 2 в - в трех, 3 в 5... Для 20-гранных кубиков будет аналогично. i от 1 до 20 выпадет с вероятностью (2i-1)/400.

    Какие исходы вам подходят? i+b >= m, т.е i >= m-b.
    Итак, для вероятности успеха вам надо проссумировать вероятности всех хороших исходов. Т.е. просуммировать (2i-1)/400 для i от m-b до 20.

    Потом взять ту конфигурацию, у которой вероятность выигрыша больше всего.

    Формулы выше считают, что m > b. Иначе они не совсем работают и там получается вероятность больше 1. На самом деле она там 1. Так что если есть вариант с бонусом хотя бы нужное количество очков - берите его не раздумывая.
    Ответ написан
    Комментировать
  • Почему шаблон выдает ошибку при включении заголовка в .cpp файл?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Не совсем уверен, потому что кода не хватает в вопросе. Но симптом звучит как "если шаблон определяется не в том же файле, где он объявляется, то ничего не работает". Это частая ошибка на С++ с шаблонами.

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

    Поэтому надо или шаблон объявлять и опеределять в хедере, чтобы оперделения были везде, или в cpp с определениями указать спецификацию для всех используемых варинтов шаблона. Вроде
    using my_template<int>;
    Ответ написан
    6 комментариев
  • Не могу решить задачу на C?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Если проблема только с тем, что у вас циклов слишком много, то можно 3 последних объединить в 1.

    Вы при каком условии должны числа дописывать в ответ? Пока есть число хоть в одном из двух массивов.
    Вот и получается:
    while (i < M || j < N)
    Но внутри уже чуть побольше случаев. Можно просто ваши же условия объединить. Если выполняется условие первого цикла - делаете тело первого цикла. Иначе, проверяете условие второго цикла, делаете его, иначе - тело третьего цикла.

    Но можно знатно сократить код, если просто расписать все варианты, когда вы берете число из A. В противном случае, очевидно, берется число из B. Число из A берется, если оно есть и оно "лучше" числа из B - или B вообще нет, или A < B:
    if (i < M && (j == N || A[i] < B[j])) {
      C[k++] = A[i++];
    } else {
      C[k++] = B[j++];
    }
    Ответ написан
    4 комментария
  • Как это посчитать?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Проще всего двигать элементы по одному, справа-налево. Элемент можно сдвинуть, если справа стоит 0 или такой же элемент. Поддерживаем инвариант, что все элементы правее current уже сдвинуты и уплотнены до предела. Двигаем текущий пока можем. Чтобы не было циклов не двигаем нули.
    int n = a.size();
    int current = n-1;
    while (current >= 0) {
        while (a[current] > 0 && current < n-1 && 
              ((a[current+1] == a[current]) || (a[current+1] == 0))) {
          a[current+1] += a[current];
          a[current] = 0;
          ++current;
        }
        --current;
    }
    Ответ написан
    5 комментариев