Visual Studio 中 priority_queue::push() 的时间复杂度？
Time complexity of priority_queue::push() in Visual Studio?
我使用 Windows 和 Visual Studio 2015。据我从参考资料和其他人的问题中可以看出，priority_queue::push() 应该有 O(log(n)) 时间复杂。这当然意味着这个简单的代码：
#include <queue>
using namespace std;
int main()
{
priority_queue<int> q;
const int n=100000; //We can vary this
for (int i = 0; i < n; i++)
{
q.push(i);
}
}
应该有复杂度 O(nlog(n))，这意味着对于上面的 n=100 000 它应该是小菜一碟。我需要几分钟（std::set 只需要一秒钟）。
我已经调试了这段代码并在 10 秒的倍数处停止了它，并绘制了那些时间的 i 的平方。它们非常（！）准确地位于一条线上，这意味着上面的代码具有 O(n^2) 的复杂性。
我的问题是，不是 priority_queue::push() 保证在 O(log(n)) 中 运行 还是我做错了什么？
提前致谢！
编辑： 我试过 this post 中的提示。它没有改善任何事情，所以我想重新分配底层容器不是我的问题。
编辑：已解决 和往常一样，答案非常简单。我在调试模式下 运行 程序，这显然改变了某些功能的复杂性。我不知道这一点，虽然我认为这是很合理的......
n=100000 几分钟似乎很长。
您是否有机会在调试模式下进行测试？
关于复杂度和性能：
Priority queues are a type of container adaptors, specifically
designed such that its first element is always the greatest of the
elements it contains
并且：
By default, if no container class is specified for a particular
priority_queue class instantiation, the standard container vector is
used.
这意味着在 i 递增的循环中，新项目需要插入到向量的开头，这意味着所有其他元素都必须移动一个 - 这对于每次迭代.由于 vector 中的所有元素都是连续存储的（虽然 push_back 实际上用于插入项目，但 push_heap 被调用以重新排列它们）。
翻转（使用默认矢量容器）几乎不需要时间，即使在调试模式下也是如此。
来自 Are std::vector elements guaranteed to be contiguous?:
23.2.6 Class template vector [vector]
1 A vector is a sequence container that supports random access iterators. In addition, it supports (amortized) constant time insert
and erase operations at the end; insert and erase in the middle take
linear time. Storage management is handled automatically, though hints
can be given to improve efficiency. The elements of a vector are
stored contiguously, meaning that if v is a vector where T is some
type other than bool, then it obeys the identity &v[n] == &v[0] + n
for all 0 <= n < v.size().
解决方案可能是指定不同的容器类型：
template <class T, class Container = vector<T>
因此，至于 priority_queue::push() 的 O(log(n)) 的复杂性，很难保证，因为底层容器类型可能不同，并且每个容器都有自己的 [= 实现50=] 项。但是 O(log(n)) 将是最好的情况。
但除了复杂性因素之外，也许更重要的是每个操作所花费的时间。
EDIT (question): I have tried the tip in this post. It didn't improve things, so
I suppose reallocating the underlying container is not my issue.
与其说是重新分配存储元素的内存（vector 无论如何都会以块为单位进行分配——尽管对于较大的容器来说，预分配总是可取的），而是关于在第一个元素之前插入每个元素（如果确实如此）情况，似乎是这样）。即使分配了足够的 space，要在 vector 前面插入一个元素，所有其他元素也需要恰好移动一个 element-size。就是搬家需要时间。
答案是否定的，O(log(n)) 中根本不能保证运行。这种保证是不可能实现的。
我使用 Windows 和 Visual Studio 2015。据我从参考资料和其他人的问题中可以看出，priority_queue::push() 应该有 O(log(n)) 时间复杂。这当然意味着这个简单的代码：
#include <queue>
using namespace std;
int main()
{
priority_queue<int> q;
const int n=100000; //We can vary this
for (int i = 0; i < n; i++)
{
q.push(i);
}
}
应该有复杂度 O(nlog(n))，这意味着对于上面的 n=100 000 它应该是小菜一碟。我需要几分钟（std::set 只需要一秒钟）。
我已经调试了这段代码并在 10 秒的倍数处停止了它，并绘制了那些时间的 i 的平方。它们非常（！）准确地位于一条线上，这意味着上面的代码具有 O(n^2) 的复杂性。
我的问题是，不是 priority_queue::push() 保证在 O(log(n)) 中 运行 还是我做错了什么？
提前致谢！
编辑： 我试过 this post 中的提示。它没有改善任何事情，所以我想重新分配底层容器不是我的问题。
编辑：已解决 和往常一样，答案非常简单。我在调试模式下 运行 程序，这显然改变了某些功能的复杂性。我不知道这一点，虽然我认为这是很合理的......
n=100000 几分钟似乎很长。
您是否有机会在调试模式下进行测试？
关于复杂度和性能：
Priority queues are a type of container adaptors, specifically designed such that its first element is always the greatest of the elements it contains
并且：
By default, if no container class is specified for a particular priority_queue class instantiation, the standard container vector is used.
这意味着在 i 递增的循环中，新项目需要插入到向量的开头，这意味着所有其他元素都必须移动一个 - 这对于每次迭代.由于 vector 中的所有元素都是连续存储的（虽然 push_back 实际上用于插入项目，但 push_heap 被调用以重新排列它们）。
翻转（使用默认矢量容器）几乎不需要时间，即使在调试模式下也是如此。
来自 Are std::vector elements guaranteed to be contiguous?:
23.2.6 Class template vector [vector]
1 A vector is a sequence container that supports random access iterators. In addition, it supports (amortized) constant time insert and erase operations at the end; insert and erase in the middle take linear time. Storage management is handled automatically, though hints can be given to improve efficiency. The elements of a vector are stored contiguously, meaning that if v is a vector where T is some type other than bool, then it obeys the identity &v[n] == &v[0] + n for all 0 <= n < v.size().
解决方案可能是指定不同的容器类型：
template <class T, class Container = vector<T>
因此，至于 priority_queue::push() 的 O(log(n)) 的复杂性，很难保证，因为底层容器类型可能不同，并且每个容器都有自己的 [= 实现50=] 项。但是 O(log(n)) 将是最好的情况。
但除了复杂性因素之外，也许更重要的是每个操作所花费的时间。
EDIT (question): I have tried the tip in this post. It didn't improve things, so I suppose reallocating the underlying container is not my issue.
与其说是重新分配存储元素的内存（vector 无论如何都会以块为单位进行分配——尽管对于较大的容器来说，预分配总是可取的），而是关于在第一个元素之前插入每个元素（如果确实如此）情况，似乎是这样）。即使分配了足够的 space，要在 vector 前面插入一个元素，所有其他元素也需要恰好移动一个 element-size。就是搬家需要时间。
答案是否定的，O(log(n)) 中根本不能保证运行。这种保证是不可能实现的。