The JavaScript STL (Standard Template Library). Part 2

The deque is almost identical to the vector but with the added advantage of being able to add and remove elements from the front end efficiently.

In the code, it "inherits" most of its behaviour from the vector code by redirecting its prototype and then attaching its two extra methods in the constructor:

The push_front() and pop_front() look very similar to the push_back() and pop_back() methods except that they modify the array's start point.

Demo

Choose either the list, vector or deque demo

List Demo

In this demo, you can compile a sequence of items by inserting new items at the start, end or current iterator position. The iterator can be adjusted using the Advance and Retreat buttons. Use the assign button to modify the value at the current iterator position.

Deque Demo

This demo is similar to the vector demo with the added advantage of prepending items at the start.

Vector Demo

This demo shows the advantage of using vectors over lists. Items are only added and removed at the end of the vector however any item in the vector can be accessed by position.

Download the code

This textbox contains the complete source for the two collections (list and vector) discussed in this article. Copy this code into a file called �JSstl.js� to use with the demo.

//<script type="text/javascript">
// JSStl.js
// Source code for std namespace including list and vector collections

// Simulation of the std namespace
function STD()
{
	// do nothing.
}

// create a new list
STD.prototype.list = function()
{
	return new STDList();
}

// create a new vector
STD.prototype.vector = function()
{
	return new STDVector();
}

STD.prototype.deque = function()
{
	return new STDDeque();
}

// standard equal to functor
STD.prototype.equal_to = 
{
	fn:function(a,b)
	{
		return a == b;
	} 
};

// standard greater than functor
STD.prototype.greater = 
{
	fn:function(a,b)
	{
		return a > b;
	} 
};

// standard greater than or equal to functor
STD.prototype.greater_equal = 
{
	fn:function(a,b)
	{
		return a >= b;
	} 
};

// standard less than functor
STD.prototype.less = 
{
	fn:function(a,b)
	{
		return a < b;
	} 
};

// standard less than or equal to functor
STD.prototype.less_equal = 
{
	fn:function(a,b)
	{
		return a <= b;
	} 
};

// create a reference object referencing a value
STD.prototype.ref = function(v)
{
	return {value:v};
}
// create a functor to operate on references
STD.prototype.deRef = function(ftor)
{
	return { functor:ftor,	fn:function(a,b) { return this.functor(a.value,b.value); } };
}

// useful function to test whether an object is an iterator
STD.prototype.isIterator = function(it,bMyType,bMine)
{
	// test whether it is an iterator, 
	// options: if it is also a list type, if it is for this list
	if ( !it ) return false;
	
	// assumes all iterators have the following property
	if ( !it.isIterator ) return false;
	
	// also that to be the same type, it has a type property
	if ( bMyType && (it.type != this.type) ) return false;
	
	// and to be contained in this, it has a container property
	if ( bMine && (it.container !== this) ) return false;
	
	return true;
}

// create the "std" namespace object
var std = new STD();


//=============================================================================
// STDLinkIterator
// An iterator for linked nodes
function STDLinkIterator(container,node,bForward,type)
{
	this.container = container;
	this.node = node;
	this.bForward = bForward;
	this.type = type;
	
	this.item = node.item;
}
STDLinkIterator.prototype.clone = function()
{
	return new STDLinkIterator(this.container,this.node,this.bForward,this.type);
}
STDLinkIterator.prototype.isIterator = true;
STDLinkIterator.prototype.incImpl = function(pos, nIncrement, bF)
{
	if ( bF ) while ( nIncrement-- && pos.next ) pos = pos.next;
	else while ( nIncrement-- && pos.prev ) pos = pos.prev;
	return pos;
}
STDLinkIterator.prototype.increment = function(nIncrement)
{
	if ( arguments.length == 0 ) nIncrement = 1;
	this.node = this.incImpl(this.node, nIncrement, this.bForward);
	this.item = this.node.item;
}
STDLinkIterator.prototype.decrement = function(nDecrement)
{
	if ( arguments.length == 0 ) nDecrement = 1;
	this.node = this.incImpl(this.node, nDecrement, !this.bForward);
	this.item = this.node.item;
}
STDLinkIterator.prototype.minus = function(other)
{
	var n = 0;
	var pos = other.node;
	while ( (pos !== this.node) && !pos.bSentinel )
	{
		n++;
		pos = this.incImpl(pos, 1, this.bForward);
	}
	return n;
}
STDLinkIterator.prototype.equal_to = function(other)
{
	return (this.node === other.node);
}
STDLinkIterator.prototype.insert = function(value)
{
	var it = this.container.insert(this,value);
	this.node = it.node;
	this.item = it.item;
}


