Контейнерные классы

[8Observer8]

Привет!

Текст из книги Макса Шлее "Профессиональное программирование на С++. Qt 4.8":

При  создании объекта  класса  QMap<K,T>
  нужно передать  его  размер в конструктор. Этот
размер не является, как это принято в других контейнерных классах, размером, ограничи-
вающим максимальное  количество элементов,  а представляет  собой количество позиций.
Количество позиций должно быть больше количества элементов, ожидаемых для хранения,
иначе поиск элементов в словаре будет проводиться недостаточно эффективно. Желатель-
но, чтобы это значение относилось к разряду простых чисел, т. к. в этом случае размещение
элементов будет более  удобным  (см. приложение 2)

Мне тут каждое предложение непонятно.

При  создании объекта  класса  QMap<K,T>
  нужно передать  его  размер в конструктор.

Зачем передавать размер?

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

В каких контейнерах требуется передать число, которое ограничит "максимальное  количество элементов"?
Есть ли разница между "максимальным  количеством элементов" и "количеством позиций"?

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

Зачем задавать количество элементов? А если я не знаю ожидаемое число элементов, то насколько снизится эффективность в тех случаях, когда я не знаю ожидаемое число элементов и когда я его знаю (и могу выделить память заранее)?

Зачем выделять больше места для хранения, чем ожидается? Почему тогда разработчики QMap не учли, что нужно выделять больше? То есть если я выделяю столько-то, то на самом деле бы выделялось больше. А на сколько больше нужно указать?

Желательно, чтобы это значение относилось к разряду простых чисел, т. к. в этом случае размещение
элементов будет более  удобным  (см. приложение 2)

Признаюсь "приложение 2" ещё не читал, но очень интересно стало, почему именно простые числа (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 и т.д.)?

Помогите прояснить эти вопросы. Заранее спасибо!

[Igors]

Не вижу никакого параметра "размер" подаваемого в QMap - ни в Qt 4.7 ни в Qt 5.2. Также не знаю ни одного контейнера (ни в std ни в Qt) с ограничениями по размеру, все они растут пока не исчерпается память, затем выбрасывают исключение.

Вы что, обнаружили что Ваш QMap ищет недостаточно быстро? Если до этого дело не дошло - не занимайтесь фигней. Польза от пролистанных книг невелика. И не покупайтесь на слово "профессионально", что совсем не значит "круто" 

[lit-uriy]

8Observer8, про контейнерные классы читай в доке, а не у Шлее.

[8Observer8]

Igors, спасибо! Буду стараться вникать.

lit-uriy, спасибо большое за ссылку! Я как раз читаю эту документацию на английском. Теперь будет проще. Жалко не перевели тему "Неявное разделение данных"

У Шлее есть параграф "Модель общего использования данных" Он всё верно описал?

Из соображений эффективности во многих классах Qt избегается копирование данных, вме-
сто этого используется ссылка на эти данные (см. рис. 4 .12). Этот принцип получил назва-
ние общее использование данных  (shared  d ata). В Qt используется модель неявных общих
данных. В этой модели вызов конструктора копирования или оператора присваивания не
приведет к копированию данных, а только увеличит счетчик ссылок на эти данные на 1.
Соответственно, при удалении элемента счетчик ссылок уменьшится на 1. Если значение
счетчика ссылок становится равным 0, то данные уничтожаются. Копирование данных про-
исходит  только  при  изменениях,  соответственно  значение  счетчика  ссылок  при  этом
уменьшается.
На рис. 4.12 на первом шаге создаются два объекта, и т. к. данные им не были присвоены,
то они оба указывают на  shared_null (общий ноль). На втором шаге первому объекту при-
сваиваются данные, счетчик ссылок становится равным единице. На третьем шаге второму
объекту присваивается первый объект, и они теперь оба указывают на одни и те же данные,
счетчик ссылок при этом увеличивается на единицу. На четвертом шаге производится из-
менение данных первого объекта, что приводит  к созданию для него отдельной  копии, а
счетчик ссылок старых данных уменьшается на один, т. к. на один объект, использующий
эти данные, стало меньше. Если бы мы пятым шагом изменили данные второго объекта, то
после создания копии для новых данных счетчик ссылок старых данных уменьшился бы до
значения 0, и это привело бы к освобождению памяти и уничтожению старых данных.

Проиллюстрируем изображенную на рис. 4.12 ситуацию программным кодом:

Код:

QString str1;          // Ссылается на shared_null 
QString str2;          // Ссылается на shared_null 
str1 = "Новая строка"  // Ссылается на данные, счетчик ссылок = 1 
str2 = str1;           // str1 и str2 указывают на одни и те же данные 
                       // счетчик ссылок = 2 
str1 += " добавление"; // Производится копирование данных для str1

[m_ax]

Также не знаю ни одного контейнера (ни в std ни в Qt) с ограничениями по размеру..

std::array http://ru.cppreference.com/w/cpp/container/array

[Serr500]

У Шлее есть параграф "Модель общего использования данных" Он всё верно описал?

Да. Всё верно.

[8Observer8]

Спасибо за ответы!

Хочу научиться применять контейнеры и алгоритмы наиболее эффективно. Прошу мне помочь. Накидайте, пожалуйста, ссылок на ресурсы и книжки по Tulip и STL. Может вам попадались ресурсы где бы на практике тестировались STL и Qt контейнеры. Как здесь: http://microfork.com/stdvector-stdlist-stdqueue-preformance-analisys/

Вот какие материалы у меня сейчас под рукой:

