Массивы против контейнеров

[pastor]

Пример: QList имеет 10K элементов. Удаляем элемент из середины. Это значит сдвигаются  5К указателей и перекачивается 20К (40К в 64 бит). Это цена 1 erase. Ну оно конечно "быстро" по сравнению с вектором где конструктор копирования будет вызван 5К раз - но очень "относительно".

Если чесно, про лист не понял, что за "20К (40К в 64 бит)"?

Про вектор тоже не верно. Все зависит от типа данных, хранимых в контейнере: movable или non-movable типы. И от этого зависит что будет происходить в недрах контейнера при вставке\удалении элементов. В QList данные всегда movable.

В некоторых случаях мне приходится управлять данными "без контейнеров", в стиле С. Да, это требует заметно больше усилий и аккуратности. Зато получается намного чище, код быстрее а иногда.. даже текст короче Улыбающийся Удобство контейнеров разлагает, приучает ими бездумно ляпать к месту и не к месту. Чего там мне думать сколько где памяти выделилось почем зря? За меня все сделают, я ж классы вывчыв!! На мой взгляд это скользкая дорожка к "говнокоду"

Igors, предположим что у тебя есть сишный массив из 5К элементов. Ты удалил 200 из середины. А далее что? В середине дырка? Или, тебе необходимо вставить новый элемент в середину? Как быть?


Имхо это не корректно сравнимать контейнеры (QList, QVector) с сишными массивами.

[Igors]

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

Вот давайте и сделаем для конкретной задачи. А то что будет на ++ я переживу  

Если чесно, про лист не понял, что за "20К (40К в 64 бит)"?

Чтобы удалить элемент из середины, QList сдвигает 20(40)К байт

Про вектор тоже не верно. Все зависит от типа данных, хранимых в контейнере: movable или non-movable типы. И от этого зависит что будет происходить в недрах контейнера при вставке\удалении элементов. В QList данные всегда movable.

Наоборот, QList справляется с non-movable данными, а QVector нет и std::vector нет. Если sizeof элемента QList меньше sizeof(void *), то элемент может и не иметь конструктора копирования и оператора присваивания, а также можно спокойно использовать указатель на элемент - он не изменится при вставке или удалении др. элементов. А с вектором это рухнет (причем подло, не сразу).

Igors, предположим что у тебя есть сишный массив из 5К элементов. Ты удалил 200 из середины. А далее что? В середине дырка? Или, тебе необходимо вставить новый элемент в середину? Как быть?

Имхо это не корректно сравнимать контейнеры (QList, QVector) с сишными массивами.

А я и не говорил что это должен быть С массив. Просто др структуры данных вместо стандартных. Вообще ну зачем так сразу плохо думать о человеке... типа "ага, он не знает что есть вектор и до сих пор использует С массив". А может он знает но "сомневается"?  

[GreatSnake]

...предположим что у тебя есть сишный массив из 5К элементов. Ты удалил 200 из середины. А далее что? В середине дырка?

memcpy()

Или, тебе необходимо вставить новый элемент в середину? Как быть?

realloc() + memcpy()

А как ещё?

[Igors]

memcpy()
...
realloc() + memcpy()

memmove т.к. поля перекрываются

[BRE]

Вот давайте и сделаем для конкретной задачи. А то что будет на ++ я переживу 

Ну так показывай, как это все у тебя красиво, коротко и эффективно сделано в "стиле С". Будем оборачивать в класс MySuperContainer.   

[pastor]

Наоборот, QList справляется с non-movable данными, а QVector нет и std::vector нет. Если sizeof элемента QList меньше sizeof(void *), то элемент может и не иметь конструктора копирования и оператора присваивания, а также можно спокойно использовать указатель на элемент - он не изменится при вставке или удалении др. элементов. А с вектором это рухнет (причем подло, не сразу).

Может у нас разное определение movable и non-movable типов. У меня такое определение:

movable type - a data type that can safely be moved around in memory using memcpy() or memmove(), such as the C++ primitive types and Qt's implicitly shared classes

QList не хранит данные непосредственно (за исключеним если sizeof(T) имеет размер поинтера и может! быть перемещен - movable type). Он хранит указатели на данные. А указатель это movable или non-movable тип? ))

По поводу QVector. Он сам определяет, какие данные он содержит, movable или non-movable. Все кастом типы по определению non-movable. Но мы можем из них сделать movable при помощи Q_DECLARE_TYPEINFO.

The distinction between movable and non-movable types is also used to speed up insertions in the middle of the vector. When such an insertion takes place, the elements that come after the point of insertion must be moved one position further. If T is a movable type, this is achieved using memmove(); otherwise, QVector<T> needs to move the items one by one using operator=(). The same applies to removals in the middle.

[pastor]

memmove т.к. поля перекрываются

Ну а тогда какая разница между массивом С и темже контейнером QList? Он тоже memmove использует для этих же целей.

[Igors]

Ну так показывай, как это все у тебя красиво, коротко и эффективно сделано в "стиле С". Будем оборачивать в класс MySuperContainer.  

Ну обернуть я и сам могу    А это место у меня (увы) на ++ (std::vector). Получается и некрасиво, и некоротко. Есть идеи оригинального контейнера - обсудим.

Может у нас разное определение movable и non-movable типов. У меня такое определение:

Спасибо за Q_DECLARE_TYPEINFO.(этого не знал). Я имел ввиду

Код

C++ (Qt)
struct Piggy {
   Piggy  ( void ) : mType(0), mStr(0) {} 
  ~Piggy ( void )  { delete [] mStr; }
 
// data
  int mType;
  char * mStr;
};
 
