将std::string插入到std::map中

Question

我有一个程序，逐行从文件中读取数据。我想将该行的某些子字符串复制到下面的映射中：

std::map< DWORD, std::string > my_map;
DWORD index;         // populated with some data
char buffer[ 1024 ]; // populated with some data
char* element_begin; // points to some location in buffer
char* element_end;   // points to some location in buffer > element_begin

my_map.insert( std::make_pair( index, std::string( element_begin, element_end ) ) );

这个std::map<>::insert()操作需要很长时间（会使文件解析时间增加一倍）。有没有办法使这个操作更少的耗费资源？

谢谢, PaulH

编辑：具体来说，我想知道我是否正在执行最少的复制操作，以将数据从文件中存入映射中。

- PaulH

---

当你说它“加倍”解析时间时，“加倍”相对于什么？ - anon

@Space_C0wb0y - 这个文件大约有1.18Mb。这张地图大约有8200个条目。 - PaulH

@PaulH 如果你需要地图，那就得付出代价。毕竟，插入数据肯定不是一瞬间的事情。 - anon

@PaulH，你是真的在通过分析器运行你的代码还是只是计时？一个真正的分析器（例如callgrind）将为你提供更多关于额外成本的详细信息。 - Michael Kristofik

如果您不打算在初始读取后插入到映射中，则将所有数据读入向量，然后进行排序会更快。 - Martin Tilsted

Answer 1

也许你可以尝试使用字符串构造函数的另一个版本：

string ( const char * s, size_t n );

如果您的字符串实现没有针对char *进行专门处理，它将被强制遍历给定的范围并逐个复制每个字符。在这种情况下，上面的构造函数可能会更快（只是猜测而已）。

- Björn Pollex

Answer 2

你真的需要在这里使用地图吗？就我所看到的例子，你只想将索引存储为键值，而且我猜想这只是简单地增加每个插入的值。你可以使用已知为最快容器的std::vector来完成这个任务。只需使用push_back并使用at(index)访问值即可。

- Simon Linder

---

是的，我需要对数据进行排序和索引。 - PaulH

在向量中，它会根据元素的位置自动进行索引，并且还有一个插入方法，因此您可以对其进行排序。 - Simon Linder

向量不是“最快的容器”。在某些方面，它比其他一些容器更快。 - anon

Answer 3

你可以尝试以下几种方法，但需要注意数据结构和字符串本身的开销。

1. 它是否必须是一个map？你可以尝试使用std::tr1::unordered_map并查看是否有所改善。

2. 查询速度需要多快？如果可以接受O(n)的查询时间，可以尝试使用std::vector。

3. 是否需要存储每个子字符串的副本？可以只存储指针而不是副本。

- Michael Kristofik

---

1和2是的，我需要它被排序和索引。 3 - 指向什么？ - PaulH

@PaulH 你可以创建一个包含指向缓冲区的 char* 和长度的小结构体。将该结构体存储到映射表中，而不是直接存储字符串本身。这会需要将整个文件保留在内存中。 - Michael Kristofik

@PaulH，还要问问自己何时需要对其进行排序和索引。只要在容器中存储足够的信息以便在需要时查找和排序数据，它就不一定需要始终保持排序状态。 - Michael Kristofik

Answer 4

稍微回答一下你的补充问题。试着将map暂时改为字符串向量，然后计时将一个固定字符串值插入到向量中。例如：

vector <string> v;
string s( "foobar" );

your insert loop:
   v.push_back( s );

这应该给你一个关于速度可能性的下限。

另外，你应该在所有优化都开启的情况下计时（如果你还没有这样做）。这可以对许多标准库操作产生惊人的影响。

- anon

---

在 insert 循环之前不要忘记使用一个大致的大小来预留空间。 - Matthieu M.

Answer 5

如果您的编译器无法在插入中优化掉冗余副本，您可以使用括号运算符直接分配到映射中：

my_map[index].assign(element_begin, element_end)

编辑：正如Neil所指出的那样，如果可以插入重复的键，则这将没有帮助。

- Mark B

---

在赋值操作发生之前，这会创建字符串的冗余副本。 - anon

我同意它创建了一个冗余的默认构造字符串，但这应该比填充所有数据的字符串要便宜。两个迭代器的赋值难道不是直接赋值给字符串数据吗？ - Mark B

这里的问题在于insert() - 如果没有预先存在的键入口，那么使用迭代器创建的副本的复制构造函数将创建该入口（后者不可避免，前者可能会被优化）。如果有预先存在的键入口，则插入不执行任何操作。 - anon

Answer 6

我相信大部分与 map 相关的执行时间都花费在了字符串的复制上。 std::map 喜欢拥有自己的一份拷贝。所以当你插入时，std::map 会复制键和值。

很久以前，当处理器速度较慢、内存较小的时候，程序员会使用指针来传递“大型”数据项，而不是每次都复制数据。指针比字符串要小得多，并且需要更少的执行时间来复制。也许你应该在 map 中存储指向字符串的指针：

#include <map>
#include <string>
#include "boost/shared_ptr.hpp"

typedef boost::shared_ptr<string>    Shared_Str_Ptr;

typedef std::map< DWORD, Shared_Str_Ptr> Map_Container;

//...
Map_Container my_map;
Shared_Str_Ptr p_str(new std::string("Hello"));
my_map[5] = p_str;

shared_ptr 会为你处理内存管理，因此在删除 map 或其内容时不必担心。

另请参阅 Boost 智能指针。

- Thomas Matthews

---

请不要再使用智能指针容器了。当只需要一个实例时，在堆上创建std::string并对其进行引用计数的开销绝对不是您想要的。 - Matthieu M.

Answer 7

你正在存储字符串，但我猜你已经读取了它们并将它们添加到了映射中。这将导致复制。如果你在其中存储指向字符串的指针（string*而不是string），可能会更快。

- RvdK

---

OP仍然需要一个指向字符串对象的指针。这意味着需要进行复制。 - Michael Kristofik

当然。我试图建议优化从阅读写作的流程。没有无用的副本。因此，如果他是逐行阅读的话。将该行作为字符串存储在堆上。然后将字符串存储在映射中（复制）。最好将字符串存储在堆上，并在映射中存储指向该字符串的指针。 - RvdK

Answer 8

假设您需要将数据放入std::map<DWORD，std::string>中，那么是的，您正在执行最少的复制操作以将数据放入映射中。

- Magnus Hoff