Russian Qt Forum

Добрый день

С удивлением обнаружил что QList умеет вставлять только "по одному" - пришлось использовать вектор указателей. Не беда, но все-таки.. Или я плохо читал букварь?  Плиз "ткните носиком"

Спасибо

 а что значит вставлять только по одному? есть же http://doc.qt.io/qt-5/qlist.html#append-1 (http://doc.qt.io/qt-5/qlist.html#append-1)

append добавляет в конец (относительно легкая операция), а мне нужно в середину.

Кутишные контейнеры - говно, не надо их юзать. Особенно кулист

Подробностей бы?

могу за QVector сказать - он говно, тк. тормозит.
за QMultiMap - он говно, тк. есть проблемы, когда более 1 ключа с тем же значением.

Попробуйте скомпилять:

C++ (Qt)
#include <list>
#include <QList>
 
class NonCopyable
{
public:
    NonCopyable(const NonCopyable&) = delete;
    NonCopyable(NonCopyable&&)      = default;
};
 
int main()
{
    std::list<NonCopyable> std_list;
    std_list.push_back(NonCopyable{});
 
    QList<NonCopyable> q_list;
    q_list.push_back(NonCopyable{});
}

QVector тормозит при каких обстоятельствах? Если предварительно резерв делать, то не замечал тормозов.
Я QMultiMap заменяю на QMap<T1, QList<T2>>

Рискну предположить что как-то раз, возможно совершенно случайно, QVector был заменен на std::vector, и... (о чудо!) стало быстрее! Разбираться отчего да почему - та нафиг надо! Все и так ясно! QVector - говно! Этот вывод отложился в (под)сознании и стал непререкаемой истиной, ну а как же, ведь он основан на личном опыте ("своими глазами видел"). Хотя объективные подтверждения вряд ли найдутся, скорее всего "сам насвистел".

Увы, в основном из таких предрассудков и состоит наш "богатый опыт"  :)

Опять примитивное швыряние говном (чужой опыт ничему не учит). Мне вот идея QList кажется весьма разумной, многие ситуации он покрывает, пусть не все. Да и в целом Qt контейнеры поприятнее stdухи. Есть конечно недочеты, напр не хватает хвункторов, ну это дело такое...

 

вас в гугле забанили?

Насчет тормозов вектора, есть бага на кутишном трекере.

А вот чем лист то не угодил? Вполне удобная и полезная конструкция...

Ну там много смешных тикетов:)



Сколько аллокаций в последней строке?


А тут?

Для QString сработает как вектор (sizeof(QString) == sizeof(void *)), поэтому вероятно ни одной (пул). Размер QImage навскидку не помню, наверное > sizeof(void *) (если не так поправьте), поэтому кроме вставки в массив указателей будет еще и выделение блока для эл-та QImage - хотя это и не оптимально. Да, возможно для хранения QImage(й) оптимальнее QVector, особенно с учетом implicit шары. И что? Не вижу никаких оснований для "снисходительной иронии"  :) (на базе сомнительной статьи).

А вот с сортировкой у QList нехорошо - месит данные, а ведь можно было сортировать массив указателей.

Ладно, предлагаю поговорить о том как вообще выбирать контейнер. Практически в любой задаче будет много векторов, простые данные, структуры (не классы) которых "много". Но если элемент что-то "выше травы" (класс) - то обычно, в большинстве случаев, приходится выделять для него блок памяти и хранить вектор указателей. Тогда вставка и удаление намного дешевле, и адреса эл-тов не "уплывут", Ну ясно ассоциативные контейнеры - своя песня, а так ничего другого-то и нет. Собсно это и обобщает QList - вполне нормально.

Помню Ваня тут все тьюториалы писал :), рекомендовал такой 2-мерный массив (псевдокод)
Хотя с имплисит шарой и/или конструктором перемещения это и будет работать сносно - все-таки это не есть грамотно для вставок/удалений.

