STL Containers: Vector, List, and Dequeue

Dr. Lawlor, CS 202, CS, UAF

We've seen std::vector, implemented as an array internally, which lets you efficiently access random elements, but you can only efficiently insert data at the end (push_back).

We've seen std::list, implemented as a linked list internally, which lets you efficiently insert random elements (including push_front and push_back), but you can only efficiently access the front and back element, not a random element in the middle.

There's another interesting STL container called a "deque" (pronounced "deck", also called a "FIFO") that gives you the ability to efficiently access any element, and to insert or delete elements at the beginning or end efficiently.

The typical implementation of a deque uses an ordinary array, but you keep *two* pointers into the array for the start and end of the deque. To add stuff to the end, you just move the end pointer down like an ordinary array. To add stuff to the beginning, you move the start pointer *back* up the array. If you run out of space at either end, you can just reallocate, or you can actually *wrap around* to the other unused end of the array! (See Gaddis textbook, or attend the lecture for details.)

Here's an example of the syntax. Note I can push back or front, *and* still use the index operator:

#include <deque>

int foo(void) {
	std::deque<std::string> d;
	d.push_back("a"); d.push_back("b"); d.push_front("c");
	for (unsigned int i=0;i<d.size();i++) {
		cout<<" deque contents: "<<d[i]<<"\n";
	}
	return 0;
}

(Try this in NetRun now!)

You can also use an iterator to walk through the contents of the deque, just like a list or vector:

#include <deque>

int foo(void) {
	std::deque<std::string> d;
	d.push_back("a"); d.push_back("b"); d.push_front("c");
	for (std::deque<std::string>::iterator it=d.begin();it!=d.end();++it) {
		cout<<" deque contents: "<<(*it)<<"\n";
	}
	return 0;
}

(Try this in NetRun now!)

You can even write your *own* deque implementation, such as this one:

template <class T>
class mydeque {
public:
	int n;
	T *storage; // dynamically allocated array of n elements
	int s,e; // pointers to first and last+1 elements
	mydeque() {
		n=2;
		storage=new T[n];
		s=e=n/2;
	}
	~mydeque() {
		delete[] storage;
	}
	void push_back(const T &add) {
		storage[e]=add;
		e++;
		if (e>=n) { 
			cout<<"mydeque::push_back past end "<<e<<"\n"; //exit(1);
			int nn=2*n+16;
			T *nstorage=new T[nn];
			for (unsigned int i=0;i<size();i++) {
				nstorage[s+i]=storage[s+i];
			}
			delete[] storage; storage=nstorage;
			n=nn;
		}
	}
	void push_front(const T &add) {
		if (s<1) {// need more space at the *START*:
			//cout<<"mydeque::push_front before start "<<s<<"\n"; //exit(1);
			int nn=2*n+16;
			int g=nn-n; // nstorage[g] == storage[0]
			T *nstorage=new T[nn];
			for (unsigned int i=0;i<size();i++) {
				nstorage[g+s+i]=storage[s+i];
			}
			s+=g; e+=g;
			delete[] storage; storage=nstorage;
			n=nn;
		}
		s--;
		storage[s]=add;
	}
	unsigned int size(void) {
		return e-s;
	}
	T &operator[](int i) {
		if (i<0 || i>=(int)size())  {cout<<"mydeque::index bad "<<i<<"\n"; exit(1);}
		return storage[s+i];
	}
private:
	mydeque(const mydeque &d); // don't do that!
	void operator=(const mydeque &d); // don't do that!
};

int foo(void) {
	mydeque<std::string> d;
	d.push_back("a"); d.push_back("b"); d.push_front("c"); d.push_front("d");
	for (unsigned int i=0;i<d.size();i++) {
		long delta=0;
		if (i>0) delta=&d[i]-&d[i-1];
		cout<<" d["<<i<<"]="<<d[i]<<" (at address "<<&d[i]<<")\n";
	}
	return 0;
}

(Try this in NetRun now!)