Russian Qt Forum
Апрель 26, 2024, 22:10 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Страниц: 1 2 [3] 4 5   Вниз
  Печать  
Автор Тема: QList::insert (multi)  (Прочитано 28252 раз)
ViTech
Гипер активный житель
*****
Offline Offline

Сообщений: 858



Просмотр профиля
« Ответ #30 : Октябрь 04, 2018, 20:10 »

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

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

1. Написать в Qt feature request на добавление нужных методов insert.
Won't fix.

Я тоже думаю, что они так ответят. Ну если кутешники не хотят, чтобы их QList и QVector отвечали требованиям SequenceContainer, то и фиг с ними.

2. Самому пропатчить Qt и добавить нужные Вам методы insert.
Поставят -1.

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

Пока сам не сделаешь...
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #31 : Октябрь 05, 2018, 09:59 »

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;
}

Да, стандартные алгоритмы работают даже с ущербными кутешными контейнерами, если в них есть необходимый базовый функционал.
Зная (гнусную) натуру 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 раз. Разве это "решение"? Нет, просто другая форма записи тупенького "по одному"

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

Кстати, у него есть доступ к методам reserve(), end(), так что всё может выйти.
"Прошу исполнить"  Улыбающийся

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

Я разве против оптимизации что-то говорил?
Может и не говорили, но у Вас не сработал "рефлекс", а обильные познания в std этого отнюдь не компенсируют  Улыбающийся
Записан
ViTech
Гипер активный житель
*****
Offline Offline

Сообщений: 858



Просмотр профиля
« Ответ #32 : Октябрь 05, 2018, 13:53 »

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

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

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

Кстати, у него есть доступ к методам reserve(), end(), так что всё может выйти.
"Прошу исполнить"  Улыбающийся

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

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

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

Может и не говорили, но у Вас не сработал "рефлекс", а обильные познания в std этого отнюдь не компенсируют  Улыбающийся
Чуть позже и посмотрим, как сильно меня рефлексы подводят Улыбающийся.
Записан

Пока сам не сделаешь...
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #33 : Октябрь 06, 2018, 11:58 »

Нормальная у std натура, получше чем средний разработчик напишет. Не надо просто от неё чудес ждать.
Неоднократно наблюдал код людей пораженных этой болезнью. Их мЫшление весьма искажено - они не конкретную задачу решают, а ищут "что из 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 контейнеры "ущербные" (с какой стати?), а с коллегами ("средними разработчиками") можно и не церемониться - они ведь не постигли той великой мудрости с итераторами и прочей лабудой. А то что заученная мудрость, мягко говоря, "проблематична" - человек (упорно) замечать не хочет. Он выучил - а значит впереди планеты всей  Улыбающийся

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

Тут бы я порекомендовал...
Во-во

..размышлять не в терминах указателей(особенно голых), а в терминах владения объектами(например с умными указателями). Объекты и владение можно перемещать/передавать. Только с поддержкой move-семантики в Qt не очень гладко.
Ну если объект сидит в контейнере - то контейнер по меньшей мере "один из владельцев". Поэтому если нет других, то как-то выделять/подчеркивать владение излишне.
Записан
RedDog
Частый гость
***
Offline Offline

Сообщений: 221


Просмотр профиля
« Ответ #34 : Октябрь 06, 2018, 13:00 »

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

Сообщений: 3258


Просмотр профиля
« Ответ #35 : Октябрь 06, 2018, 13:06 »

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

Обратная совместимость.
Записан
Авварон
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 3258


Просмотр профиля
« Ответ #36 : Октябрь 06, 2018, 13:07 »

QHash/QMap тоже оч не удобны - с новым range-for не дружат.
Записан
RedDog
Частый гость
***
Offline Offline

Сообщений: 221


Просмотр профиля
« Ответ #37 : Октябрь 06, 2018, 13:25 »


Обратная совместимость.
С кем?
Записан
ViTech
Гипер активный житель
*****
Offline Offline

Сообщений: 858



Просмотр профиля
« Ответ #38 : Октябрь 06, 2018, 13:42 »

Ну в самом деле, если я бы хотел тупо вставлять "по одному", то почему не так
Код
C++ (Qt)
QList<T> src. dst;
...
for (int i = 0; i < src.size(); ++i)
dst.insert(insertPos + i, src[i]);
Неужели лишняя строка ляжет на меня позорным пятном? Улыбающийся

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

Пока сам не сделаешь...
RedDog
Частый гость
***
Offline Offline

Сообщений: 221


Просмотр профиля
« Ответ #39 : Октябрь 06, 2018, 16:00 »

Бенчмарк  вставки в середину стд и кути листа, показывает монопенисуальное время, даже последний на пару % быстрее.
Записан
Авварон
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 3258


Просмотр профиля
« Ответ #40 : Октябрь 06, 2018, 17:25 »


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

С Qt.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #41 : Октябрь 07, 2018, 11:24 »

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

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

QHash/QMap тоже оч не удобны - с новым range-for не дружат.
А кто такой "новый range-for" что так пленяет Ваше воображение?  Улыбающийся

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

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

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

Сообщений: 858



Просмотр профиля
« Ответ #42 : Октябрь 07, 2018, 12:16 »

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

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

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

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

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

Пока сам не сделаешь...
Авварон
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 3258


Просмотр профиля
« Ответ #43 : Октябрь 07, 2018, 18:22 »

Да, неоптимально, но.. сколько там будет тех QImage? Где Вы возьмете хотя бы 1K текстур?  Улыбающийся На такие (пере)расходы можно(или нужно) просто забить.

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

Сообщений: 3258


Просмотр профиля
« Ответ #44 : Октябрь 07, 2018, 18:25 »

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

Код:
std::map<Key, Value> map = {};
for (const auto &item: map) {
    const auto &key = item.first;
    const auto &value = item.second;
    foo(key, value);
}

Код:
QMap<Key, Value> map = {};
for (const auto it = map.constBegin(), end = map.constEnd(); it != end; ++it) {
    const auto &key = it->key();
    const auto &value = it->value();
    foo(key, value);
}

Оч удобно, чо.
Записан
Страниц: 1 2 [3] 4 5   Вверх
  Печать  
 
Перейти в:  


Страница сгенерирована за 0.223 секунд. Запросов: 22.