Попробовал - не вышло (наверное компилятор староват). В чем суть-то?

По запросу "г...но" кутишные контейнеры не выдаются.

С компилятором всё нормально(если он не совсем чудной какой-нибудь). Суть в том и есть, что нельзя в кутешный контейнер положить некопируемый объект.

C++ (Qt)
    QVector<std::unique_ptr<MyClass>> q_vector;
    q_vector.append(std::make_unique<MyClass>());
 

Implicit sharing, которым кутешники так хвалятся, иногда боком выходит: выполняется копирование, когда об этом совсем не просят.

А по теме:

В контейнерах особо и не должно быть кучи методов на все случаи жизни. Если таким желаниям потакать, то найдётся много желающих туда свои хотелки запихнуть. И тогда в другие контейнеры придётся добавлять такой же функционал. Поэтому: контейнеры отдельно, алгоритмы отдельно. То, что Вы хотите сделать, больше подходит под алгоритм. Так что или готовый (https://en.cppreference.com/w/cpp/algorithm) подбирайте, или свой пишите.

Всё верно. Вас устраивает контейнер, который для одних _кутешных_ типов эффективен, а для других - нет? И без знания что "у ей внутре" не скажешь, подойдет лист, или нет.
К примеру, QVariant - плохой тип для листа, хотя есть QVariantList и он много где используется.
К 6ке вроде бы закопают qlist. Ну я на это надеюсь.

Вообще, std::deque лучше примерно всем.

Ну удачи написать внешний range-insert))))

Аллоцировать на каждую вставку чтобы сэкономить немного бинарного кода в QtCore? Отличная идея!

В принципе - да, устраивает, хотя (за европейскую зарплату) мог быть и лучше. И да, любой контейнер эффективен для одних типов, но не для всех. И знать потроха (хотя бы в общих чертах) обов'язково.

К сожалению, MSVC реализация ставит на нем крест :'( Да и в других размера чанка не хватает, поэтому давно использую самописную деку. Насчет "всем" это Вы конечно загнули, он силен только на push_back, но во многих задачах это важно.

Мда, сегодня наверное "не Ваш день", сделаю вид что не слышал  :)

Я говорил в общем о подходе. Определяется необходимый и достаточный набор методов для контейнеров (в STL описываются в Named requirements (https://en.cppreference.com/w/cpp/named_req)), остальное выносится в алгоритмы (https://en.cppreference.com/w/cpp/algorithm).

Имея метод

C++ (Qt)
QList::iterator QList::insert(QList::iterator before, const T &value)

нужно какую-то rocket science применить, чтобы внешний range-insert написать? :) Эффективность такого решения - отдельный разговор.

А что не так? Сделайте мой день :).

Смысл member range-insert у вектора - одна аллокация и один сдвиг хвоста вектора.
Без доступа к методам reserve(), end() ничего не выйдет.
Так что удачи с генерик алгоритмом.

Ну вектор себя ведет примерно одинаково независимо от типа (исключение - вектор булов, тут комитет как всегда лоханулся)

Интересно, не знал. А в новой студии не поправили?
А как же insert, он тоже быстрее становится - достаточно подвинуть чанк а не весь хвост.

Прям совсем ничего не выйдет? :) Или не выйдет оптимально(по каким-то критериям)? И при чём тут конкретно вектор(я так понимаю std::vector имеется в виду)? Других контейнеров, куда можно вставлять в заданную позицию, не существует?

Не знаю, но если так зависеть от реализации - зачем тогда std?
Так не выходит, эл-ты во всех последующих чанках тоже надо месить. Дека очень важна когда счет идет на мульены, тогда пере-распределение "всего" (вектор) просто вешает ОС.

А еще хороший малоизвестный контейнер sequence (?) насколько помню так он называется в std. Доступа по индексу нет, просто можно создавать новый эл-т (обычно для хранения его указателя в др контейнере) и "удалять" (мнимо). Типа кастомной кучи/аллокатора.

