c++ - 什么对我来说更好 : vector or list?

Question

我有一个函数可以读取文件夹中的文件(为此我正在使用 boost)。我也试图只保留 2 个文件(它们是日志文件，所以它们被轮换，我不想保留旧日志 = 第三个文件中的日志)。我将文件名存储在一个列表中，但由于读取不是按创建时间顺序完成的，因此我需要对列表进行排序。

我知道

Vectors are good at:

• Accessing individual elements by their position index (constant time).
• Iterating over the elements in any order (linear time).
• Add and remove elements from its end (constant amortized time).

和

Advantages to list containers:

• Efficient insertion and removal of elements anywhere in the container(constant time).
• Efficient moving elements and block of elements within the container or even between different containers (constant time).
• Iterating over the elements in forward or reverse order (linear time).

---

我不确定最好的方法是什么:使用列表还是 vector ？

我要吗

• 使用 vector 并对其进行升序排序、从末尾删除、添加新元素(在末尾)、重新排序等；或
• 使用列表并对其进行升序排序，从头开始删除，在末尾添加新元素，resort等；

---

• 是否只在开头需要排序，因为我插入的每个文件名都是最后创建的？
• 如果 list/vector 是排序的，求助的时间是多少？
• 如果我使用 std::is_sorted 可以不每次都排序吗？

---

更多信息:

因为boost的文件轮换没有“如果文件太多则删除文件”状态，只有“磁盘空间足够”，我实现了保留最后两个文件或每次删除最旧文件的步骤创建了新的，并且有 2 个日志文件。所以每次创建一个新的日志文件时，我都会验证文件列表，如果有足够的(2 个或更多)就删除旧的。因为文件的名称是 logs_%N.log，所以我不知道文件 logs_X1.log 是否比 logs_X2.log 旧/p>

eg: I restart the applications, there are the files logs_51.log, logs_52.log, which one is going to be deleted? Supposing it is going to delete logs_51.log and create logs_0.log, if I restart it again, there will be logs_52.log and logs_0.log. Which one is going to be deleted now?)

这就是我需要排序的原因，因为应用程序可能会重新启动，而我读取现有文件，完成具有更多空间的文件，然后创建一个新文件。

Answer 1

对于这种特殊情况，容器将包含 ~2 个元素，一点点都没有关系。枚举文件和删除它们所花费的时间将比您选择的算法和数据结构慢几个数量级。只需将文件名放在 std::vector 中，使用 std::sort(它将对您的日志文件名进行排序，以便最早出现在前面)，然后删除N-2 第一项。工作完成。

但对于一些一般性建议:

现在一般的建议似乎是 std::vector 比 std::list 更好，甚至在很多事情上 std::list 似乎对它有好处，主要是因为它是连续存储，对缓存更友好。

可以构建显示 std::list 更快的基准测试，但是如果您为所有内容选择 std::vector 就不会出错!

如果您需要随着时间的推移维护一个容器并且总是需要能够移除最小/最大的元素，std::priority_queue 可能是个好主意。

如果您需要在容器中找到 N 个最小/最大的项目，std::partial_sort 是一种算法；它会比完整的 std::sort 更快，因为它不会浪费精力对您不关心的元素进行排序。

但是对于像这样的所有一般性能问题，恐怕唯一正确的答案必须是“试试看”!

编辑:我最初建议使用 boost::circular_buffer 因为问题听起来就是这样，但现在很明显这不是一个好的建议，因为需要通过排序而不是插入顺序来创建顺序.