I had a vague feeling that std::deque is a "heavy" thing which you shouldn't have a million of, but iterating through a couple big ones is pretty fast. 1–4K batches wouldn't hurt my feelings. Looked up GCC, it's actually slightly less heavy at 512 bytes per node[1]. But the MSVC part — that caught me completely off guard.
https://github.com/gcc-mirror/gcc/blob/47749c43acb460ac8f410...
In general it's better to use the same standard library everywhere - discrepancies like that occur for almost every type so if you care about having the same performance on every platform... Either use libc++ or boost
From memory:
In MSVC, dequeue will allocate memory for every single element if your elements are > 8 bytes. This will never be changed, due to ABI compatibility.
Clang and gcc have batching sizes of 1K and 4K (i.e. you throw out a whole page of memory even if your dequeue contains only 1 element).