Все Вам правильно объяснили, чего тормозите? Сделать множ вставку в QList я не могу т.к. доступ к массиву указателей наглухо перекрыт (из идейных соображений). Да и вообще, чего это, взяв готовый/штатный контейнер, я должен его "доделывать"? У др контейнеров с доступом по индексу этот ф-ционал всю жизнь был. Ну а о том что вставка/удаление для таких контейнеров - удовольствие дорогое, и оптимизировать их программист просто обязан - и напоминать неудобно.

Understand the Qt containers (https://marcmutz.wordpress.com/effective-qt/containers/).
Статья уже старая, но для общего понимания довольно-таки неплоха.

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


Вы, похоже, много всего не можете сделать :). Но это, опять же, не означает, что это в принципе невозможно сделать. Почему не пользуетесь теми другими хорошими контейнерами, зачем Вам плохой QList? Если вернуться к баранам и говорить конкретно о QList, то можно предложить такие варианты:

1. Написать в Qt feature request на добавление нужных методов insert.
2. Самому пропатчить Qt и добавить нужные Вам методы insert.
3. Написать функцию, которая в QList вставляет несколько элементов по одному.
4. Воспользоваться готовым алгоритмом из STL:

C++ (Qt)
#include <QList>
#include <QDebug>
#include <iterator>
 
int main()
{
    QList<int> a = {1, 2, 7};
    QList<int> b = {1, 2, 3, 4, 5, 6, 7};
 
    std::copy(b.begin() + 2, b.end() - 1, std::inserter(a, a.begin() + 2));
 
    qDebug() << a;
}

Да, стандартные алгоритмы работают даже с ущербными кутешными контейнерами, если в них есть необходимый базовый функционал.


Ещё неудобно напоминать, что для конкретной задачи нужно подбирать контейнер, который для неё подходит оптимальным образом. Вы, похоже, методом тыка выбираете: есть ли в контейнере нужные методы или нет, а не исходя из его характеристик и назначения. Ну и для каких задач предназначен контейнер, мы опять скорей всего не узнаем. Может нужно делать миллион вставок по десятку элементов в разные места контейнера? Расскажите ещё раз, что если Вы не указали что-то, то нужно подразумевать то-то, если не отметили другое, то это обозначает третье. Очень интересно послушать :).

Эта частная операция в частном (vector, deque) контейнере позволяет снизить сложность алгоритма вставки в середину с O(M*N) до О(N). Утверждать что такая оптимизация не нужна for the sake of algorithms не оч умно так-то.

Won't fix.

Поставят -1.

Я разве против оптимизации что-то говорил? Я больше толковал о том, что нужно отделять мух от котлет и выбирать подходящие инструменты. То, что в контейнерах STL озаботились оптимизацией при вставке нескольких элементов - это замечательно. Но контейнеры STL не единственные в мире С++, есть и другие. Те же кутешные :).


