I´d like to add that deque has a larger overhead than vector, this can be a serious problem if you need to store huge amounts of data, especially with small data types. At least STLport and Dinkumware use small block sizes (2-8 Elements, depending on the data type´s size) and, IIRC, 3 pointers, which can sum up in enormous RAM consumption.