我知道搜索已排序的向量比搜索未排序的向量要快得多。当向量存储字符串时，这是可以理解的。我的问题是假设向量存储对象或指向类对象的指针，例如人。这个类有两个属性，一个 SSN 和一个年龄。对于 (std::find_if) 的向量已经有两个谓词可用，一个用于搜索 SSN(string)，另一个用于搜索 age(int)。我的问题是对这种向量进行排序的最佳做法是什么。
问问题
185 次
4 回答
6
这里没有最佳实践。如果要按 SSN 搜索对象，请按 SSN 排序。如果要按年龄搜索对象，请按年龄排序。如果您想同时搜索（或者），请不要使用向量。使用来自Boost.MultiIndex.
顺便说一句，如果您使用二分搜索（或），而不是线性搜索，则只有在已排序的向量上lower_bound搜索upper_bound会equal_range更快find_if。
于 2013-09-14T18:28:16.370 回答
2
这取决于您对向量的使用，如果您必须根据年龄进行搜索，则使用年龄，如果是 SSN，则使用 SSN。
不过，如果您使用 SSN（为什么不使用整数？），最佳实践可能是使用 std::unordered_map。
那是因为 SSN 是唯一的。
于 2013-09-14T18:27:12.913 回答
1
当你想对某个东西进行排序时，最好的做法是首先问自己：什么函数应该确定是否 a < b？
定义函数并将其用于排序。
于 2013-09-14T18:54:09.570 回答
0
迁移到“更重”的多键数据结构的缺点之一是（如 Boost.MultiIndex 提供的那些），您可能会失去一些局部性和性能，具体取决于您的使用情况。
考虑容器的元素数量和访问模式。
如果您正在构建一个容器，然后以后不再修改它，而是进行大量查找，您可能会发现简单地创建和填充vector、制作副本以及以不同方式对两个副本进行排序可能是您想要的。（如果您想避免重复完整数据副本的开销，并且不介意一个额外的间接级别，您可以考虑让您的容器包含shared_ptr.)
如果您倾向于一次执行大量Age查询，然后切换到SSN查询，也许以一种方式排序，执行查询，以另一种方式排序，然后执行其他查询就可以了 - 再次，这取决于排序之间的查询数。
如果您的数据结构足够小（几十个或更少），您可能会发现对您的一种查找类型进行线性搜索就可以了，并且您可以对vector另一种类型的查找进行排序 - 特别是如果您倾向于偏爱一种查找方式。
您也可以考虑将您的内容拆分Person成几部分——有点像数据库规范化——并拥有一个“仅”包含SSNs 和某种句柄或 的容器，另一个容器PersonKey不只包含Ages 和键，最后一个容器包含钥匙和其余的。这有助于使您的搜索非常本地化（参见“结构数组”与“数组结构”）。
这些中的每一个都可能增加代码复杂性和维护成本，因此通常的“您的里程可能会有所不同”声明适用。您可能会在使用这些解决方案中的任何一个进行权衡。
于 2013-09-14T18:54:47.740 回答