Russian Qt Forum

Скажите, а почему Вас совершенно не волнуют соображения эффективности? Хотели ли мы освободить память занимаемую указателями? Не всегда, как показывает пример. Зачем тогда столько эмоций?  :)

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

Igors, использование контейнеров в с++ и "говнокод" это совершенно разные вещи.
ИМХО!
Нужно пользоваться контейнерами. Вектор занимает столько же памяти, сколько и обычный массив. Вот если производительность критична и доказано, что отказ от контейнера повысит ее, то тогда и только тогда стоит использовать си-подобный код.

Вектор часто занимает заметно больше памяти т.к. ему нужен пул чтобы эффективно расти. Может не устроить что нельзя использовать указатель на элемент вектора (при добавлении/удалении элементов). Удаление из вектора катастрофично по скорости. Поведение вектора (да и др. контейнера) трудно знать точно. Очищает ли память clear()? Сколько раз вектор перераспределит память если добавить в него напр 100К элементов? На злополучной Вындоуз платформе добавляются еще проблемы. Конечно, для большинства задач все эти мелочи несущественны, но не для всех.

Раньше это звучало немного иначе
:)

> Вектор часто занимает заметно больше памяти т.к. ему нужен пул чтобы эффективно расти
man vector::reserve
> Может не устроить что нельзя использовать указатель на элемент вектора (при добавлении/удалении элементов).
Тут немного не понял
> Удаление из вектора катастрофично по скорости
man vector::pop_back. Из массива ты вообще удалить ничего не можешь. ;)
> Поведение вектора (да и др. контейнера) трудно знать точно
Уверен? Откуда такие данные?
> Очищает ли память clear()?
Вроде, это не оговаривается. Можно вызвать vector::reserve. Есть еще хорошее решение через swap.
> Сколько раз вектор перераспределит память если добавить в него напр 100К элементов
Смотря как добавить.
> На злополучной Вындоуз платформе добавляются еще проблемы
Подробнее, пожалуйста.

На крайний случай можно написать свой Allocator.
Я не навязываю, а высказываю свою точку зрения. Есть предложение перенести спор в другую ветку, где можно продолжить дискуссию.

Очень часто при инспекции кода я прошу переписать сишные массивы на контейнеры. Т.к. там уже есть ошибка, или она с большой вероятностью появится. Я приветствую использование сишных массивов только в одном случае - приложение работает медленно -> мы провели анализ -> выяснили, что узкое место это работа с контейнером -> переписали на сишные массивы -> написали длинный коментарий почему мы так сделали.

P.S. Это только моё мнение, а не первый удар в холеваре  ;)

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

Фух, чуть не запорол тему. Не делал еще такого разделения тем.
Igors, твой ход. ;)

Пантер, спасибо за хлопоты


1) reserve, resize - то да, но когда размер фиксирован и известен - не такая уж большая выгода по сравнению с обычным массивом (ну удобный деструктор, можно выскочить по exception). А вот когда добавляем/удаляем - имеем проблемы с производительностью и перерасходом памяти. erase() вообще ужасен. QList обещает "быстрое" удаление - но то по сравнению с тем ужасом.

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

2) По поводу хранения указателей на элементы вектора. Это "плохая привычка", храните индексы. Хорошо, вот живой пример.

C++ (Qt)
// треугольник хранит индексы 3 точек
struct Triangle {
 size_t  mIndices[3];
};
 
typedef QVector3D Vertex;
 
// простая 3D модель
struct CModel {
 QVector <Vertex> mVertices;  // вектор 3D точек
 QVector <Triangle> mTriangles;  // вектор треугольников
};
 

Теперь мы каким-то образом обнаружили что некоторые точки и/или треугольники нужно удалить. Просто так нельзя - ведь индексы уплывут. Каким образом мы можем это сделать с нашими прекрасными контейнерами? Или вектор здесь не подходит? Хорошо, возьмите любой другой std или Qt.

3) Я не утверждал что нужно использовать "просто массивы" вместо контейнеров. В большинстве случаев выход - написание своего контейнера.

Я правильно понял, что спор окончен, т.к. все стороны согласны, что нужно использовать контейнеры?  ;)

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

1. Ты сам привел выгоды: . Этого уже вполне достаточно.
1.1 Разве в QList удаление приводит к сдвигам?

QList организован как вектор. Если удалять в середине, то будет сдвигать.

Да, просто он сдвигает массив адресов (или POD) что дешевле

Разве приведенный мной пример ну такой уж "специальный случай" (аж 2 структуры)? По-моему так он очень заурядный. Вот и покажите мне богатырскую силу контейнеров для такой простенькой задачки - удалить ненужные точки/треугольники  :)