//=============================================================================
// STDList
// - an ordered container
// - reversible
function STDList()
{
	this.head = {item:"head",prev:null,bSentinel:true};
	this.tail = {item:"tail",tail:null,bSentinel:true};
	this.clear();
}
STDList.prototype.type = "list";
STDList.prototype.createNode = function(item)
{
	// create a leaf node containing the item
	return {item:item,prev:null,next:null};
}
STDList.prototype.insertNode = function(node,prev,next)
{
	// insert a node between prev and next nodes
	prev.next = node;
	node.prev = prev;
	next.prev = node;
	node.next = next;
	this.nSize++;
}
STDList.prototype.removeNode = function(node)
{
	// remove a node from its current position
	node.prev.next = node.next;
	node.next.prev = node.prev;
	this.nSize--;
}
STDList.prototype.iterator = function(node,bForward)
{
	if ( arguments.length == 1 ) bForward = true;
	return new STDLinkIterator(this,node,bForward,this.type);
}
STDList.prototype.isIterator = STD.prototype.isIterator;
STDList.prototype.assign = function(a,b)
{
	// replace list contents with inputs
	this.clear();
	
	var i = this.head;
	var node;
	if ( this.isIterator(a) && this.isIterator(b) )
	{
		// insert range [a,b)
		while ( !a.equal_to(b) )
		{
			node = this.createNode(a.item);
			i.next = node;
			node.prev = i;
			i = node;	
			this.nSize++;
			a.increment();
		}
	}
	else
	{
		// insert value b, a times
		while ( a > 0 )
		{
			node = this.createNode(b);
			i.next = node;
			node.prev = i;
			i = node;	
			this.nSize++;	
		}
	}
	this.tail.prev = i;
	i.next = this.tail;
}
STDList.prototype.back = function()
{
	// return the last element (or undefined if there isn't one)
	return (this.nSize > 0) ? this.tail.prev.item : undefined;
}
STDList.prototype.begin = function()
{
	// return iterator at start of list
	return this.iterator(this.head.next);
}
STDList.prototype.clear = function()
{
	// remove all elements from list
	this.head.next = this.tail;
	this.tail.prev = this.head;
	this.nSize = 0;
}
STDList.prototype.empty = function()
{
	return this.nSize == 0;
}
STDList.prototype.end = function()
{
	return this.iterator(this.tail);
}
STDList.prototype.erase = function(begin,end)
{
	var a,b;
	a = begin.node;
	if ( this.isIterator(end) ) b = end.node;
	else b = a.next;

	var prev = a.prev;
	while ( a !== b )
	{
		this.nSize--;
		a = a.next;
	}
	prev.next = b;
	b.prev = prev;
}
STDList.prototype.front = function()
{
	// return value at start of list (or undefined if there isn't one)
	return (this.nSize > 0) ? this.head.next.item : undefined;
}
STDList.prototype.insert = function(where,a,b)
{
	var next = where.node;
	var prev = next.prev;
	// insert an item or items into the list
	if ( arguments.length == 2 )
	{
		node = this.createNode(a);
		this.insertNode(node,where.node.prev,where.node);
	}
	else
	{
		if ( this.isIterator(a) && this.isIterator(b) )
		{
			while ( !a.equal_to(b) )
			{
				node = this.createNode(a.item);
				this.insertNode(node,prev,null);
				a.increment();
			}
		}
		else
		{
			while ( a > 0 )
			{
				node = this.createNode(b);
				this.insertNode(node,prev,null);
				a--;
			}
		}
		next.prev = prev;
		prev.next = next;
	}
}
STDList.prototype.merge = function(right,less)
{
	// merge items from another list
	// both lists must already be ordered by less
	this.mergeItems(this.head,this.tail,
					this.head.next,this.tail,false,
					right.head.next,right.tail,true,
					less ? less : STD.prototype.less);
	
}
STDList.prototype.pop_back = function()
{
	// removes last element from list
	this.removeNode(this.tail.prev);
}
STDList.prototype.pop_front = function()
{
	// removes first element from list
	this.removeNode(this.head.next);
}
STDList.prototype.push_back = function(value)
{
	// add item to end of list
	var node = this.createNode(value);
	this.insertNode(node,this.tail.prev,this.tail);
}
STDList.prototype.push_front = function(value)
{
	// add item to front of list
	var node = this.createNode(value);
	this.insertNode(node,this.head,this.head.next);
}
STDList.prototype.rbegin = function()
{
	// return reverse iterator at end of list
	return this.iterator(this.tail.prev,false);
}
STDList.prototype.remove = function(value)
{
	// remove all elements that match a value
	var next;
	for ( var i = this.head.next; i != this.tail; i = next )
	{
		next = i.next;
		if ( this.equal_to.fn(i.item,value) ) this.removeNode(i);
	}
}
STDList.prototype.remove_if = function(pred)
{
	// remove all elements for which pred.fn(value) is true
	var next;
	for ( var i = this.head.next; i != this.tail; i = next )
	{
		next = i.next;
		if ( pred.fn(i.item,value) ) this.removeNode(i);
	}	
}
STDList.prototype.rend = function()
{
	// return reverse iterator at head of list
	return this.iterator(this.head,false);
}
STDList.prototype.resize = function(nSize, value)
{
	while ( nSize < this.nSize ) this.pop_back();
	while ( nSize > this.nSize ) this.push_back(value);
}
STDList.prototype.reverse = function()
{
	// swap items around
	var n = Math.floor(this.nSize / 2);
	var h = this.head.next;
	var t = this.tail.prev;
	while ( n > 0 )
	{
		var tmp = h.item;
		h.item = t.item;
		t.item = tmp;
		n--;
	}
}
STDList.prototype.size = function()
{
	return this.nSize;
}
STDList.prototype.mergeItems = function(wBefore,wAfter,aBegin,aEnd,bCountA,bBegin,bEnd,bCountB,less)
{
	var i = wBefore;
	var a = aBegin;
	var b = bBegin;
	while ( (a !== aEnd) || (b !== bEnd) )
	{	
		var bA;
		if ( a === aEnd ) bA = false;
		else if ( b === bEnd ) bA = true;
		else bA = less.fn(a,b);

		if ( bA )
		{
			i.next = a;
			a.prev = i;
			i = a;
			a = a.next;
			if ( bCountA ) this.nSize++;
		}
		else 
		{
			i.next = b;
			b.prev = i;
			i = b;
			b = b.next;
			if ( bCountB ) this.nSize++;
		}
	}
	i.next = wAfter;
	wAfter.prev = i;
}
STDList.prototype.mergeSort = function(begin,end,nCount,less)
{
	// nothing to do if zero or one items
	if ( nCount < 2 ) return;
	
	// if just two items, swap them
	if ( nCount == 2 )
	{
		var other = begin.next;
		if ( less.fn(other, begin) )
		{
			var temp = begin.item;
			begin.item = other.item;
			other.item = temp;
		}
		return;
	}
	
	// else find the mid point and recurse
	var nHalf = Math.floor(nCount/2);
	var mid = begin;
	for ( var i = 0; i < nHalf; i++ ) mid = mid.next;
	this.mergeSort(begin,mid,nHalf,less);
	this.mergeSort(mid,end,nCount-nHalf,less);
	
	// now merge the two
	this.mergeItems(begin.prev,end,begin,mid,false,mid,end,false,less);
}
STDList.prototype.sort = function(less)
{
	this.mergeSort(this.head.next,this.tail,this.nSize,less?less:STD.prototype.less);
}
STDList.prototype.splice = function(where,right,begin,end)
{
	switch ( arguments.length )
	{
	case 2:
		begin = right.begin();
		end = right.end();
		break;
	case 3:
		end = right.end();
		break;
	case 4:
		break;
	}
	var lBegin = begin.node;
	var lEnd = end.node;
	var lPrev = lBegin.prev;
	
	var wNext = where.node;
	var wPrev = wNext.prev;
	while ( lBegin !== lEnd )
	{
		var node = lBegin;
		lBegin = lBegin.next;
		this.insertNode(node,wPrev);
		wPrev = node;
		right.nSize--;
	}
	wNext.prev = wPrev;
	pPrev.next = wNext;

	lPrev.next = lEnd;
	lEnd.prev = lPrev;
}
STDList.prototype.swap = function(right)
{
	// swap contents with right
	var head = this.head;
	var tail = this.tail;
	var nSize = this.nSize;
	this.head = right.head;
	this.tail = right.tail;
	this.nSize = right.nSize;
	right.head = head;
	right.tail = tail;
	right.nSize = nSize;
}
STDList.prototype.unique = function(equal_to)
{
	if ( equal_to == undefined ) equal_to = STD.prototype.equal_to;
	// remove adjacent duplicate items
	for ( var i = this.head.next; i !== this.tail; i = i.next )
	{
		var iNext = i.next;
		while ( (iNext!==this.tail) && equal_to.fn(i.item,iNext.item) )
		{
			iNext = iNext.next;
			i.next = iNext;
			iNext.prev = i;
		}
	}
}
//=============================================================================
// STDVectorIterator
function STDVectorIterator(container, nIndex, bForward, type)
{
	this.container = container;
	this.data = container.data;
	this.bForward = bForward;
	this.type = type;

	this.setPos(nIndex);	
}
STDVectorIterator.prototype.clone = function()
{
	return new STDVectorIterator(this.container,this.getPos(),this.bForward,this.type);
}
STDVectorIterator.prototype.setPos = function(nIndex)
{
	delete this.item;
	this.nIndex = nIndex;
	if ( this.nIndex >= this.container.nEnd ) return;
	if ( this.nIndex < this.container.nBegin ) return;
	this.item = this.data[nIndex];
}
STDVectorIterator.prototype.getPos = function()
{
	return this.nIndex = Math.min(
		Math.max(this.nIndex,this.container.nBegin-1),
		this.container.nEnd);
}
STDVectorIterator.prototype.increment = function(value)
{
	if ( arguments.length == 0 ) value = 1;
	this.setPos(this.nIndex + (this.bForward ? value : -value));
}
STDVectorIterator.prototype.decrement = function(value)
{
	if ( arguments.length == 0 ) value = 1;
	this.setPos(this.nIndex + this.bForward ? -value : value);
}
STDVectorIterator.prototype.equal_to = function(it)
{
	return (this.container === it.container) &&
			(this.getPos() == it.getPos());
}
STDVectorIterator.prototype.isIterator = true;
STDVectorIterator.assign = function(value)
{
	if ( (this.nIndex < this.container.nEnd) &&
		 (this.nIndex >= this.container.nBegin) ) this.data[this.nIndex] = value;
}
STDVectorIterator.prototype.minus = function(other)
{
	return this.getPos() - other.getPos();
}
STDLinkIterator.prototype.insert = function(value)
{
	this.container.insert(this,value);
}

