deque

an example:


inline void test_deque()
{
std::deque<int> Q;
Q.push_back(3);
Q.push_front(1);
std::copy(Q.begin(),Q.end(),std::ostream_iterator<int>(std::cout," "));
std::cout<<std::endl;
for(std::deque<int>::iterator iter=Q.begin();iter<Q.end();iter++)
std::cout<<*iter<<" ";

}

continuous memory
const time to insert at front and the end.


inline void test_list()
{
std::list<int> L;
L.push_back(0);
L.push_front(1);
L.insert(++L.begin(),2);

std::copy(L.begin(),L.end(),std::ostream_iterator<int>(std::cout," "));
}


insert takes constant time but need to provide the iterator first.