std::multimap :: equal_range 的时间复杂度

Question

下午好，我想知道std::multimap::equal_range的时间复杂度是什么？是O(n)还是O(log n)。我记得阅读过std::multimap::erase的时间复杂度是“对于被删除的序列长度，它是对数加线性时间”。 <http://frank.mtsu.edu/~csjudy/STL/Multimap.html>

- Frank

Answer 1

C++03标准中，23.1.2节的表69（“关联容器要求”）表示，等值范围函数equal_range的时间复杂度为对数级别。

- Steve Jessop

---

Steve Jessop，感谢您的回复。如果我们的代码实际上解引用了一个错误的指针，那么可以说在Windows上会发生访问冲突，而在Linux上会发生总线错误/分段错误吗？以下是代码摘录：1.UnmapViewOfFile(PrevMapPtr); 2. TmpPrevMapPtr = PrevMapPtr; 3. typedef std::multimap<char *,Range>::const_iterator I; std::pair<I,I> b = mmultimap.equal_range(TmpPrevMapPtr); 4. for (I i=b.first; i != b.second; ++i){ ranges_type.erase(i->second); } 感谢您的帮助。 - Frank

Steve Jessop，感谢您的回复。如果我们的代码实际上解引用了一个错误的指针，那么可以说在Windows上会发生访问冲突，而在Linux上会发生总线错误/分段错误吗？以下是代码摘录：1.UnmapViewOfFile(PrevMapPtr); 2. TmpPrevMapPtr = PrevMapPtr; 3. typedef std::multimap<char *,Range>::const_iterator I; 4. std::pair<I,I> b = mmultimap.equal_range(TmpPrevMapPtr); 5. for (I i=b.first; i != b.second; ++i){ ranges_type.erase(i->second); } 6. erasecount = mmultimap.erase(TmpPrevMapPtr); 感谢您的帮助。 - Frank

Steve Jessop，非常抱歉我发布了两个版本的评论。如果您有时间，请查看刚才的评论。感谢您的帮助。 - Frank

@Steve Jessop，谢谢你的回复。昨天，在另一个关于同一主题的帖子中，你说：“不幸的是，在取消映射文件之前，你需要从multimap中删除那个键[char *指针]。或者你可以复制映射文件中的字符串，插入到map中，但如果你要这样做，还不如使用std::string。”所以我按照你的建议去做了，目前代码片段似乎运行正常。这个multimap被定义为std::multimap<char *,Range>，其中Range是一个类。谢谢。 - Frank

@Steve Jessop，这是Range类。谢谢。 class Range { public: Range(int low, int high, char* ptr = 0, char* mapptr = 0, int stamp = 0) { // [low,high] mLow = low; mHigh = high; mPtr = ptr; mMapPtr = mapptr; mStamp = stamp; }bool operator<(const Range& rhs) const { return mHigh < rhs.mHigh; } int getCaseNumber() const { return mCaseNumber; }private: int mLow; int mHigh; char* mPtr; char* mMapPtr; int mStamp; }; // class Range - Frank

Answer 2

equal_range 是一个 O(log n) 的操作，它返回 lower_bound 和 upper_bound 成对的迭代器范围。

这意味着它返回一个迭代器范围，从第一个大于或等于搜索关键字的键开始，并以第一个大于搜索关键字的键结束。

- Cory Nelson

---

equal_range 可以适用于任何类型。它使用你在 multimap 构造函数中提供的比较器 -- 如果默认的比较器 (less<T>) 对于 char* 类型不起作用，你需要定义自己的比较器。无论哪种方式，它都不需要进行哈希处理。 - Cory Nelson

@Frank，我在回答你的另一个问题中提供了一个适当的比较函数。 - Robᵩ

如果你想将char当作字符串来处理并按照顺序排列它们（而不是内存地址），你可以提供一个使用strcmp的函数对象（或者直接使用strcmp？），或者只需使用std::string代替char，其std::less能够正确工作。 - Christian Rau

@Christian Rau，感谢您的回复。问题是我们使用UnMapViewOfFile（TmpPrevMapPtr）使char *指针key无效。因此，该字符串现在是一个坏指针，所以我们不能使用strcmp？我们该怎么办？谢谢。 - Frank

@Frank：不幸的是，在取消映射文件之前，您需要从multimap中删除该键。或者您可以从已映射的文件中制作字符串副本，以插入到map中，但如果您要这样做，您可以直接使用std :: string。 - Steve Jessop

Answer 3

我从来没有找到比SGI STL程序员指南更好的信息来源。在这种情况下，您感兴趣的页面是排序关联容器概念页面，该页面在复杂性保证部分声明：

下界、上界和等价范围是对数的。[1]

...

[1] 这比关联容器提供的保证要强得多。关联容器中的保证仅适用于平均复杂度；最坏情况下的复杂度可以更大。然而，排序关联容器为最坏情况下的复杂度提供了一个上限。

- Oliver Seiler

---

@Olivier Seiler，谢谢您的回答。我刚刚接受了您的答案。谢谢。 - Frank

标准更具权威性，但 SGI 文档更加方便。有时您会遇到在此之间发生更改的内容，这可能会让您感到困扰。 - Steve Jessop

@Steve Jessop，如果您知道SGI和标准之间的具体差异，请回答https://dev59.com/82435IYBdhLWcg3wtCSQ？谢谢。 - Mark Ransom

@Mark：我已经标记了它，并且会尝试记住，但说实话，自从我安装了 Foxit 后，它可以在比 Adobe Reader 更短的时间内搜索 PDF 文档，我就不再经常使用 SGI 文档了 :-) - Steve Jessop