The C++ Standad Template Library (STL) Containers

Requirement Compare

Compare is a set of requirements expected by some of the standard library facilities from the user-provided function object types.

The return value of the function call operation applied to an object of a type satisfying Compare, when contextually converted to bool, yields true if the first argument of the call appears before the second in the strict weak ordering relation induced by this type, and false otherwise.

As with any BinaryPredicate, evaluation of that expression is not allowed to call non-const functions through the dereferenced iterators.

The associative containers std::set, std::map, std::multiset, and std::multimap as well as std::priority_queue expect a Compare type.

The following standard library functions or algorithms expect a Compare type, too:

sort

sorts a range into ascending order (function template)

sort

sorts the elements (public member function of std::forward_list<T,Allocator>)

sort

sorts the elements (public member function of std::list<T,Allocator>)

stable_sort

sorts a range of elements while preserving order between equal elements (function template)

partial_sort

sorts the first N elements of a range (function template)

partial_sort_copy

copies and partially sorts a range of elements (function template)

is_sorted (C++11)

checks whether a range is sorted into ascending order (function template)

is_sorted_until (C++11)

finds the largest sorted subrange (function template)

nth_element

partially sorts the given range making sure that it is partitioned by the given element (function template)

lower_bound

returns an iterator to the first element not less than the given value (function template)

upper_bound

returns an iterator to the first element greater than a certain value (function template)

binary_search

determines if an element exists in a certain range (function template)

equal_range

returns range of elements matching a specific key (function template)

merge

merges two sorted ranges (function template)

merge

merges two sorted lists (public member function of std::forward_list<T,Allocator>)

merge

merges two sorted lists (public member function of std::list<T,Allocator>)

inplace_merge

merges two ordered ranges in-place (function template)

includes

returns true if one set is a subset of another (function template)

set_difference

computes the difference between two sets (function template)

set_intersection

computes the intersection of two sets (function template)

set_symmetric_difference

computes the symmetric difference between two sets (function template)

set_union

computes the union of two sets (function template)

push_heap

adds an element to a max heap (function template)

pop_heap

removes the largest element from a max heap (function template)

make_heap

creates a max heap out of a range of elements (function template)

sort_heap

turns a max heap into a range of elements sorted in ascending order (function template)

is_heap (C++11)

checks if the given range is a max heap (function template)

is_heap_until (C++11)

finds the largest subrange that is a max heap (function template)

max

returns the greater of the given values (function template)

max_element

returns the largest element in a range (function template)

min

returns the smaller of the given values (function template)

min_element

returns the smallest element in a range (function template)

minmax (C++11)

returns the smaller and larger of two elements (function template)

minmax_element (C++11)

returns the smallest and the largest elements in a range (function template)

lexicographical_compare

returns true if one range is lexicographically less than another (function template)

next_permutation

generates the next greater lexicographic permutation of a range of elements (function template)

prev_permutation

generates the next smaller lexicographic permutation of a range of elements (function template)

Stack

A stack implements a stack or FILO (First In Last Out) queue and is based on a deque by default, although it might use a vector just as well.

Queue

A queue implements a (First In Last Out) queue and is based on a deque by default, although it might use a vector just as well.

Prority Queue

A prority_queue keeps its elements sorted and produces the smallest element according to some comparison function object. It is otherwise called a heap and is based on a vector by default because it requires random access and swapping elements.

You can write a customized priority queue by availing yourself of the following STL algorithms, which rely on random-access iterators, as found in vector and queue:

template <class RandIter>
void make_heap(RandIter start, RandIter end);
template <class RandIter, class Comp>
void make_heap(RandIter start, RandIter end, Comp cmpfn);
//
template <class RandIter>
void push_heap(RandIter start, RandIter end);
template <class RandIter, class Comp>
void push_heap(RandIter start, RandIter end, Comp cmpfn);
//
template <class RandIter>
void pop_heap(RandIter start, RandIter end);
template <class RandIter, class Comp>
void pop_heap(RandIter start, RandIter end, Comp cmpfn);

Or you can turn a sequence into a heap all at once by calling:

template <class RandIter>
void sort_heap(RandIter start, RandIter end);
template <class RandIter, class Comp>
void sort_heap(RandIter start, RandIter end, Comp cmpfn);

Doubly-Linked Lists

A list is a sequence optimized for insertion and deletion of elements. When you insert into a list or delete an element from a list , the locations of other elements of the list are not affected. In particular, iterators referring to other elements are not affected.

The STL provides two linked-list types:

1. list: a doubly-linked list, and
2. forward_list: a singly-linked list introduced in recent revisions (C++11)

These are implemented in container list<>.

With the exception of subscripting, capacity management, and size() for forward_list, the STL lists provide the member types and operations offered by vector<>. In addition, list<> and forward_list<> provide specific list member functions:

Vectors

std::vectors are automatic arrays which keep track of their size, that is how many places have been occupied (pressumably in an integer variable), as well as their capacity, which is the total number of objects of the given type that they can accomodate. Further, when they have filled up, they reallocate their sequence of objects in a larger chunk of memory, the start of this run of memory is updated (in a pointer variable), and the new, larger capacity is updated, too. This means that indeces into the array-like structure remain valid, but pointers are invalidated, so they must never be taken in the first place.

Unlike with linked lists, insertions (or deletions) are either meaningless or demand that all objects after the one inserted be shifted one place, which is done in linear time, whereas lists perform insertions and deletions in constant time. Furthermore, insertions and deletions would invalidate all subsequent indeces...