// использование
 QList <Piggy > lst;
 lst.push_back(Piggy());
 Piggy & p = lst.back();
 p.mStr = new char[128];
 strcpy(p.mStr, "Test");
 

Это пройдет с QList, но не с QVector (std::vectior). Это может быть важно когда копирование по каким-то причинам недопустимо (напр др объект держит указатель на созданный элемент).

Ну а тогда какая разница между массивом С и темже контейнером QList? Он тоже memmove использует для этих же целей.

Разница та что в С (и векторе) можно получить указатель на массив, а с QList нет.

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

[Пантер]

Igors, тему выбрал исходя из начала обсуждения. Вроде, в начале, сравнивались массивы и контейнеры.
Можно тему и поменять, если нужно. Хотя, смысла не вижу.

[Igors]

Igors, тему выбрал исходя из начала обсуждения. Вроде, в начале, сравнивались массивы и контейнеры.
Можно тему и поменять, если нужно. Хотя, смысла не вижу.

Пантер, как хотите, у меня претензий нет. Просто слышу много писка, мол, "изобретаешь велосипед". "знание STL", "а вот в дусте можно и так" и.т.п. А по работе (на практике) получается куда не все так радужно и просто как в учебных примерах.  Никто не против выучить стандартное (не дураки тот же STL придумали) и спокойно пользоваться  - да вот не всегда получается  Где-то с 1 миллиона полигонов в сцене все проблемы/огрехи начинают (настойчиво) напоминать о себе. На 5 млн уже "как бы проскочить". На 10 - "надо что-то делать потому что так не годится".

[BRE]

Я вот читаю и не нахожу в тексте какие конкретно "проблемы/огрехи начинают настойчиво напоминать", для какого конкретно контейнера, при каком конкретно его использовании. Одна вода.... 

Igors, есть различные структуры хранения данных: списки, деревья, векторы, деки, ... Каждая структура обладает своими свойствами, плюсами и минусами. У каждой есть своя область применения.
Если ты выбрал для использования вектор (не важно в чьей реализации), напихал в него много данных и пытаешься удалять элементы в его середине, то ты, по-любому, получишь неплохие тормоза. И автор std::vector в этом будет совершенно не виноват.
Если ты изобретешь новую структур хранения данных, которая будет хоть чуть-чуть эффективней уже известных - опубликуй идею и в ближайшее время появятся куча качественных реализаций.

[Пантер]

1. Igors, не понял на счет выканья.
2. "Писк" немного оскорбляющее слово.
3. У тебя очень часто "сишный подход".
4. Тему я отделил не для того, чтобы над сишными массивами (или над тобой) поглумиться.

Отвлекусь:
Сейчас по работе пришлось столкнуться с несколькими проектами. В основном они написаны в духе "си с классами". Сегодня целый день провели (я с человеком, который ведет один из проектов) в поисках одного бага. Было очень тяжело искать баг в коде, в котором

Код

C++ (Qt)
char *XXX

передается из класса в класс, из функции в функцию, и не понятно кто создает/удаляет эту хрень.  (самое интересное, что утечек памяти нет - это означает, что программист мнооооооого времени провел за отладкой). В общем, баг был в том, что в один из моментов обращения к указателю валило прогу.
К чему это я?
Ну, с контейнерами такого бы не получилось. Т.е. вероятность бага снизилась бы.
Если пишешь на чем-то, то и используй средства этого языка. Ведь не очень красиво будет писать вот так:
"My imja is Panter. I'm zhivu in Russia. I l'ubl'u this forum".

[Igors]

Я вот читаю и не нахожу в тексте какие конкретно "проблемы/огрехи начинают настойчиво напоминать", для какого конкретно контейнера, при каком конкретно его использовании. Одна вода.... 

А у Вас? 

Igors, есть различные структуры хранения данных: списки, деревья, векторы, деки, ... Каждая структура обладает своими свойствами, плюсами и минусами. У каждой есть своя область применения.

Не вода ?    Но согласен, давайте более конкретно (ниже)

Если пишешь на чем-то, то и используй средства этого языка.

Я и не отказываюсь их использовать, просто часто вынужден искать др. ходы.

В посте #7 я уже привел конкретный пример и попросил показать решение. Ладно, давайте возьмем задачку попроще

Каждый элемент данных (facet) хранит массив точек переменной длины. Расклад примерно такой

1 точка (на элемент) - 2% (случаев)
2 точки - 2%
3 точки - 75%
4 точки -  20%
5 и более точек - 1%

Понятно что можно залепить QVector <QVector <Point>> - и все дела. Но на хороших объемах это работает плохо: медленно и жрет гораздо больше памяти чем требуют данные. В то же время мне нужно обращаться к элементу по индексу (т.е. прямой доступ). Какое бы решение Вы предложили?

Спасибо

[BRE]

С твоими требованиями, самое простое, это придумать свою структуру хранения данных, лишенную всяческих недостатков.  Этакий IdealContainer. 

Тебе с одной стороны хочется что бы памяти много не кушал, с другой стороны, что бы доступ был быстрым, а вставка/удаление выполнялось бы за O(1)....

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

[Waryable]

С твоими требованиями, самое простое, это придумать свою структуру хранения данных, лишенную всяческих недостатков.  Этакий IdealContainer. 

Тебе с одной стороны хочется что бы памяти много не кушал, с другой стороны, что бы доступ был быстрым, а вставка/удаление выполнялось бы за O(1)....

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

Странные рассуждения. Мне тоже иногда приходится писать свои велосипеды. Бывают проблемы, которые принципиально не решаемы с помощью стандартных вещей.