//=============================================================================
// STDVector
function STDVector()
{
	this.data = new Array();
	this.nBegin = 0;
	this.nEnd = 0;
	this.type = "vector";
}
STDVector.prototype.iterator = function(nPos,bForward)
{
	bForward = arguments.length == 1 ? true : bForward;
	return new STDVectorIterator(this,nPos,bForward,this.type);
}
STDVector.prototype.isIterator = STD.prototype.isIterator;
STDVector.prototype.assign = function(a,b)
{
	// replace list contents with inputs
	if ( this.isIterator(a) && this.isIterator(b) )
	{
		this.clear();
		while ( !a.equal_to(b) )
		{
			this.data.push(a.item);
			a.increment();
			this.nEnd++;
		}
	}
	else
	{
		this.data = new Array(a);
		this.nBegin = 0;
		this.nEnd = a;
		for ( var i = 0; i < a; i++ ) this.data[i] = b;
	}
}
STDVector.prototype.at = function(pos)
{
	return this.data[pos+this.nBegin];
}
STDVector.prototype.back = function()
{
	return this.data[this.nEnd-1];
}
STDVector.prototype.begin = function()
{
	return this.iterator(this.nBegin);
}
STDVector.prototype.capacity = function()
{
	return this.data.length;
}
STDVector.prototype.clear = function()
{
	this.data = new Array();
	this.nBegin = 0;
	this.nEnd = 0;
}
STDVector.prototype.empty = function()
{
	return this.data.length == 0;
}
STDVector.prototype.end = function()
{
	return this.iterator(this.nEnd);
}
STDVector.prototype.erase = function(first, last)
{
	var nFirst = first.getPos();
	if ( nFirst == this.nEnd ) return;
	var nLast;
	if ( arguments.length == 1 ) nLast = nFirst + 1;
	else nLast = last.getPos();
	
	var nCount = nLast - nFirst;
	this.data.splice(nFirst, nCount);
	this.nEnd -= nCount;
}
STDVector.prototype.front = function()
{
	return this.data[this.nBegin];
}
STDVector.prototype.insert = function(where,a,b)
{
	var nWhere = where.getPos();
	if ( arguments.length == 2 )
	{
		this.data.splice(nWhere,0,a);
		this.nEnd++;
		where.item = a;
		return where;
	}

	var aTail = this.data.splice(nWhere,this.nEnd-nWhere);	
	if ( this.isIterator(a) && this.isIterator(b) )
	{
		while ( !a.equal_to(b) )
		{
			this.data.push(a);
			this.nEnd++;
		}
	}
	else
	{
		for ( var i = 0; i < a; i++ ) this.data.push(b);
		this.nEnd += a;
	}
	for ( i in aTail ) this.data.push(aTail[i]);
}

