3

我有一个文件说它somefile.txt包含按排序顺序的名称（单个单词）。

我想在添加新名称后按排序顺序更新此文件。

以下哪项是最优选的方式，为什么？

用一个std::multiset

std::multiset<std::string> s;

std::copy(std::istream_iterator<std::string>(fin),//fin- object of std::fstream
          std::istream_iterator<std::string>(), 
          std::inserter(s, s.begin())); 

s.insert("new_name");

//Write s to the file

或者

用一个std::vector

std::vector<std::string> v;

std::copy(std::istream_iterator<std::string>(fin),
              std::istream_iterator<std::string>(), 
              std::back_inserter(v));

v.push_back("new_name");

std::sort(v.begin(),v.end());

//Write v to the file.
4

4 回答 4

9

多重集插入对象比向量慢，但它们保持排序。多重集可能比向量占用更多的内存，因为它必须保存指向内部树结构的指针。这可能并非总是如此，因为向量可能有一些空白空间。

我想如果您需要信息以增量方式增长，但始终准备好立即访问以便那么多集获胜。

如果您一次收集所有数据而不需要按顺序访问它，则将其推送到向量上然后排序可能更简单。所以要存储的数据有多动态才是真正的标准。

于 2013-08-08T20:28:27.577 回答
2 
std::string new_name = "new_name";
bool inserted = false;
std::string current;
while (std::cin >> current) {
    if (!inserted && new_name < current) {
        std::cout << new_name << '\n';
        inserted = true;
    }
    std::cout << current << '\n';
}
于 2013-08-08T20:31:45.040 回答
1

这两种选择基本上是等价的。

在性能关键的情况下，该vector方法会更快，但在这种情况下，您的性​​能很大程度上会受到磁盘的限制；您选择哪个容器并不重要。

于 2013-08-08T20:23:25.360 回答
0

从这家伙的测试中我可以看到，向量更快（http://fallabs.com/blog/promenade.cgi?id=34）。我建议你测试一下，自己看看。性能通常与平台有关，尤其是在这种情况下，与数据集有关。

从他的测试中，他得出结论，简单元素最适合矢量。对于复杂元素（例如超过 4 个字符串），multiset 更快。

此外，由于向量是大数组，如果您要添加大量数据，则可能值得考虑使用另一种类型的容器（例如链表或专门的 boost 容器，请参阅Is there a sorted_vector class，它支持 insert()等等？）。

于 2013-08-08T20:36:08.107 回答