Deques

A deque (pronounced "deck") is very similar to a vector. It manages its elements with a dynamic array, provides random access, and has almost the same interface as a vector. The difference is that with a deque the dynamic array is open at both ends. Thus, a deque is fast for insertions and deletions at both the end and the beginning.

Deques have the following differences compared with the abilities of vectors:

1. Inserting and removing elements is fast both at the beginning and at the end (for vectors it is only fast at the end). These operations are done in amortized constant time.
2. The internal structure has one more indirection to access the elements, so element access and iterator movement of deque's are usually a bit slower.
3. Iterators must be smart pointers of a special type rather than ordinary pointers because they must jump between different blocks.
4. In systems that have size limitations for blocks of memory (for example, some PC systems), a deque might contain more elements because it uses more than one block of memory. Thus, max_size() might be larger for deque's.
5. Deques provide no support to control the capacity and the moment of reallocation. In particular, any insertion or deletion of elements other than at the beginning or end invalidates all pointers, references, and iterators that refer to elements of the deque.
6. However, reallocation may perform better than for vectors, because according to their typical internal structure, deque's don't have to copy all elements on reallocation.
7. Blocks of memory might get freed when they are no longer used, so the memory size of a deque might shrink (however, whether and how this happens is implementation specific).

Bitmap's*

Immutability of Associative Containers

Since the elements of an associative container are stored according to their keys (in a binary tree, hash table...), it is essential that the key associated with each element is immutable. In simple associative containers this means that the elements themselves are immutable, while in other types of associative containers, such as pair associative containers, the elements themselves are mutable but the part of an element that is its key cannot be modified or assigned a value to. This has an important consequence: associative containers cannot have mutable iterators in the sense that if it is an iterator for an associative container and t is an object of it's value type, then *it = t is not a valid expression.

Consequently, every element of a simple associative container is immutable: objects may be inserted and erased, but not modified.

Types of Associative Containers

Associative containers are either maps or sets. A map associates or maps a key to a value, whereas in a set (set and multiset) their elements are their own keys.

A map may be either a stl::map or a stl::multi_map, and a set may be either a stl::set or a stl::multi_set. Here the prefix multi means that elements with the same key are allowed. Furthermore, sameness is to be understood not literally but according to a function or a function object that takes to objects and returns a boolean value.

According to their implementation and performance, associative containers are further divided into:

1. ordered containers: and are set, multiset, map, and multimap. They are implemented as binary trees, often red-black trees. They use a comparison function or a comparison function object to compare keys.
2. unordered containers: and are unordered_set, unordered_multiset, unordered_map, and unordered_multimap. According to Bjarne Stroutstrup, they are implemented as hash tables with linked overflow.

Comparison Function Objects for STL's Associative Containers

template
<
class T,
class Compare = less<T>,
class Alloc = allocator<T>
>
class set;

#include <algorithm>
#include <functional>
#include <iostream>
#include <set>
#include <string>

class Person {
public:
	explicit Person(int id, const std::string &name) : m_id{id}, m_name{name} {}
	const int id() const {return m_id;}
	const std::string& name() const {return m_name;}
private:
	const int m_id;
	const std::string m_name;
};

bool operator<(const Person &lhs, const Person &rhs) { // compare by id
	return lhs.id() < rhs.id();
}

std::ostream& operator<<(std::ostream &os, const Person &rhs) { // for formatted output
	os << "Id: " << rhs.id() << ", Name: " << rhs.name();
	return os;
}

struct PersonCompareByName {
	bool operator()(const Person &lhs, const Person &rhs) const {
		return lhs.name() < rhs.name();
	}
};

int main() {
	auto people = {Person{2, "C"}, Person{3, "A"}, Person{1, "B"}};

	// By Id
	std::set<Person> peopleById = people;
	std::cout << "By Id: " << "\n\n";
	std::copy(cbegin(peopleById), cend(peopleById), std::ostream_iterator<Person>{std::cout, "\n"});

	std::cout << '\n';

	// By Name (1)
	std::set<Person, PersonCompareByName> peopleByName = people;
	std::cout << "By Name (1): " << "\n\n";
	std::copy(cbegin(peopleByName), cend(peopleByName), std::ostream_iterator<Person>{std::cout, "\n"});

	std::cout << '\n';

	// By Name (2)
	auto personComparator = [](const auto &lhs, const auto &rhs) {return lhs.name() < rhs.name();};
	std::set<Person, decltype(personComparator)> peopleByName2{people, personComparator};
	std::cout << "By Name (2): " << "\n\n";
	std::copy(cbegin(peopleByName2), cend(peopleByName2), std::ostream_iterator<Person>{std::cout, "\n"});

	return 0;
}

Using a std::set for Recording Visited Items

We will be using the following:

1. insertions, and possibly deletions
2. const_iterator std::set::find( const Key& key ) const
3. const_iterator std::set::end() const for comparing the returned value

This would enable us to write a bool has(s, k) const, and a similar bool has_or_add(s, k) function.

In many situations the key type would be just a pointer...

Difference Between std::map::operator[](KEY) and std::map::at(KEY)

f you access a key using the indexing operator [] that is not currently a part of a map, then it automatically adds a key for you. This is a huge caveat. For this reason, I prefer using the indexing operator [] for setting, and members find() / at() for lookup.

Another advantage of using at() over [] is the fact that it can operate on a const std::map, whereas [] won't.

at(key) throws an exception if the key doesn't exist.