Я тоже думаю, что они так ответят. Ну если кутешники не хотят, чтобы их QList и QVector отвечали требованиям SequenceContainer (https://en.cppreference.com/w/cpp/named_req/SequenceContainer), то и фиг с ними.


Логично. Но варианты, что я привёл, конечно, не единственные. Можно и другие решения для QList придумать. Кстати, у него есть доступ к методам reserve(), end(), так что всё может выйти. Если на него вообще стоит время тратить.

Зная (гнусную) натуру std сразу можно предположить - ничего толкового оно не делает, просто "2 строчки вместо одной" (ценой вычурных конструкций). Ладно, проверим. Поставим breakpoint на QList::insett (вот это место)

C++ (Qt)
template <typename T>
inline typename QList<T>::iterator QList<T>::insert(iterator before, const T &t)
{
    Q_ASSERT_X(isValidIterator(before), "QList::insert", "The specified iterator argument 'before' is invalid");
 

И убедимся что затратный insert вызовется N раз. Разве это "решение"? Нет, просто другая форма записи тупенького "по одному"

А остальные предложения
Даже не заслуживают обсуждения, их минусы очевидны.

"Прошу исполнить"  :)

Есть простое нормальное решение - использовать std::vector или QVector<T *>. Да, требуется чуть больше внимания, придется следить за delete/clear, ну я это переживу. Но вот подумалось - а подходит ли вообще QList для этих целей? Стоит ли (упорно) добиваться такого ф-ционала? Например (псевдокод)
Указатели передаются "из рук в руки", ни одного копирования/удаления данных нет. То что часто есть забота (clear без delete) здесь в плюс. Требовать того же от QList вряд ли разумно - ведь QList::operator[] возвращает ссылку на эл-т, стало быть и вставляться должны сами данные, с неизбежным копированием. Это проблематично.

Может и не говорили, но у Вас не сработал "рефлекс", а обильные познания в std этого отнюдь не компенсируют  :)

Нормальная у std натура, получше чем средний разработчик напишет. Не надо просто от неё чудес ждать.


Это предложения, которые лежат на поверхности в ответ на всякие "не могу"/"ничего не выйдет". Хотите решения получше - придётся поднапрячь голову.


Это у Авварон просите, он знает как это сделать :). Можно даже на std::vector продемонстрировать, у него тоже reserve(), end() доступны(а может и ещё что нужное). У меня же стек удачи переполнен, ничего хорошего не получится )).


Тут бы я порекомендовал размышлять не в терминах указателей(особенно голых), а в терминах владения объектами(например с умными указателями). Объекты и владение можно перемещать/передавать. Только с поддержкой move-семантики в Qt не очень гладко.

Чуть позже и посмотрим, как сильно меня рефлексы подводят :).

Неоднократно наблюдал код людей пораженных этой болезнью. Их мЫшление весьма искажено - они не конкретную задачу решают, а ищут "что из std здесь подходит", любой ценой пытаясь влепить std вызов, полагая что чем их больше - тем лучше. Что он делает, к месту здесь или нет - зачастую понимается слабо, да это им и неважно, главное - владение предметом налицо. Богатырская сила std охотно демонстрируется когда вопрос решается "как угодно". Ну в самом деле, если я бы хотел тупо вставлять "по одному", то почему не так

C++ (Qt)
QList<T> src. dst;
...
for (int i = 0; i < src.size(); ++i)
 dst.insert(insertPos + i, src[i]);

Неужели лишняя строка ляжет на меня позорным пятном? :) Зачем забивать голову всякой чепухой типа inserter'ов когда все прекрасно и без них?

А вот когда ручное решение утомительно и попользоваться готовым было бы очень к месту - ни хрена от того std "не дождесся". Сразу включается "плохая задача", типа "я слишком много хочу", "жду чудес" (да неужели?) и.т.п.

И еще такой деликатный момент. У людей, даже вполне нормальных, но злоупотребляющих std быстро развиваются самонадеянность и зазнайство. Вот уже Qt контейнеры "ущербные" (с какой стати?), а с коллегами ("средними разработчиками") можно и не церемониться - они ведь не постигли той великой мудрости с итераторами и прочей лабудой. А то что заученная мудрость, мягко говоря, "проблематична" - человек (упорно) замечать не хочет. Он выучил - а значит впереди планеты всей  :)

Эта тема в очередной раз подтверждает мои наблюдения.

Во-во

Ну если объект сидит в контейнере - то контейнер по меньшей мере "один из владельцев". Поэтому если нет других, то как-то выделять/подчеркивать владение излишне.

Маленький вопрос созрел: если QList ущербный (об ущербность наверняка Qt-шники осведомлены), то какого рожна всякие QHash/Map его юзают по полной? Из сета лист создаётся, а не вектор, QVariantList а не вектор, да много где листом значения возвращаются.
В чем дело?

