std::deque将元素存储在固定大小的“存储桶”（数组）中。不同的编译器使用不同的存储桶大小：
element_size < 256 ? 4096 : element_size * 16对于MSVC（尤其是MSVC）和GCC，如果双端队列元素的大小大于硬编码的大小，std::deque则std::list在大多数情况下会导致性能下降。
我认为Clang的效果更好，无论双端队列元素的大小如何，存储桶至少应包含16个元素。尽管在某些情况下，对于小元素，最小的bucket大小4096字节可能不是最佳的。
为什么没有std::deque用于存储桶大小的附加模板参数，其默认值是供应商认为合理的值？这不会破坏向后兼容性，但可以优化性能。
正如cplusplus.com上所读,std::queue实现如下:
队列实现为容器适配器,它是使用特定容器类的封装对象作为其底层容器的类,提供一组特定的成员函数来访问其元素.元素被推入特定容器的"后面"并从其"前面"弹出.
底层容器可以是标准容器类模板之一或其他一些专门设计的容器类.该底层容器应至少支持以下操作:
......
标准容器类deque和list满足这些要求.默认情况下,如果没有为特定队列类实例化指定容器类,则使用标准容器双端队列.
我很困惑为什么deque(类固醇上的双端队列)在这里被用作默认值,而不是list(这是一个双向链表).
在我看来,这std::deque是非常矫枉过正:它是一个双端队列,但也有恒定时间元素访问和许多其他功能; 基本上是一个功能齐全的std :: vector bar'元素在内存中连续存储'保证.
正常情况下std::queue只有极少数可能的操作,在我看来,双向链表应该更有效率,因为需要在内部发生的管道要少得多.
为什么然后std::queue使用std::deque默认值而不是std::list？
如果我有std::deque并且std::vector想要将它们组合到std::deque，我可以通过以下方式进行：
typedef int T; // type int will serve just for illustration
std::deque< T > deq(100); // just some random size here
std::vector< T > vec(50);
// ... doing some filling ...
// now moving vector to the end of queue:
deq.insert(
deq.end(),
std::make_move_iterator( vec.begin() ),
std::make_move_iterator( vec.end() )
);
std::cout << deq.size() << std::endl;
我们知道向量的大小，但我们不能在最后std::deque使用之前保留内存std::deque.insert(...)。那么这是将所有元素移动std::vector到末尾的最快方法std::deque吗？还是我错过了什么？
谢谢你。
来自emplace_back()以下文档的摘录:
- 迭代器有效性
与此容器相关的所有迭代器都是无效的,但指针和引用仍然有效,指的是它们在调用之前引用的相同元素.
- 数据竞赛
容器已修改.
调用不访问任何包含的元素:同时访问或修改它们是安全的(尽管请参见上面的迭代器有效性).
以及以下文档的摘录operator[]():
- 数据竞赛
访问容器(const和非const版本都不会修改容器).
可能会访问或修改元素n.同时访问或修改其他元素是安全的.
因此,鉴于deque的某个实例至少有一个元素,通过访问它operator[]()并同时调用emplace_back()容器确实是线程安全的？
我倾向于说它是,但不能决定"访问" emplace_back()的文档是否包括使用operator[]()如下:
int access( std::deque< int > & q )
{
return q[ 0 ];
}
void emplace( std::deque< int > & q , int i )
{
q.emplace_back( i );
}
其中两个函数同时调用,或者"访问"仅适用于已经采用某些引用或指针的元素:
std::deque< int > q { 1 };
auto * ptr = & q[ 0 ]
std::thread t1 ( [ …我在这里得到一个编译错误,我不知道代码有什么问题.我正在使用g ++ 4.9.2.
#include<iostream>
#include<deque>
using std::string;
using std::deque;
class Dummy {
public:
virtual ~Dummy(){};
Dummy():ID_("00") {};
private:
const string ID_;
};
int main(){
{
deque <Dummy> waiter;
waiter.push_back(Dummy());
waiter.erase( waiter.begin() );
}
return 0;
}
编辑:我知道删除const会删除编译错误,但我不知道为什么.无论如何,我需要这个const.
这是我在 HackerRank 上研究这个问题的解决方案时遇到的一个问题。它基本上归结为以下内容：给定一个数组 A 和一个整数 K，问题要求您找到大小为 K 的 A 的每个连续子数组的最大值。还有一些额外的东西（对于每个测试用例，这个问题都会发生 T次，并且必须从输入中读取才能获得 A)，但这就是它的要点。
该站点会检查您的答案是否足够有效，即使您的代码最终产生了正确的输出，也可能会因超时而导致提交失败。现在，当您第一次进入代码区域时，有一些预定义的代码供您使用：
#include <iostream>
#include <deque>
using namespace std;
void printKMax(int arr[], int n, int k){
//Write your code here.
}
int main(){
int t;
cin >> t;
while(t>0) {
int n,k;
cin >> n >> k;
int i;
int arr[n];
for(i=0;i<n;i++)
cin >> arr[i];
printKMax(arr, n, k);
t--;
}
return 0;
}
一切都很好，该站点已经为您的利益处理输入，并为您指明模块化方法。你所要做的就是解决连续子数组问题；我使用以下函数完成了它，该函数通过了所有测试用例：
void printKMax(int arr[], int n, int k){
// Queue will store …我为什么要使用a std::stack或a std::queue而不是a std::vector或a std::deque？
由于容器适配器只是标准容器周围的包装器,为什么要使用它们呢？
我正在实现的算法具有以下结构：
while C is not empty
select a random entry e from C
if some condition on e
append some new entries to C (I don't care where)
else
remove e from C
重要的是循环 e 的每次迭代都是随机选择的（具有统一的概率）。
理想情况下select，append和remove步骤都是 O(1)。
如果正确地明白，使用std::list的append和remove步骤将是O（1），但随机选择将是O（N）（例如，使用std::advance如在此解决方案）。
And std::deque and std::vector seem to have complementary O(1) and O(n) operations.
I'm guessing that std::set will introduce some O(log n) complexity.
Is there any …
以下是导致问题的原因的示例：
#include <deque>
int main() {
std::deque<int> has_data = {1, 2, 3};
std::deque<int>::iterator iter1 = has_data.begin() + 5; // This works fine
std::deque<int> had_data = {4, 5, 6};
had_data.clear();
std::deque<int>::iterator iter2 = had_data.begin() + 5; // This also works fine
std::deque<int> is_empty;
std::deque<int>::iterator iter3 = is_empty.begin() + 5; // This causes a segfault
}
如果双端队列之前从未包含任何元素，则添加到空双端队列的迭代器似乎只是一个问题。
我很好奇这是否是 STL 中的错误，或者我是否只是以导致未定义行为的方式使用它。我只在使用 Xcode（GUI 和命令行）编译时遇到这个问题。我也在 Linux 上使用 GCC 6.2.0 版尝试过它，但那里似乎不存在问题。