C++ Standard Library Data Structures and Algorithms

C-Style Arrays

In stack: int a[3] = {0, 1, 2};

In heap: int* b = new int[3];

Sorting

std::sort(myvector.begin(), myvector.end());

Example 2: std::sort(myvector.begin(), myvector.end(), myCompFunction);

mylist.sort() or mylist.sort(compare_nocase);

bool compare_nocase(const std::string& first, const std::string& second) { return first < second; }

Templated Classes

Include template <typename T> above the header.

Each function has a template declaration:

template <typename T>
class_name<T>::getmax () {
  // ...
}

typedef list_iterator iterator;

Strings

str.substr(3, 5) (starts at position 3, length 5)

str1.compare(str2) != 0

str.length()

Lists

iterator insert(iterator position, const value_type& val); (returns pair)

Maps

std::map<int, char> bob;

bob.insert(std::make_pair(1, 'a'));

Accessing elements: bob[1]

Queues

Operations: front(), back(), push(), pop() (void)

Priority Queues

Operations: push(), pop(), top()

Unordered Maps

std::unordered_set<std::string> seedSet;

HashSeed(tmpBox, &images[i]);

Tree Traversals

Inorder: 1. Left subtree (recursive call) 2. Process root 3. Right subtree

Preorder: 1. Process root 2. Left subtree 3. Right subtree

Postorder: 1. Left subtree 2. Right subtree 3. Process root

Main Function Structure

int main(int argc, char* argv[]) {
  // ...
}

Inheritance

Protected and private inheritance are options:

• With protected inheritance, public members become protected, and other members are unchanged.
• With private inheritance, all members become private.

Virtual Functions

Some functions are marked virtual. This means that when redefined by a derived class, the new definition will be used, even for pointers to base class objects.

Pure virtual functions (declared with = 0) must be redefined in a derived class.

• Any class with pure virtual functions is called "abstract".
• Objects of abstract types cannot be created; only pointers to these objects may be created.
• Functions specific to a particular object type are declared in the derived class prototype.

Red-Black Tree Properties

1. The root is black.
2. If a node is red, its children must be black.
3. Every path from a node to a null descendant must contain the same number of black nodes.

Classes: Constructors and Operators

Copy constructor: Point(const Point &p2);

Assignment operator:

class_name& class_name::operator=(const class_name &other) {
  if (&other == this)
    return *this;
  // ... copy members ...
  return *this;
}

Destructor: ~class_name();