The JavaScript STL (Standard Template Library). Part 1
The JavaScript STL (Standard Template Library). Part 1
One of the obstacles that programmers encounter when developing with different programming languages is that each language has its own "culture" and ways of getting things done. Sometimes different instances of the same language can suffer from this malady. This adds a complexity to software development that would be a waste of time if it weren't so necessary.
In the C++ programming language (where I spend the other half of my programming life), a solution to this kind of problem has been developed, standardized and wholeheartedly adopted by developers worldwide. It's called the Standard Template Library or STL for short.
I won't go into too much detail about the specification of the STL as a quick search on the Internet will bring up numerous sites about it. This article is intended to present a JavaScript implementation of the STL and that is what I will focus on.
A bit about the C++ STL
The STL offers a package of useful collections, iterators and algorithms based on a small and consistent set of rules. Different parts of the STL are interchangeable and the interface for each object is consistent, which makes it easy for programmers to switch between different parts or even implementations without having to modify other parts of their code.
An important aspect of the STL is that the runtime behavior
of each collection, iterator and algorithm has also been standardized and documented.
For example: The time to insert a value into a STL map is documented as O(log(N)) which is a favorable
behaviour. Inserting a value into a vector anywhere but at the end is an expensive
operation which takes time O(N); in the worst case
scenario, nearly all of the elements in the vector will need to be shifted.
Translating C++ language features into JavaScript
You might think that porting a C++ library into JavaScript would be next to impossible, but as it turns out, enough of the features that make STL possible in C++ have some equivalent in JavaScript that will suffice. Let's have a look at some of these issues.
How can you have templates in JavaScript?
While C++ and JavaScript share a similar syntax, the languages are very different. C++ is strongly typed, where functions and variables are designed to operate on specific types and nothing else. In contrast, JavaScript is essentially typeless. In JavaScript a variable or function argument can be anything; a number, a string, an object or even a function. Often the kind of value being dealt with in JavaScript needs to be determined at runtime in order to be used properly.
Templates were added in C++ to add a bit of flexibility to the strongly typed nature of the language. It allows code to be written in general terms without specifying directly the types of values being operated on. The following example demonstrates the use of templates to determine the maximum of two inputs:
|
Despite the differences between languages, a number of key features of C++ templates translate quite well into JavaScript. Let's have a look at the max example above:
// JavaScript function max returns the greater of two values
function max(left,right)
{
return left < right ?
right : left;
}
var i = max(-5,7); // i becomes 7
var f = max(5.4,4.5); // f becomes 5.4
var s = max("hello","world"); // s becomes "world"
In the JavaScript version of max, the function evaluates the expression left < right and returns the greater value. The difference here, apart from the syntax, is that with JavaScript the type of comparison between left and right is determined at runtime while C++ (being a compiled language) must determine the type of comparison beforehand.
The use of templates in C++ extends to more than just functions of simple types. Templates may be used to define new classes as well as functions and these may be based on other classes and even combinations of multiple classes and simple types. Take a look at the following definition:
template <class T, int M>
class MyLess
{
public:
bool fn(const T &left,
const T &right)
{
return
(left.getValue() % M) < (right.getValue() % M);
}
};
In the example above I've defined a new class called "MyLess" that supports a member function "fn" that can be used to compare the values returned from two objects and return true if the modulo value of the left one is less than the right one (Note: In C++ this function would normally be written using an overloaded operator(), but JavaScript doesn't support operator overloading, so for the purposes of this article I have used a normal function.) This class may be used to compare objects of any type so long as the object implements a getValue() method that returns a numeric value that the % (modulo) operator can operate on.
In JavaScript we can easily mimic the behaviour of this template class:
function MyLess(M)
{
this.M = M;
}
MyLess.prototype.fn =
function(left,right)
{
return (left.getValue() % this.M) <
(right.getValue() % this.M);
}In this JavaScript version, the template parameter M is passed in as an argument to the MyLess constructor; there is no need to identify the class T here as the function fn will only execute properly if its arguments support a getValue() method.
Namespaces
Namespaces do for C++ what departments do for a superstore; they partition off different sections of the code and help avoid the nightmare of name clashes between unrelated pieces of code. This is particularly useful when different parts of the code use the same name to identify different things. For example, the full name of the STL list is std::list; std is the namespace defined by the STL. Since there is no specialized namespace mechanism in JavaScript I have used the next best thing: prefixes. You could argue that C++ namespaces are just prefixes in disguise and indeed implementations of C++ use a form of prefixing (otherwise known as name mangling) to implement namespaces. For the JavaScript STL, I have use the prefix "STD."
Const
const in C++ is an indicator to the compiler and programmer that the variables and objects it is associated with are not to be modified. JavaScript has no native support for const-ness so to implement the behaviour of const would require runtime flags. This would add an unnecessary complexity to the code so I have omitted this feature from this implementation.
Operator overloading
Operator overloading in C++ is a convenience mechanism that allows special behaviour to be programmed into operators such as ++, --, = and even (). In practice it's just a way for the programmer to assign functions to specific operators and this feature is used extensively in the STL. Since JavaScript doesn't support overloaded operators, the JavaScript STL code substitutes named functions instead. To maintain an degree of consistency I have settled on using the following substitutions:
|
C++ operator |
JavaScript named function |
|
operator++ |
increment() |
|
operator-- |
decrement() |
|
operator() |
fn() |
Function overloading
Function overloading in C++ allows multiple functions sharing the same name to be defined. The compiler knows which version to call depending on the types of arguments passed to the function:
void F(int i)
{
// do something with an integer
}
void F(string s)
{
// do something with a string
}
...
F(5); // calls F(int)
F("hello"); // calls F(string)JavaScript has no function overloading, any function name may only have one implementation associated with it at any one time, however, it's possible to simulate function overloading by detecting the argument types at runtime. For example:
function F(v)
{
if ( typeof(v) == "string" ) // do something
with a string
else // do something with an integer
}This one function serves the same purpose as the pair of overloaded C++ functions above. Each time it is called, it tests whether the argument is a string or not and decides what to do with it afterwards.
Created: March 27, 2003
Revised: August 22, 2005
URL: https://webreference.com/programming/javascript/gr/column13/1
Find a programming school near you