Standard Template Library - Algorithms

COMP282 Lectures 2022-03-22

There are the following types of algorithms:

• Min/Max:
  • min_element, max_element
• Sorting:
  • sort, stable_sort
• Non-modifying Sequence:
  • all_of, any_of, none_of, find_if, count_if
• Modifying Sequence:
  • copy, shuffle, unique, reverse
• Misc
  • Helper functions for searches, sorts and tree structures.

min

We can write our own simple algorithm like so:

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

bool compare(int i1, int i2) {
	return i1 < i2;
}

int main() {
	vector<int> arr;
	for (int i = 0; i < 100; i++) {
		arr.push_back(i);
	}
	cout << *min_element(arr.begin(), arr.end(), compare);
}

This functionality is also available in functional:

#include <vector>
#include <algorithm>
#include <funcitonal>
#include <iostream>
using namespace std;

int main() {
	vector<int> arr;
	for (int i = 0; i < 100; i++) {
		arr.push_back(i);
	}
	cout << *min_element(arr.begin(), arr.end(), less<int>());
}

Functors

Functors are classes with () overloaded, like less. We can use them instead of pointers.

Comparator.hpp:

class Comparator {
	int c;
	public:
	Comparator(int c) : c(c) {}
	bool operator()(int i1, int i2);
}

Comparator.cpp:

#include "Comparator.h"
#include <cmath>
bool Comparator::operator()(int i1, int i2) {
	if (std::abs(c - i1) < std::abs(c - i2)) {
		return true;
	}
	return false;
}

We can then use the comparator in our min program:

#include <vector>
#include <algorithm>
#include <funcitonal>
#include <iostream>
using namespace std;

int main() {
	vector<int> arr;
	for (int i = 0; i < 100; i++) {
		arr.push_back(i);
	}
	int c;
	cin >> c;
	cout << *min_element(arr.begin(), arr.end(), Comparator(c));
}

sort & stable_sort

#include <vector>
#include <algorithm>
#include <iostream>
#include Comparator.h
using namespace std;

int main() {
	vector<int> arr;
	for (int i = 0; i < 100; i++ ) {
		arr.push_back(i);
	}
	int c;
	cin >> c;
	sort(arr.begin(), arr.end(), Comparator(c));
	for (auto x : arr) {
		cout << x << " ";
	}
}

We can replace sort with stable_sort if we want to sort stably.

shuffle

#include <vector>
#include <algorithm>
#include <iostream>
#include <random>
using namespace std;

int main() {
	vector<int> arr;
	for (int i = 0; i < 100; i++ ) {
		arr.push_back(i);
	}
	unsigned seed;
	cin >> seed;	// we can also set the seed using the time
	shuffle(arr.begin(), arr.end(), default_random_engine(seed));
	for (auto x : arr) {
		cout << x << " ";
	}
}

unique

This algorithm uses == to remove duplicates:

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int main() {
	vector<int> arr;
	for (int i = 0; i < 100; i++ ) {
		arr.push_back(1);
	}
	int c;
	cin >> c;
	unique(arr.begin(), arr.end());
	for (auto x : arr) {
		cout << x << " ";
	}
}

copy

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int main() {
	vector<int> arr;
	for (int i = 0; i < 100; i++ ) {
		arr.push_back(i);
	}
	vector<int> arr2;
	for (int i = 0; i < 100; i++ ) {
		arr2.push_back(-i);
	}
	move(arr.begin() + 5, arr.end(), arr2.begin() + 5);
	for (auto x : arr2) {
		cout << x << " ";
	}
	cout << endl;
	cout << arr.size();
	for (auto x : arr) {
		cout << x << " ";
	}
}