STDVector.prototype.pop_back = function()
{
	if ( this.nEnd > this.nBegin ) delete this.data[--this.nEnd];
}
STDVector.prototype.push_back = function(value)
{
	this.data[this.nEnd++] = value;
}
STDVector.prototype.rbegin = function()
{
	return this.iterator(this.nEnd-1, false);
}
STDVector.prototype.rend = function()
{
	return this.iterator(this.nBegin-1,false);
}
STDVector.prototype.size = function()
{
	return this.nEnd - this.nBegin;
}
STDVector.prototype.swap = function(right)
{
	var data = this.data;
	var nBegin = this.nBegin;
	var nEnd = this.nEnd;
	
	this.data = right.data;
	this.nBegin = right.nBegin;
	this.nEnd = right.nEnd;
	
	right.data = data;
	right.nBegin = nBegin;
	right.nEnd = nEnd;
}

//=============================================================================
// STDDeque
function STDDeque()
{
	this.data = new Array();
	this.nBegin = 0;
	this.nEnd = 0;
	
	this.type = "deque";
	
	// add a few specialisations...
	this.push_front = STDDeque_push_front;
	this.pop_front = STDDeque_pop_front;
}

// inherit methods from STDVector
STDDeque.prototype = STDVector.prototype;

STDDeque_push_front = function(value)
{
	this.data[--this.nBegin] = value;
}
STDDeque_pop_front = function()
{
	if ( this.nEnd > this.nBegin ) delete this.data[this.nBegin++];
}

