Карта вектора struct vs Vector of struct

Question

Я делаю небольшую проектную программу, которая включает в себя ввод кавычек, которые впоследствии будут сохранены в базе данных (в этом случае .txt-файл). Существуют также команды, которые пользователь вводит, например, список (который показывает цитату автора) и случайный (который отображает случайную цитату).

Вот структура, если я хотел бы использовать карту (с автором строки в качестве ключа):

struct Information{ 
    string quoteContent; 
    vector<string> tags; 
} 

и вот структура, если я хотел бы использовать вектор вместо:

struct Information{ 
    string author; 
    string quoteContent; 
    vector<string> tags; 
} 

примечание : Наибольшее количество котировок, которые у меня были в базе данных, - 200. (импортировано из файла)

Мне просто интересно, какая структура данных даст лучшую производительность. Я все еще довольно новичок в этой вещи C++, поэтому любая помощь будет оценена!

Answer 1

Для ваших объемов данных это, очевидно, не имеет значения с точки зрения производительности, но multi_map, скорее всего, позволит вам писать более короткий, понятный и удобный код. Что касается общей производительности векторных карт (что полезно знать, но, скорее всего, становится актуальным только для миллионов элементов данных или требований с низкой задержкой) ...

vector не производит автоматическую сортировку для вас, поэтому вы 'd возможно, push_back кавычки, когда вы их читаете, затем сделайте один std::sort после загрузки данных, после чего вы можете быстро найти элементы с помощью std::binary_search или std::lower_bound или определить позиции вставки для новых котировок, используя, например, std::lower_bound, но если вы хотите вставить новую цитату после этого, вам нужно переместить существующие векторные элементы из этой позиции, чтобы освободить место - это относительно медленно. Поскольку вы просто делаете несколько ad-hoc-вставок на основе пользовательского ввода, время для этого всего лишь с несколькими сотнями котировок в векторе будет совершенно несущественным. В целях изучения программирования, однако, хорошо понимать, что multimap устроен как разновидность ветвящегося двоичного дерева с указателями, связывающими элементы данных, что позволяет относительно быстро вводить (и удалять). Для некоторых приложений, следующих за всеми этими указателями, может быть более дорого (т.медленнее), чем смежная память вектора (что лучше работает с кэш-памятью процессора), но в вашем случае элементы данных представляют собой все строки и векторы строк, которые, вероятно, (если не будут задействованы короткие оптимизаторы строк), требуют переполнения всей памяти в любом случае.

В общем, если автор, естественно, является ключом для ваших данных, просто используйте multi_map ... он сделает все ваши операции в разумные сроки, возможно, не самый быстрый, но не особенно медленный, в отличие от вектора для пост-данных- вставки в середине контейнера (/ удаления).

Answer 2

В зависимости от цели использования. Обе структуры данных имеют свои плюсы и минусы.

Vectors

• индекс положения в() или оператор []
• Функция поиска нет Вы должны использовать найти алгоритм FUNC.

Карты:

• Ключ можно найти
• индекс Положение не применяется. Ключи хранятся

(используйте неупорядоченную карту для лучшей производительности, чем карты.)

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

Answer 3

Золотое правило: «Когда сомневаетесь, измерьте».
Т.е. напишите несколько тестов, сделайте некоторые бенчмаркинга.

В любом случае, учитывая, что у вас около 200 предметов, я не думаю, что должно быть важное отличие от двух случаев на современном оборудовании для ПК. Big-O обозначение имеет значение, когда N большой (например, 10,000s, 100,000s, 1,000,000s и т.д.)

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

Другим вариантом может быть, чтобы иметь vector с элементами сортировки, используя имена автора, так что вы можете использовать бинарный поиск (который O (LogN)) внутри vector.