Standard string
s.at(index) or s[index] // access single char
s + text OR s += text
s.substr(start) // return new substring
s.substr(start, length)
s.find(key) // returns index or string::npos
s.erase(index, length) // erase, insert, replace destructively modify s
s.insert(index, text)
s.replace(index, length, text)
for (char ch: s) { ... } // chars visited in order
Stanford strlib.h
if (equalsIgnoreCase(s1, s2)) { ... }
if (endsWith(str, suffix)) { ... }
if (startsWith(str, prefix)) { ... }
if (stringContains(str, key) { ... }
integerToString(int)
stringToInteger(str)
realToString(double)
stringToReal(str)
stringSplit(str, delimiter) // returns Vector of tokens
toLowerCase(str)
toUpperCase(str)
trim(str) // remove leading/trailing whitespace
Vector
Vector v = {elem, elem, ... , elem};
v.add(elem) OR v += elem
v.clear()
v.get(index) OR v[index]
v.insert(index, elem)
if (v.isEmpty()) { ... }
v.remove(index)
v.set(index, elem) OR v[index] = elem
v.size()
for (T elem: v) { ... } // visited in order of index
Grid
Grid g(nRows, nCols);
int numCells = grid.numRows() * grid.numCols()
if (grid.inBounds(row, col)) { ...}
grid[row][col] = value
for (T elem: grid) { ... } // visited left-to-right, top-to-bottom
GridLocation
GridLocation loc = {row, col};
grid[loc] = value
if (grid.inBounds(loc)) { ... }
GridLocation neighbor = {loc.row + 1, loc.col - 1};
if (loc == neighbor) { ... }
Stack
Stack s = {bottom, ... , top};
s.push(elem)
s.peek() // Look at top
s.pop() // Removes top
s.size()
if (s.isEmpty()) { ... }
s.clear()
// no iterator, no direct access to elements other than top
Queue
Queue q = {front, ... , back};
q.enqueue(elem)
q.peek() // Look at front
q.dequeue() // Removes front
q.size()
if (q.isEmpty()) { ... }
q.clear()
// no iterator, no direct access to elements other than front
Set
Set s = {elem1, elem2, ... , elemN};
if (s.contains(elem)) { ... }
s.add(elem)
s + elem; s + set2; // union
s.remove(elem)
s - elem; s - set2; // difference
intersectSet = s1 * s2;
s.size()
if (s.isEmpty()) { ... }
if (s.isSubsetOf(s2)) { ... }
s.clear()
// Visits elements in sorted order
for (T elem: set) { ... }
Map
Map m = { { key1, val1}, ... {keyN, valN } };
m.put(key, value) OR m[key] = value
m.get(key) OR m[key] // bracket form auto-inserts default value if not present
if (m.containsKey(key)) { ... }
m.size()
if (m.isEmpty()) { ... }
m.remove(key)
m.clear()
Vector keys = m.keys();
// Visits keys in sorted order
for (K key: m) { ... }
Lexicon
Lexicon lex(filename);
if (lex.contains(word)) { ... }
if (lex.containsPrefix(prefix)) { ... }
Priority Queue
PriorityQueue pq = { { pri1, key1}, ... {priN, keyN } };
pq.changePriority(value, newPriority)
pq.clear()
pq.dequeue()
pq.enqueue(value, priority)
pq.equals(pq)
pq.isEmpty()
pq.peek()
pq.peekPriority()
pq.size()
Breadth First Search Pseudocode
function bfs(v1, v2):
create a queue of vertexes to visit,
initially storing just v1.
mark v1 as visited.
while queue is not empty and v2 is not seen:
dequeue a vertex v from it,
mark that vertex v as visited,
and add each unvisited neighbor n of v to queue.
Dijkstra's Algorithm Pseudocode
function dijkstra(v1, v2):
consider every vertex to have a cost of infinity,
except v1 which has a cost of 0.
create a priority queue of vertexes, ordered
by heuristic, storing only v1
while the pqueue is not empty:
dequeue vertex v from pqueue, mark as visited.
for each of the unvisited neighbors n of v,
we now know that we can reach this neighbor
with a total cost of (v's cost + the weight
of the edge from v to n).
if the neighbor is not in the pqueue, or
this is cheaper than n's current cost, we
should enqueue the neighbor n to the
pqueue with this new cost, and with v as
its previous vertex.
when done, we can reconstruct the path from v2
back to v1 by following the previous pointers.
A* Algorithm Pseudocode
function astar(v1, v2):
consider every vertex to have a cost of infinity,
except v1 which has a cost of 0.
create a priority queue of vertexes, ordered
by heuristic, storing only v1 with a priority
of H(v1, v2).
while the pqueue is not empty:
dequeue vertex v from pqueue, mark as visited.
for each of the unvisited neighbors n of v,
we now know that we can reach this neighbor
with a total cost of (v's cost + the weight
of the edge from v to n).
if the neighbor is not in the pqueue, or
this is cheaper than n's current cost, we
should enqueue the neighbor n to the
pqueue with this new cost plus H(n, v2),
and with v as its previous vertex.
when done, we can reconstruct the path from v2
back to v1 by following the previous pointers.