1. Не жалею, что прочитал обзорную главу "Контейнерные классы" из книги Макса Шлее

2. Документация по Qt контейнерам на русском: http://www.doc.crossplatform.ru/qt/4.6.x/containers.html

3. Анализ производительности std::vector, std::list и std::deque: http://microfork.com/stdvector-stdlist-stdqueue-preformance-analisys/

4. Алгоритм выбора STL-контейнера: http://habrahabr.ru/company/infopulse/blog/194726/

5. Главы под названиями:
- "Chapter 11: Delving into the Standard Library"
- "Chapter 12: Understanding Containers and Itarators"
- "Chapter 13: Mastering STL Algorithms"
из книги Professional C++ (2nd Edition, 2012). В книге параллельно рассматривается C++11
Ссылка: http://kickass.to/wrox-professional-c-plus-plus-2nd-edition-2011-retail-ebook-debt-t7461950.html
Исходники: http://www.wrox.com/WileyCDA/WroxTitle/Professional-C-2nd-Edition.productCd-0470932449,descCd-DOWNLOAD.html

6. Книга целиком об STL: "Эффективное использование STL"
Ссылка: http://rutracker.org/forum/viewtopic.php?t=956876

[Igors]

Хочу научиться применять контейнеры и алгоритмы наиболее эффективно. Прошу мне помочь. Накидайте, пожалуйста, ссылок на ресурсы и книжки по Tulip и STL.

Да я не видел и половины того что Вы привели   (спасибо за полезные ссылки). Но теория и практика - разные вещи. Вот простая задачка из жизни:

- есть структура данных Facet, которая содержит N чисел int. На практике частота N распределена примерно так

- 3 числа (triangle) 80%
- 4 числа (quad) 15 %
- 1 или 2 числа  (particle) 4%
- 5 и более (complex) 1%

Какой контейнер Вы бы использовали для хранения массива структур Facet (и как организовать саму структуру) ?  Операции вставки/удаления редки (хотя имеются)

[8Observer8]

Igors, спасибо большое за задачку Я подумаю.

[8Observer8]

Вот, что пишут про неупорядоченные ассоциативные контейнеры (хэш-контейнеры) из C++11 (из книги Professional C++)

Insertion, deletion, and lookup with these unordered associative containers can be done on average
in constant time. In a worst case scenario it will be in linear time. Lookup of elements in an
unordered container can be much faster than with a normal map or set, especially when there are
lots of elements in the container.

Речь идёт об этих контейнерах:
- unordered_map
- unordered_set
- unordered_multimap
- unordered_multiset

Вопрос об "усреднённом поведении (времени)". Правильно ли я понимаю (из текста выше), что если я вызову функцию вставки один раз, то получу самый наихудший вариант - линейное время? А если буду вызывать функции удаления и вставки столько раз сколько элементов в контейнере, то получу время, которое не зависит от количества элементов (константное время)?

В цитате выше ещё написано, что поиск по хэш-контейнерам может быть выше, чем для нормальных map и set, особенно если много элементов. Получается, что если мне нужно часто искать и контейнеры большие, то лучше использовать хэш-контейнеры? Тогда я получу константное время поиска, вместо логарифмического?

А что здесь имеется ввиду под словом "Lookup"? Это может быть поиск с помощью функции find(), а может быть доступ к элементам.

[8Observer8]

Что такое "LOOKUP PERFORMANCE"? Это доступ к элементу по индексу или поиск элемента с помощью find()?

[lit-uriy]

LOOKUP - поиск (по ключу)

[Igors]

Igors, спасибо большое за задачку Я подумаю.

Ну вот, думал человек за ум взялся. Ан нет  

Вот, что пишут про неупорядоченные ассоциативные контейнеры (хэш-контейнеры) из C++11 (из книги Professional C++)

Опять Professional = круто. Реально используются

- вектор
- QList
- мапа
- хеш
- set (реже)
- список (иногда)

В Qt или std варианте (кто что любит). Эти контейнеры покрывают по меньшей мере 90% потребностей, и это, в общем, правильно. Злоупотребления в основном с вектором - напр нередко дека заметно лучше. Также выбор между мапой и хешем часто в пользу хеша, все читали что он "быстрее" - но это может быть и не так.

Ну чего Вы лезете в фантастику типа  unordered_map ?   Может полагаете что используя его Вы сделаете нечто супер-быстрое? Напрасно. Качество и скорость определяются не "широтой" используемых средств, а тем насколько хорошо они соответствуют данным. Один и тот же контейнер может быть очень хорош для одних - но столь же плох для других.

А сейчас у Вас "пальба по площадям". Выучите напр тот же QHash, прочувствуйте чем он хорош и плох, а еще лучше - напишите свой. Тогда вопросы с "unordered" собой отпадут - это всего лишь вариации того же кеша. Да, lookup - это просто поиск по ключу.

В общем, я всегда говорил - надо меньше забивать голову книгами  

[lit-uriy]

Получается, что если мне нужно часто искать и контейнеры большие, то лучше использовать хэш-контейнеры?

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

[OKTA]

Но теория и практика - разные вещи. Вот простая задачка из жизни:

- есть структура данных Facet, которая содержит N чисел int. На практике частота N распределена примерно так

- 3 числа (triangle) 80%
- 4 числа (quad) 15 %
- 1 или 2 числа  (particle) 4%
- 5 и более (complex) 1%

Какой контейнер Вы бы использовали для хранения массива структур Facet (и как организовать саму структуру) ?  Операции вставки/удаления редки (хотя имеются)

Чего-то маловато входных данных для задачки