//</script>

This textbox contains a short demonstration of how lists and vectors may be used on a web page.

<html>
<head>
<script type="text/javascript" src="JSstl.js"></script>
<script type="text/javascript">
function modifyDemo(demo, position, visibility)
{
	var oDiv = document.getElementById(demo + 'Demo');
	oDiv.style.position = position;
	oDiv.style.visibility = visibility;
}
function showDemo(demo)
{
	modifyDemo('blank','absolute','hidden');
	modifyDemo('list','absolute','hidden');
	modifyDemo('deque','absolute','hidden');
	modifyDemo('vector','absolute','hidden');

	modifyDemo(demo,'static','visible');
}

var listAgent = null;
var oListInput = null;
function showList()
{
	if ( !listAgent )
	{
		listAgent = new ListAgent(document.getElementById('listBox'));
		oListInput = document.getElementById('listInput');
	}
	showDemo('list');
}

var dequeAgent = null;
var oDequeInput = null;
var oDequePos = null;
function showDeque()
{
	if ( !dequeAgent )
	{
		dequeAgent = new VectorAgent(document.getElementById('dequeBox'), std.deque());
		oDequeInput = document.getElementById('dequeInput');
		oDequePos = document.getElementById('dequePos');
	}
	showDemo('deque');
}

var vectorAgent = null;
var oVectorInput = null;
var oVectorPos = null;
function showVector()
{
	if ( !vectorAgent )
	{
		vectorAgent = new VectorAgent(document.getElementById('vectorBox'),std.vector());
		oVectorInput = document.getElementById('vectorInput');
		oVectorPos = document.getElementById('vectorPos');
	}
	showDemo('vector');
}

