- mongodb - 在 MongoDB mapreduce 中,如何展平值对象?
- javascript - 对象传播与 Object.assign
- html - 输入类型 ="submit"Vs 按钮标签它们可以互换吗?
- sql - 使用 MongoDB 而不是 MS SQL Server 的优缺点
我刚刚发现 std::map.insert 可以接受一个迭代器作为其第一个参数作为插入过程的搜索提示,例如 map.insert(hintIterator, insertElement);
。但是提示元素有位置要求吗?它需要在插入位置之前还是之后?顺便问一下,提示迭代器位置对插入效率有多大影响?
最佳答案
它可以是 begin()
中的任何位置至end()
.如果传入与理想插入位置相对应的迭代器,则可以大大提高搜索正确位置的插入成本。
来自 SGI STL网站
Complexity guarantees
Insert with hint is logarithmic in general, but it is amortized constant time if t is inserted immediately before p.
要了解为什么会这样,请考虑正在应用的算法。 std::map
具有按某种顺序排列的项目,并且为了找到正确的插入点,必须遍历项目,直到找到一个位置(“A”)必须在新数据之前并且下一个项目(“B”)必须跟着它。预先给定这个位置,可以消除搜索。
新数据必须在这两项之间进行,并更新它们之间的链接。至少(对于可向前迭代的容器)项目 A 必须更新为指向新数据,该数据随后指向 B。如果包含的内容是可反向迭代的,则 B 也必须更新为指向新数据。
应该如何指定位置?必须知道 A 或 B。正如 Cubbi 指出的,并在 alt.comp.lang.learn.c-cpp 上讨论过2003 标准在提示应该是什么方面有所不同。 SGI 文档建议 B 是需要的,而标准建议 A。可能(假设 std::map
具有双向迭代器)这并不重要。不过,我建议较低项目 (A) 的位置最好,因为您始终可以期望能够继续向前搜索。
更新:由于有根据的猜测在得到验证之前是无用的,所以这里有一个快速测试:
#include <ctime>
#include <map>
#include <iostream>
int main() {
typedef std::map<unsigned int,unsigned int> map;
const unsigned int k=100000;
const unsigned int reps=10;
// Avoid edge cases by padding either end
map srcMap;
{
for(unsigned int i=0; i!=k;++i) {
srcMap.insert(std::make_pair(i,i));
}
unsigned int l=3*k;
for(unsigned int i=2*k; i!=l;++i) {
srcMap.insert(std::make_pair(i,i));
}
}
std::cout << "Hint is always the position of the preceding value\n";
for(unsigned int i=0; i!=reps;++i)
{
map testMap(srcMap);
map::iterator p=testMap.lower_bound(k-1);
unsigned int l=2*k;
std::clock_t start = std::clock();
for(unsigned int i=k; i!=l;++i) {
p=testMap.insert(p,std::make_pair(i,i));
}
std::clock_t end = std::clock();
std::cout << static_cast<double>((end - start) ) << " ";
}
std::cout << std::endl;
std::cout << "Hint is always the position of the following value\n";
for(unsigned int i=0; i!=reps;++i)
{
map testMap(srcMap);
map::iterator p=testMap.lower_bound(2*k);
unsigned int l=k-1;
std::clock_t start = std::clock();
for(unsigned int i=2*k-1; i!=l;--i) {
p=testMap.insert(p,std::make_pair(i,i));
}
std::clock_t end = std::clock();
std::cout << static_cast<double>((end - start) ) << " ";
}
std::cout << std::endl;
std::cout << "Hint is always the start of the container\n";
for(unsigned int i=0; i!=reps;++i)
{
map testMap(srcMap);
unsigned int l=2*k;
std::clock_t start = std::clock();
for(unsigned int i=k; i!=l;++i) {
testMap.insert(testMap.begin(),std::make_pair(i,i));
}
std::clock_t end = std::clock();
std::cout << static_cast<double>((end - start)) << " ";
}
std::cout << std::endl;
std::cout << "No hint\n";
for(unsigned int i=0; i!=reps;++i)
{
map testMap(srcMap);
unsigned int l=2*k;
std::clock_t start = std::clock();
for(unsigned int i=k; i!=l;++i) {
testMap.insert(std::make_pair(i,i));
}
std::clock_t end = std::clock();
std::cout << static_cast<double>((end - start)) << " ";
}
std::cout << std::endl;
return 0;
}
在我运行 MinGW GCC 4.5 的小上网本上,我得到了:
Hint is always the position of the preceding value
94 109 109 109 109 109 110 110 110 94
Hint is always the position of the following value
109 94 109 94 110 110 109 109 110 110
Hint is always the start of the container
188 172 172 187 172 172 235 187 172 187
No hint
172 171 172 172 172 172 172 172 171 172
所以我想说,任何一方的提示都会产生大致相同的结果,而且总比没有提示要好。选择一个糟糕的提示位置(例如开始)比没有提示更糟糕。
关于c++ - std::map 的插入提示是否有任何位置限制?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4342204/
我正在开发一个小型图书馆,我需要做的一件事是让访问者访问一些数据并返回结果。 在一些较旧的 C++ 代码中,访问者需要声明一个 typedef return_type .例如,boost::stati
我正在尝试使用std:map类型的键和值制作std::any Visual Studio 2017 std::map m("lastname", "Ivanov"); std::cout (m["la
我已经在 C++ 的 map 中声明了一个集合为 std::map> .如何循环访问或打印设定值? 最佳答案 如果你知道如何迭代 std::map或 std::set单独地,您应该可以毫无问题地组合迭
如何循环? 我已经试过了: //----- code std::vector >::iterator it; for ( it = users.begin(); it != users.end();
我有两个用例。 A.我想同步访问两个线程的队列。 B.我想同步两个线程对队列的访问并使用条件变量,因为其中一个线程将等待另一个线程将内容存储到队列中。 对于用例 A,我看到了使用 std::lock_
我正在查看这两种类型特征的文档,但不确定有什么区别。我不是语言律师,但据我所知,它们都适用于“memcpy-able”类型。 它们可以互换使用吗? 最佳答案 不,这些术语不能互换使用。这两个术语都表示
我有以下测试代码,其中有一个参数 fS,它是 ofstream 的容器: #include #include #include #include int
这是这个问题的延续 c++ function ptr in unorderer_map, compile time error 我试图使用 std::function 而不是函数指针,并且只有当函数是
std::unordered_map str_bool_map = { {"a", true}, {"b", false}, {"c", true} }; 我们可以在此映射上使
我有以下对象 std::vector> vectorList; 然后我添加到这个使用 std::vector vec_tmp; vec_tmp.push_back(strDRG); vec_tmp.p
为什么 std::initializer_list不支持std::get<> , std::tuple_size和 std::tuple_element ?在constexpr中用得很多现在的表达式,
我有一个像这样定义的变量 auto drum = std::make_tuple ( std::make_tuple ( 0.3f , Ex
假设我有一个私有(private)std::map在我的类(class)里std::map 。我怎样才能将其转换为std::map返回给用户?我想要下面的原型(prototype) const std
假设我有一个私有(private)std::map在我的类(class)里std::map 。我怎样才能将其转换为std::map返回给用户?我想要下面的原型(prototype) const std
问题 我正在尝试将 lambda 闭包传递给 std::thread,它使用任意封闭参数调用任意封闭函数。 template std::thread timed_thread(Function&& f
我想创建一个模板类,可以容纳容器和容器的任意组合。例如,std::vector或 std::map ,例如。 我尝试了很多组合,但我必须承认模板的复杂性让我不知所措。我编译的关闭是这样的: templ
我有一个 std::vector>我将其分配给相同类型的第二个 vector 。 我收到这个编译器错误: /opt/gcc-8.2.0/include/c++/8.2.0/bits/stl_algob
有时候,我们有一个工厂可以生成一个 std::unique_ptr vector ,后来我们想在类/线程/你命名的之间共享这些指针。因此,最好改用 std::shared_ptr 。当然有一种方法可以
这个问题在这里已经有了答案: Sorting a vector of custom objects (14 个答案) 关闭 6 年前。 我创建了一个 vector vector ,我想根据我定义的参
我有三个类(class)成员: public: std::vector > getObjects(); std::vector > getObjects() const; privat
我是一名优秀的程序员,十分优秀!