c++ - 结构 vector 与结构 vector 的映射

Question

我正在制作一个小型项目程序，其中涉及输入稍后将保存到数据库中的引号(在本例中为 .txt 文件)。还有一些用户可以输入的命令，例如列表(显示作者的引用)和随机(显示随机引用)。

如果我使用 map ，这是结构(以作者字符串作为键):

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

如果我使用 vector 的话，这是结构:

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

注意:我在数据库中的最大引用数量是 200。(从文件导入)

我只是想知道哪种数据结构会产生更好的性能。我对 C++ 还很陌生，所以任何帮助将不胜感激!

Answer 1

对于您的数据量，从性能角度来看，这显然并不重要，但 multi_map 可能会让您编写更短、更易于理解和维护的代码。关于 vector 与 map 的一般性能(这是很好的了解，但可能只与数百万数据元素或低延迟要求相关)...

vector 不会为您进行任何自动排序，因此您可能会在阅读它们时使用 push_back 引号，然后执行一个 std::sort 数据加载后，您可以使用 std::binary_search 或 std::lower_bound 按作者快速查找元素，或者识别新元素的插入位置引用例如std::lower_bound，但如果您想在此后插入新的引号，则必须将现有的 vector 元素从该位置移开以腾出空间 - 这相对较慢。由于您只是根据用户输入进行一些临时插入，因此在 vector 中仅使用几百个引号来执行此操作的时间将完全微不足道。不过，出于学习编程的目的，最好了解一下 multimap 被安排为一种分支二叉树，其中指针链接数据元素，从而允许相对快速的插入(和删除)。对于某些应用程序来说，遵循所有这些指针可能比 vector 的连续内存(与 CPU 缓存内存配合得更好)更昂贵(即更慢)，但在您的情况下，数据元素可能都是字符串和字符串 vector (除非 Short字符串优化启动)无论如何都需要跳过所有内存。

一般来说，如果作者自然是您数据的关键，只需使用 multi_map...它会在合理的时间内完成您的所有操作，也许不是最快的，但绝不会特别慢，不像用于数据填充后中间容器插入(/删除)的 vector 。