Обратная совместимость.

QHash/QMap тоже оч не удобны - с новым range-for не дружат.

С кем?

Позорным пятном, конечно, не ляжет, но моё высказывание про std и среднего разработчика вполне подтвердит :). Если Вы в какой-то момент решите, что для решаемой задачи вместо QList лучше использовать QLinkedList, как себя поведут эти две простые строчки? С таким подходом, надо полагать, код такого вида будет по всей кодовой базе. Будете во всех местах постоянно переписывать?

Бенчмарк  вставки в середину стд и кути листа, показывает монопенисуальное время, даже последний на пару % быстрее.

С Qt.

Ага, ну вот пошел в ход "фиговый листок" мнимой общности.
При этом прозрачного намекается что, дескать, стоит потерпеть все эти уродства - ведь "универсально" делаем! Сколько интеллекта бездарно разбазаривается для достижения этой (липовой) общности  :'(

На деле же все наоборот. Замена QList (прямой доступ) на QLinkedList (последовательный доступ) - решение принципиальное, то что хорошо для одного контейнера - плохо для другого и наоборот. Напр QLinkedList умеет быстро вставлять, а QList нет. Поэтому, если уж так случилось, меняем имя контейнера чтобы компилятор отсыпал все места где он юзается. И руками по всему коду, каждое место смотрим и, если нужно, содержательно правим. И в следующий раз думаем головой когда выбираем контейнер для базовых данных (а не на std надеемся).

А кто такой "новый range-for" что так пленяет Ваше воображение?  :)

Хмм.. ну допустим ее нет, что бы Вы предложили взамен? QVector что ли? Это по меньшей мере столь же спорно. Или как? Лично я лучшего не вижу. Ладно, рассмотрим пример совершенно неверного применения QList
Размер QVector3D = 12, поэтому на каждый эл-т выделяется блок памяти. А это параграф да плюс параграф упр-я да плюс указатель, итого 16+16+8(4)=40 байт. Это втрое больше оригинального размера, да и скорость доступа чуть ниже. Да, нехорошо получилось.

Насколько я помню, смысл той статьи примерно такой же, мол, sizeof многих классов с гулькин нос (хотя и больше sizeof(void *), a для них QList разбазаривает память и напрасно мельтешит с alloc'ами. Да, это замечание справедливо, но все-таки я бы не принимал его так близко у сердцу :) Ну хотя бы
Да, неоптимально, но.. сколько там будет тех QImage? Где Вы возьмете хотя бы 1K текстур?  :) На такие (пере)расходы можно(или нужно) просто забить.

Выливание чего-то в QList - как общее решение - правильное, а идеального здесь нет. Гораздо чаще интересуют неперемещаемые данные чем сырой вектор.

Если Вам нравится такой подход - то и на здоровье :). А если в программе одновременно используются и QList и QLinkedList, Вы для каждого типа контейнера будете писать отдельную функцию(которые по сути делают одно и то же)? Или вставлять надо не копии элементов, а перемещать их?


Код бенчмарка показать бы, чтоб посмотреть, что именно сравнивается.

Имаджей - врядли, а QVariant'ов - запросто. Мой поинт был в том, что взяв случайный QType нельзя с уверенностью сказать что он "хорош" для кулиста. Скорее, нет.

Оч удобно, чо.

Да, кувектор. У него нет проблем кулиста.
Но лучше конечно std::vector, он и умеет больше и бинарного кода генерит меньше (навеяно недавним холиваром в геррите когда я менял QVector на std::vector)

Простите, был сильно не прав. QList сильно в опе.

180мс std против 1540мс Qt

Беда печаль...

А ссылку можно напочитать?

Вы же QList сравнивали не с std::list? :)