//=========================================================
// list code
function ListAgent(theListBox)
{
	this.container = std.list();
	
	// cache a const version of end()
	this.container.oEnd = this.container.end();
	
	this.it = null;
	this.box = theListBox;
	this.boxBorder = "1px solid red";
	this.boxHighlight = "yellow";
}
ListAgent.prototype.selectDiv = function(bSelect)
{
	if ( !this.it ) this.it = this.container.begin();
	if ( !this.it.equal_to(this.container.oEnd) ) this.it.item.style.background = bSelect ? this.boxHighlight : "";
}
ListAgent.prototype.createDiv = function(value)
{
	var oDiv = document.createElement('span');
	oDiv.innerHTML = value;
	oDiv.style.border = this.boxBorder;
	return oDiv;
}
ListAgent.prototype.increment = function()
{
	if ( this.it )
	{
		this.selectDiv(false);
		this.it.increment();
	}
	this.selectDiv(true);
}
ListAgent.prototype.decrement = function()
{
	if ( this.it ) this.selectDiv(false);
	else this.it = theList.end();
	this.it.decrement();
	this.selectDiv(true);
}
ListAgent.prototype.snapshot = function()
{
	if ( !this.it ) this.it = this.container.begin();
	return this.it.clone();
}
ListAgent.prototype.insert = function(value)
{
	this.selectDiv(true);
	var oDiv = this.createDiv(value);

	if ( this.box.children.length == 0 ) this.box.appendChild(oDiv);
	else this.box.insertBefore(oDiv,this.it.item);
	this.container.insert(this.it,oDiv);
}
ListAgent.prototype.remove = function()
{
	if ( !this.it ) return;
	if ( this.container.size() == 0 ) return;
	this.selectDiv(false);
	var it = this.it.clone();
	if ( this.container.size() > 1 )
	{
		if ( this.it.item === this.container.back() ) this.it.decrement();
		else this.it.increment();
		this.selectDiv(true);
	}
	else this.it = null;
	this.box.removeChild(it.item);
	this.container.erase(it);
}
ListAgent.prototype.push_back = function(value)
{
	var oDiv = this.createDiv(value);
	this.box.appendChild(oDiv);
	this.container.push_back(oDiv);
}
ListAgent.prototype.push_front = function(value)
{
	var oDiv = this.createDiv(value);
	if ( this.box.children.length == 0 ) this.box.appendChild(oDiv);
	else this.box.insertBefore(oDiv,this.container.front());
	this.container.push_front(oDiv);
}
ListAgent.prototype.pop_back = function()
{
	if ( this.container.size() == 0 ) return;
	if ( (this.it != null) && (this.it.item === this.container.back()) )
	{
		if ( this.container.size() > 1 ) this.decrement();
		else this.it = null;
	}
	this.box.removeChild(this.container.back());
	this.container.pop_back();
}
ListAgent.prototype.pop_front = function()
{
	if ( this.container.size() == 0 ) return;
	if ( this.it && (this.it.item === this.container.front()) )
	{
		if ( this.container.size() > 1 ) this.increment(); 
		else this.it = null;
	}
	this.box.removeChild(this.container.front());
	this.container.pop_front();
}
ListAgent.prototype.assign = function(value)
{
	if ( this.it ) this.it.item.innerHTML = value;
}

