kitsu
Anton
Есть вопрос по boost::multi_index. Не будет ли проблем, если мы получим index по некоторому полю, а так же верхнюю и нижнюю границы по конкретному значению, например, A, а одновременно с этим мы добавим в контейнер новый объект со значнием этого поля, например, B? Будут ли валидны итераторы полученные ранее по значению A?
Dmitry
На вставку итераторы не инвалидируются там
Dmitry
Так что да
Fuzzytoozy
Ребят может кто сталкивался
Fuzzytoozy
На убунте
Fuzzytoozy
Fuzzytoozy:
Я загружаю либу через dlopen достаю указатель на функцию через dlsym дальше вызываю эту функцию . Она мне инициализирует некоторые объекты и потом стартует тред
Вот в конструкторе треда этого падает
Fuzzytoozy
Причем если я этот код не компилю в .so а статически линкую все работает
Fuzzytoozy
Почему такое может быть ?
Vladislav
а с чем падает? segfault?
Fuzzytoozy
Да
Vladislav
а если под valgrind'ом запустить?
Egor
выгрузки библиотеки не происходит?
Fuzzytoozy
Нет. Загружается она успешно. После я сразу достаю указатель и вызываю функцию и она работает. Просто падает в конструкторе треда на сколько я понимаю. Функция переданная в тред не вызывается
Fuzzytoozy
Пробовал разные функции, не работает
Fuzzytoozy
Может там pthreads как то криво загружается я не знаю
Max
67791 – Crash using std::thread and iostream with dynamic loading of a shared library
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67791
Fuzzytoozy
А похоже на то
Fuzzytoozy
Стектрейс во всяком случае точно такой же)
Fuzzytoozy
Трайну завтра фиксы. Спасибо!
Vladislav
а если clang'ом собрать?
Fuzzytoozy
Не пробовал
Constantine
Vladislav
Это что там, дырень просто?
надо с основной бинарник c pthread-ом линковать, если хочешь в многопоточные динамические либы (еяпп)
Constantine
Max
Это что там, дырень просто?
Похоже, не дырень, а фича :) Хардкорная оптимизация. libstdc++ проверяет, слинкован ли бинарник с pthreads, и если нет, то опускает некоторые локи. Если в main ещё что-то используется из std, то он инициализируется безтредово.
И при позднем связывании получается какая-то фигня.
Constantine
Max
Aλexander
Max
а с ним и здесь должно заработать.
Constantine
Stanislav
Max
нет
в данном контексте - да
Aλexander
Max
нет
говорит приложению, что будет многопоточка и шаред либа. В остальном, конечно, не то.
Stanislav
kitsu
Fuzzytoozy
Fuzzytoozy
Скорей всего это действительно эта фишка , все симптомы на лицо
Constantine
Basil
помните задачу про тругольники, что была ы этом треде и я предложил решение
Basil
сложности N*N. так вот, я нашел решение сложности N
Basil
оно довольно заковыристо математически и требует составления огромной компайлтайм таблицы особых точек
Basil
таблица составляется по oeis.org/A004018
Basil
да, равнобедренные
Nikita
Дано N точек на плоскости, выдать все равнобедренные треугольники
Basil
да, это она, только там ограничение было, типа квадрат на 1000.
Nikita
Basil
так приведённая мной последовательность и определяет точки для возможных положений вершин этих многоугольников и их немного, для дпстанциих указанной. это константа, причем не превышающая 16.
Basil
и тогда просто линейный проход по точкам, с проверкой есть ли в этих особых точка еще парная
Matthew
Если две линии параллельные с шагом 1 заполнены точками то треугольников О(N²)
Basil
а, т.е. координаты не в целых числах? тогда снимаю, остаётся предложенное мной O(N*N)
Basil
да почему же квадрат. мы каждую точку проходим один раз, и в ней нет перебора остальных точек из списка, а только проверка, есть ли в особых точках две позиции из списка, и не лежат ли они на прямой
Basil
а это константа
Nikita
Nikita
Basil
еще раз уточню, координаты целые, или нет?
Oleg
Целочисленность координат — очень сильное ограничение.
Basil
если они рациональные, решение снимаю, остаётся Nквадрат.
Basil
с наихудшим случаем одна точка в центре, остальные по окружности
Nikita
Basil
но тогда она выходит из задачи вычислительной, ибо представление рацинальных чисел упирается в ограничение разрядности
Basil
я про допущение, что координаты рациональны
Basil
блин, надо больше отдыхать, чтобы такое ночью не приснилось, как мне это решение сегодня.
Matthew
Matthew
Сейчас нарисовать попробую
Nikita
а это константа
Оно является константой для фиксированного радиуса. А вот радиусы можно очень долго перебирать.
Вот другой контрпример: сетка N=3k*k. Рассмотрим центральный квадрат k*k. Для каждой упорядоченной пары вершин (u,v) в ней (где u,v не лежат на одной оси oy), есть третья вершина w — зеркально отраженная v относительно вертикальной оси, проходящей через u. uvw — равнобедренный треугольник. Таких пар (u,v) — O(k⁴) = O(N²). При этом в учёте таких треугольников каждую пару посчитали не более двух раз. Итого, уже хотя бы есть O(N²) равнобедренных треугольников, вывод уже дольше O(N)
Basil
так, подумал, и понял, что соглашусь, просто предствавил 9 точек, в квадрате 3*3, треугольников больше 9, в моём решении ошибка в оценке сложности
Matthew
https://i.imgur.com/FX63rZb.png
Тут 24 треугольника
Если приблизить отрезки, будет еще больше
Matthew
Количество прямоугольных треугольников, где одна вершина лежит на одном отрезке, а две остальные на другом (причем одна из сторон перпендикулярна отрезкам), линейно зависит от количества точек
А вот количество "обычных" треугольников зависит квадратично: для каждой на одном отрезке мы говорим, что существует О(N) (в среднем) пар точек на другом отрезке таких, что отрезок между этими двумя точками будет основанием нашего треугольника
Всего получится O(N^2)
Matthew
Квадртичное решение:
Для каждой точки Х множество других точек превращаем в пары (dist, cnt) - расстояние и количество. Тогда количество равнобедренных треугольников с вершиной в точке Х равно сумме cnt*(cnt - 1) / 2 по всем возможным dist.
Проверять треугольники на равносторонность нет нужды - в рациональных точках таких не встретится
Anonymous
@Forrgit будет жить. Поприветствуем!
Dmitry
Как передавать ренджи в функи? По ссылке или по значению?
Anonymous
Это вот эти чтоли - https://en.cppreference.com/w/cpp/experimental/ranges ?
Dmitry
Любые невладеющие. boost::ranges, ranges-v3