С бенчмарками не всё так просто. Если так "в лоб" писать пару тестов подряд в main, то бывает, что первый тормозит сильней просто потому, что первым выполняется :). Несколько раз с таким сталкивался, когда хотел на скорую руку пару вещей сравнить. И в теме изначально речь шла про вставку нескольких элементов "за раз". Попробуйте повставлять в середину 1000 раз по 100 элементов (размером больше чем int/указатель). Для std контейнеров используйте соответствующие методы для вставки диапазона. Для кутешных тоже можете, если найдёте :). Ну и сравнивать надо контейнеры, которые схожи по своему внутреннему устройству.

С ним. А надо было с чем то другим?

в объявлениях вот так было

Это совершенно разные контейнеры. Вставку в QList можно сравнить со вставкой в std::vector.

https://codereview.qt-project.org/#/c/237051/
пруфы где-то в середине - меньше плюсового кода, меньше бинарного кода.

Вектор идеален для простых данных, но чем развесистее структура (эл-т), чем тяжелее ее копирование - тем он менее эффективен. Поэтому в общем случае QList - более верное (или более концептуальное) решение. Хотя конечно не идеальное, такого в общем случае просто нет.

Что касается "std::vector быстрее" - то вряд ли из этого что-то можно выжать, и вряд ли стоит мочить все QVector :)  Проблемы практически всегда связаны с неоптимальным использованием конкретного контейнера (т.е. он здесь не к месту, нужен другой), а не с его реализацией. Но все-таки интересно где же насвистели "великие тролли"  :)

А код/проект где? Но все равно, правильно сделали что репорт написали (нечего им расслабляться  :))

Правомерное сравнение примерно такое
Еще лучше случайно выбирать точку вставки, а то все сводится к append (легкий жанр). И прогонов на одном запуске не 2, а хотя бы 6-8, а то, как указал ViTech, меряем кеш процессора.

Для тяжелых объектов придумали мур-семантику которая сводит на нет весь профит от кулиста.
Также, есть проползал добавить trait "trivially relocatable" (поддерживается в eastl) чтобы можно было перемещать данные через memmove внутри вектора (как и делает QVector сейчас).
Ну то есть куда не глянь - кулист не делает ничего полезного, а только добавляет оверхед.

Божемой, всё по ссылке.

Даже если допустить что, со всеми новшествами, перемещение "достаточно дешево" (на что всегда найдутся исключения) - суть не в этом. Как ссылаться/использовать объект? Наиболее простое - указатель. Но если объект в векторе - от винта. Приходится хранить индекс, но он не "самодостаточен", нужно знать и контейнер. А если в нем еще и вставки/удаления  - геморрой капитальный. QList и решает эту простую вещь. Делать вектор указателей чтобы "заякорить" данные без QList приходилось очень часто. Это не то чтобы "сложно", но лишние движения, от которых QList приятно избавляет.

:)

Я ничего не понял ???

Просто провайдеры блокируют этот ресурс.  :) Наверное Igors об этом..

По теме, но там по ссылке вроде же нет по произвозводительности никаких преимуществ? Там только 640 байт экономии.. НЕ? Или я плохо читал? :)
 

Не поняли про QList или не слышали старый анекдот как мать повезла сына-дебила на море?  :) Если в 2 словах, то др объекты могут хранить/пользовать указатели на эл-ты QList, при этом в него можно добавлять/удалять др эл-ты, адреса не "уплывут". А c векторами такой возможности нет

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

Но вот что QList не умеет... а сильно бы хотелось:

class A
{...}

class B: public A
{...}

QList<A*> listA;
QList<B*> listB;

listA = listB;  // dont work :( можно только в цикле копировать по элементам...

Я же бенчмарк добавил, вот же https://pastebin.com/qLC5qrmY
Небольшой прирост есть, скорее всего за счет того, что не надо делать копии QVector

> Небольшой прирост есть, скорее всего за счет того, что не надо делать копии QVector

Ах, ага, вижу.. процентов 5-6.. тоже небольшой, но результат...  :)