Если взять этот код (как ты его называешь "в стиле C") и обернуть его в класс, то получиться контейнер. Эффективность этого контейнера (!) сильно пострадает по сравнению с тем кодом "в стиле С"?

То всего лишь "как назвать", непринципиально. Проблемв пользоваться стандартным или городить свое (жизнь заставляет)

Знатоки STL/Boost/Assistant и др. - ну где де же Вы? Покажите мне "велосипедисту" как грамотно решить задачу в посте #7 (крутые итераторы, лямбда и все такое). А то вот у меня что-то со стандартным вектором выходит сложно и длинно  :)

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

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

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



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


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

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

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

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

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

memcpy()
realloc() + memcpy()

А как ещё? :)

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

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

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


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

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

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

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

Спасибо за 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 нет.

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

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

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

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

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".

А у Вас?  :)

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

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

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

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

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

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

Спасибо

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

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

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

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

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

Ну вот, опять задачка не понравилась - видите ли, требования у меня завышенные. Уж и не знаю как угодить  :) А ведь там несложно и решений не одно. Ладно, вот еще случай (классический).

Есть такая структурка

C++ (Qt)
struct Vertex {
 QVector3D mPosition;   
 QVector3D mNormal;    
 QVector3D mTexture;   
 QVector3D mBlur;   
 ARGB mColor;
 ..
};
 

Дело в том что mPosition есть всегда и всегда значима. А вот все остальное может быть - а может и не быть в любых вариациях. Напр. mTexture может иметься а mColor нет, или наоборот - как фишка ляжет. Варианты:

1) Держать всегда все данные (как определена структура выше). Это конечно очень просто и это будет работать. Но признавать свою беспомощность не хочется

2) Разделить все на отдельные контейнеры (mPosition в одном, mNormal в др. и.т.д). Это ведет к заметному усложнению др. частей кода - я везде буду обязан работать только "по индексу" а не "по указателю". Это не очень приятно.

3) Ваше решение ?

Заметим что на "чистом С" решение довольно просто. А как это решить на ++ (которое вроде круче) ?

Спасибо

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

А это не задачка, это требование типа "хочу что-бы все было зашибись само и сейчас".  :)
Да и угождать мне не надо, особенно "своими задачками".

В лоб:

C++ (Qt)
struct Vertex
{
 QVector3D mPosition;   
 QVector3D *mNormal;    
 QVector3D *mTexture;   
 QVector3D *mBlur;   
 ARGB *mColor;
 ..
};
 

Чуть подумав:

C++ (Qt)
class Vertex
{
public:
 void addProperty( ... );
 void removeProperty( ... );
 
private:
 QVector3D mPosition;
 QList<Propertiy> mProperties;
};
 

Ну и хочеться уже взглянуть на что-то из этого:  ;)


Так сказать хочется увидеть твой кунг-фу "чистый С". В свое время я был большим ценителем, да и сейчас люблю насладится красотой хорошего кода.

Детский сад.  ::)

Давайте посчитаем байты

sizeof(QVector3D) = 12  (3 float)
sizeof(ARGB) = 4 (по байту на канал)

С использованием указателей каждый член весит уже 20 байт (32 бит) или 24 (64 бит). Немного сэкономили "когда данных мало", зато раздули почти вдвое "когда есть". Итого: памяти съедается не меньше "зато" добавили забот с указателями.

Конечно покажу - но когда Вы перестанете злиться (понимая что Вы не правы  :))

А почему для комментирования было выбрано решение "в лоб"?  :)

Я совершенно не злюсь.  :)
Хотя надежда увидеть код почти покинула меня. И мне все больше кажется, что тот абзац из первого сообщения этой темы, обычный треп или попытка произвести на кого-то впечатление. Да?  :)

Ну так Ваше "не в лоб" (чуть подумав) еще хуже по всем статьям  :)

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

По поводу реализации - здесь никакой "интриги" нет. Ну предположим каждый вертекс может иметь свой расклад.

C++ (Qt)
struct Vertex {
 size_t GetSize( void )  const { return theGlobalVertexTable[mTableIndex].GetSize(); } 
 
// ой как бы здесь заверещала наша малышь  :)
 Vector3D * GetNormal( void )  { return theGlobalVertexTable[mTableIndex].GetNormal((char *) this); } 
 ,,,
 
// data
 Vector3D mPosition;   // постоянные данные
 UInt32 mTableIndex;   // индекс расклада в таблице
};
 
struct VertexTableEntry {
 size_t GetSize( void ) const { return mSize; }
 Vector3D * GetNormal( char * src )  { return (Vector3D *) (mNormalOffset ? (src + mNormalOffset) : NULL);  } 
...
 
// data
 size_t  mSize;
 size_t mNormalOffset;
 ...
};
 

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

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

Ну а пример... это пять.