//=========================================================
// vector code
function VectorAgent(theVectorBox, container)
{
	this.container = container;
	this.box = theVectorBox;
	this.boxBorder = "1px solid green";
	this.boxHighlight = "teal";
}
VectorAgent.prototype.createDiv = ListAgent.prototype.createDiv;
VectorAgent.prototype.push_back = ListAgent.prototype.push_back;
VectorAgent.prototype.pop_back = ListAgent.prototype.pop_back;
VectorAgent.prototype.push_front = ListAgent.prototype.push_front;
VectorAgent.prototype.pop_front = ListAgent.prototype.pop_front;
VectorAgent.prototype.insert = function(index,value)
{
	var oDiv = this.createDiv(value);

	var it = this.container.begin();
	it.increment(index);

	if ( it.item ) this.box.insertBefore(oDiv, it.item);
	else this.box.appendChild(oDiv);

	this.container.insert(it, oDiv);
}
VectorAgent.prototype.assign = function(index,value)
{
	this.container.at(index).innerHTML = value;
}
</script>
</head>
<body>
<button onclick="showList();">List Demo</button>
<button onclick="showVector();">Vector Demo</button>
<button onclick="showDeque();">Deque Demo</button>
<div>
	<div id="blankDemo">Choose a demo</div>
	<div id="listDemo" style="position:absolute;visibility:hidden">
		<h3>List Demo</h3>
		<div id=listBox></div>
		<input type=text id=listInput value="type a value here" onfocus="this.value='';" onkeypress="if ( event.keyCode == 13 ) { if ( event.shiftKey ) listAgent.push_front(this.value); else listAgent.push_back(this.value); this.value = ''; }"><br>
		<button onclick="listAgent.push_front(oListInput.value);" ID="Button1">Push Front</button>
		<button onclick="listAgent.push_back(oListInput.value);" ID="Button2">Push Back</button>
		<button onclick="listAgent.pop_front();oListInput.focus();">Pop Front</button>
		<button onclick="listAgent.pop_back();">Pop Back</button>
		<button onclick="listAgent.insert(oListInput.value);">Insert</button>
		<button onclick="listAgent.remove();">Remove</button>
		<button onclick="listAgent.increment();">Advance</button>
		<button onclick="listAgent.decrement();">Retreat</button>
		<button onclick="listAgent.assign(oListInput.value);">Assign</button>
		
	</div>
	<div id="dequeDemo" style="position:absolute;visibility:hidden">
		<h3>Deque Demo</h3>
		<div id="dequeBox"></div>
		<input type=text id="dequeInput" value="type a value here" onfocus="this.value='';" onkeypress="if ( event.keyCode == 13 ) { if ( event.shiftKey ) dequeAgent.push_front(this.value); else dequeAgent.push_back(this.value); this.value = ''; }">
		<input type=text id="dequePos" value="enter a position here" onfocus="this.value='';"><br>
		<button onclick="dequeAgent.push_front(oDequeInput.value);">Push front</button>
		<button onclick="dequeAgent.pop_front();">Pop Front</button>
		<button onclick="dequeAgent.push_back(oDequeInput.value);">Push Back</button>
		<button onclick="dequeAgent.pop_back();">Pop Back</button>
		<button onclick="dequeAgent.assign(parseInt(oDequePos.value),oDequeInput.value);">Assign</button>
		<button onclick="dequeAgent.insert(parseInt(oDequePos.value),oDequeInput.value);">Insert</button>
	</div>
	<div id="vectorDemo" style="position:absolute;visibility:hidden">
		<h3>Vector Demo</h3>
		<div id="vectorBox"></div>
		<input type=text id="vectorInput" value="type a value here" onfocus="this.value='';" onkeypress="if ( event.keyCode == 13 ) { vectorAgent.push_back(this.value); this.value=''; }">
		<input type=text id="vectorPos" value="enter a position here" onfocus="this.value='';"><br>
		<button onclick="vectorAgent.push_back(oVectorInput.value);">Push Back</button>
		<button onclick="vectorAgent.pop_back();">Pop Back</button>
		<button onclick="vectorAgent.assign(parseInt(oVectorPos.value),oVectorInput.value);">Assign</button>
	</div>
</div>
</body>
</html>

Conclusion

In this article I've introduced a JavaScript implementation of the C++ Standard Template Library. This library offers a consistent interface with well defined behaviours. The JavaScript STL will never compete in performance with either the C++ version or the native JavaScript collections such as the Array or Object. It is implemented in script but it does offer flexibility and standardization that are not always seen in JavaScript.

In the next issue I will introduce more collections from the STL repertoire and delve deeper into how iterators can do more than just iterate.

Disclaimer

While I have endeavored to make this code as browser compatible as possible, I have only tested it with Internet Explorer (6.0) and Netscape (7.1) as this represents of a large proportion of users.

About the Author

Guyon Roche is a freelance web developer in London, Great Britain. He specializes in Windows platforms with an interest in bridging the gaps between different technologies, visit http://www.silver-daggers.co.uk for more details. He can be reached via e-mail at guyon.roche@btinternet.com.