在C++效率结构中创建日历应用程序

Question

我正在用Qt/C++创建一个日历应用程序，我正在决定如何制作这些结构。

到目前为止，我所做的是:创建约会的排序向量(按开始日期升序排序)。

我想知道，如果我添加一个包含52个位置(每周1个)的std::map，并在每个位置中添加指向该周约会的指针向量，是否可以提高性能。例如，获得1月份的约会将在固定的时间内发生(某种程度上-接受前4周的所有指针)。缺点:每次用户编辑/删除/创建约会时，都必须重新构建该表。

我还可以使用向量搜索1月份开始的第一个约会，然后查找1月份的最后一个约会。然后，这将在线性时间(N)内发生。

我猜，当用户快速点击所有月份时，拥有一个映射表，可以快速填充他点击的每个月的约会，比从头到尾迭代向量更有效率。

也许我可以从我的向量中保留每个月的迭代器？

有什么建议吗？-另外，如果我把这个放错了地方，请原谅。

Answer 1

如果你不打算使用数据库，你可以尝试使用一个大的std::map<time_t, Appointment> (而不是time_t，你也可以使用其他更容易比较的时间类型)。std::map将在插入约会时对其进行排序。插入/查找/擦除只需要对数时间。

当您需要列出某个范围内的约会时(比如在2012年1月)，可以使用std::map::equal_range并提供一个只查看月份(或周或天)的比较函数。请注意，std::map::equal_range也具有对数复杂度。一旦你有了一对相同范围的迭代器，遍历每个结果的时间是恒定的。

如果可能存在具有相同开始时间的重复约会，则需要使用std::multimap。

作为一般的“最佳实践”指南，您应该努力以紧凑的数字格式(如time_t)存储日期/时间，并且仅转换为输入/输出目的。这与存储/计算整数、浮点数等数值的原理相同，只是出于输入/输出的目的而将它们格式化为字符串。如果您想使用方便的日期/时间包装类(可以轻松访问天、小时、分钟等)，那么可以查看Boost.DateTime库或C++11的std::chrono。这些日期/时间包装器应该已经定义了operator<，因此它们可以直接用作std::map中的键类型。

Answer 2

您可以尝试将平衡的二进制搜索树与键(年、月、日)结合使用，并将值作为约会的列表/向量。它应该会在访问的日子里给你带来O(logn)的复杂性。AFAIR、std::map和std::set (当然还有std::multiset)被实现为RB (或AVL)平衡二叉树。不过，你应该小心--这些结构的效率恒定得多，所以你必须对你的应用程序进行基准测试。