You might not want to use deque because of how much memory it can use while still small, e.g. libc++s implementation uses a 4KiB page: http://rextester.com/VIB

You might not want to use deque because of how much memory it can use while still small, e.g. libc++s implementation uses a 4KiB page: http://rextester.com/VIB96468 http://rextester.com/VIB96468 In the GNU stdlibc++ implementation the object itself is pretty large (and they use a page size of 512 bytes): http://rextester.com/RHYKB83240 http://rextester.com/RHYKB83240