QList::insert (multi)

[ViTech]

Эта частная операция в частном (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]

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]

Зная (гнусную) натуру 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]

Нормальная у 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]

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

[Авварон]

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

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

[Авварон]

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

[RedDog]

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

С кем?

[ViTech]

Ну в самом деле, если я бы хотел тупо вставлять "по одному", то почему не так

Код

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

Неужели лишняя строка ляжет на меня позорным пятном?

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

[RedDog]

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

[Авварон]

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

С кем?

С Qt.

[Igors]

Позорным пятном, конечно, не ляжет, но моё высказывание про 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]

Ага, ну вот пошел в ход "фиговый листок" мнимой общности.

Вот если сделать "грамотно", все на std и итераторах, то можно в любой момент заменить тип контейнера(ов) на другой - и переписывать ничего не придется!

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

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

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

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

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

[Авварон]

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

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

[Авварон]

А кто такой "новый 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);
}

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