Core Concepts

Libraries organize related functionality into separate modules to achieve decoupling. Name spaces resolve conflicts from identically named functions across different libraries. C++ is fully backward compatible with C.

All standard C++ components (classes, functions, variables) are placed in the std name space, so cout is fully qualified as std::cout, you can use it directly with std::cout without importing the entire name space, or import just the components you need like using std::cout;.

Basic Input/Output

#include <iostream>
using namespace std;
int main() {
    int age;
    cout << "How old are you?" << endl;
    cin >> age;
    cout << age << endl;
    return 0;
}

endl adds a newline and flushes the output buffer, << is the stream insertion operator, and >> is the stream extraction operator.

Common Gotchas

1. C++20 allows auto to automatically deduce iterator types.
2. Name collisions: if you name a variable the same as an existing class, simply rename the variable to resolve the issue.
3. Avoid naming your custom functions the same as standard library functions to prevent ambiguity.

Data Types

Boolean Type

bool can only hold two values: true (any non-zero input) and false (zero input):

#include <iostream>
using namespace std;
int main() {
    bool flag = 2; // Equivalent to bool flag = true; or bool flag = 1;
    cout << flag << endl; // Outputs 1
    return 0;
}

String Class

#include <string>
#include <iostream>
using namespace std;
int main() {
    string my_str = "ABCD";
    cout << my_str.length() << endl; // Outputs 4, does not count the null terminator
    my_str[2] = 'c'; // Now "ABcD"
    cout << my_str.append(" EFG") << endl; // Append text to the end
    cout << my_str.find("EFG") << endl; // Returns starting index of "EFG" (E is at index 5)

    string sub = my_str.substr(2, 4); // Extract substring starting at index 2, length 4
    cout << sub << endl; // Outputs "cD E"

    my_str.erase(1, 3); // Delete 3 characters starting at index 1
    cout << my_str << endl; // Outputs "A EFG"

    my_str.replace(0, 4, "Hi"); // Replace 4 characters starting at 0 with "Hi"
    cout << my_str << endl; // Outputs "HiG"
    return 0;
}

Wide Character Type

Requires #include <cwchar> and #include <locale>, used for storing Unicode character values (typically 2 or 4 bytes per character). Related wide I/O streams include wcin, wcerr, wofstream, wifstream:

#include <cwchar>
#include <iostream>
#include <locale>
using namespace std;
locale sys_loc("chs");
int main() {
    wcin.imbue(locale("", LC_CTYPE)); // Configure wcin to use system local language
    wcout.imbue(sys_loc); // Set output locale
    wchar_t greeting[] = L", let's go!";
    wchar_t input_buf[1000];
    wcin.getline(input_buf, 4); // Can read 2 Chinese characters, for example
    wcout << input_buf << greeting << L"\n";
    return 0;
}

Functions

Default Parameters

Default parameters must be declared from right to left, with all default parameters placed at the end of the parameter list:

int power(int base, int exponent = 6);

Lvalue References

A reference is an alias for an existing variable. int &ref = original is equivalent to int* const ref = &original — the reference address cannot be changed after initialization:

int original = 10;
int &ref1 = original, &ref2 = ref1; // Both ref1 and ref2 are aliases for original
cout << ref1 << endl; // Outputs 10
ref2++;
cout << original << endl; // Outputs 11

Common use case: pass by reference for swapping:

void swapByRef(int &x, int &y) {
    int temp = x;
    x = y;
    y = temp;
}
void swapByPtr(int *x, int *y) {
    int temp = *x;
    *x = *y;
    *y = temp;
}
int main() {
    int m = 1, n = 2;
    swapByRef(m, n);
    cout << m << " " << n << endl;
    swapByPtr(&m, &n);
    cout << m << " " << n << endl;
    return 0;
}
// Output:
// 2 1
// 1 2

Function Overloading

Overloading improves code readability by allowing the same function name to handle different input types. It requires the same function name with different parameter lists. Overloading only based on different return types is not allowed, as it causes ambiguity:

int add(int a);
int add(int a, int b);
int add(char a, int b);
int add(int a, int b, int c);
// Valid overloading example

All of the following cases cause ambiguity when resolving calls:

int func(int a, int b);
int func(int &a, int &b);
int func(int a, int b, int c = 3);
string func(int a, int b);

Inline Functions

Use inline for small, frequently called functions. The inline keyword suggests the compiler expand the function body directly at the call site to avoid runtime function call overhead (the compiler may ignore the suggestion):

inline int findMax(int x, int y, int z) {
    return x > y ? (x > z ? x : z) : (y > z ? y : z);
}
int main() {
    cout << findMax(1, 2, 3) << endl;
    return 0;
}

Lambda (Anonymous) Functions

Syntax: [capture_list](parameters) -> return_type { function_body }; Or [capture_list](parameters) { function_body }; when return type can be automatically deduced.

Capture rules:

• [&]: Capture all used variables by reference
• [=]: Capture all used variables by value
• [&, N]: Capture N by value, all other used variables by reference
• [=, &N]: Capture N by reference, all other used variables by value
• [this]: Capture current class instance pointer (for use inside class methods)
• [*this]: Capture a full copy of the current class instance
• [val = init]: Create a new captured variable initialized to init

Example:

int x = 10, y = 20;
auto calculate = [x, &y](int m, int n) {
    // x is captured by value, cannot be modified inside the lambda
    // y is captured by reference, can modify the outer variable
    y = 50;
    return x * m + n * y;
};
cout << calculate(10, 2) << endl; // Output 200
cout << y << endl; // Output 50

Object-Oriented Programming

Object-oriented programming has four core characteristics: abstraction, encapsulation, inheritance, and polymorphism.

Classes and Objects

#include <iostream>
using namespace std;
class Circle {
public:
    float radius;
    Circle(float input_radius) {
        this->radius = input_radius;
    }
    float calculateArea() {
        return 3.14f * radius * radius;
    }
    float calculateCircumference() {
        return 2 * 3.14f * radius;
    }
};
int main() {
    Circle c1(1.0f), c2(2.5f);
    cout << c1.calculateArea() << endl << c1.calculateCircumference() << endl;
    return 0;
}

Constructors and Destructors

• Constructor: called automatically when a object is created, can be overloaded, has no return value, and must have the same name as the class.
• Destructor: called automatically when an object is destroyed, cleans up allocated resources, has no parameters and no return value.

class DataBuffer {
public:
    int size;
    char *buffer = nullptr;
    DataBuffer(int input_size) {
        this->size = input_size;
        buffer = (char*)malloc(100 * sizeof(char));
    }
    ~DataBuffer() {
        free(buffer);
    }
};

Encapsulation

Encapsulation hides internal implementation and exposes controlled public interfaces:

#include <string>
#include <iostream>
using namespace std;
class LibraryBook {
private:
    string title;
    int stock;
public:
    LibraryBook(string input_title) {
        this->stock = 0;
        this->title = input_title;
    }
    void setTitle(string new_title) {
        this->title = new_title;
    }
    void setStock(int new_stock) {
        this->stock = new_stock;
    }
    string getTitle() const { // const member function, cannot modify member variables
        return title;
    }
    int getStock() const {
        return stock;
    }
};
int main() {
    LibraryBook book("Twenty Thousand Leagues Under the Sea");
    book.setStock(30);
    cout << book.getTitle() << endl;
    cout << book.getStock() << endl;
    return 0;
}

Inheritance

Inheritance enables code reuse, where a derived (child) class inherits members from a base (parent) class:

#include <iostream>
using namespace std;
class Base {
public:
    int valBase;
    Base() {
        valBase = 1;
    }
    void printBase() {
        cout << "Base\n";
    }
};
class DerivedMid : public Base {
public:
    int valMid;
    DerivedMid() {
        valMid = 1;
    }
    void printMid() {
        cout << "Mid\n";
    }
    void show() {
        cout << "Mid level";
    }
};
class FinalDerived : public DerivedMid {
public:
    int valFinal;
    FinalDerived() {
        valFinal = 1;
    }
    void printFinal() {
        cout << "Final\n";
    }
    void show() {
        cout << "Final level";
    }
};
int main() {
    FinalDerived obj;
    obj.printBase();
    obj.printMid();
    obj.printFinal();
    // For identically named members across inheritance hierarchy
    obj.show(); // Default uses derived class's member
    obj.DerivedMid::show(); // Use base namespace to explicitly access parent member
    return 0;
}

Inheritance Access Modes

Inheritance can be public, protected, or private:

• Private members of the base class are never accessible to derived classes.
• Public base members become protected in the derived class when using protected inheritance.

Example:

class Base {
private:
    int secret;
public:
    void setSecret(int n) { secret = n; }
    int getSecret() const { return secret; }
};
class Derived : protected Base {
protected:
    int extra;
public:
    void setValues(int m, int n) { Base::setSecret(m); extra = n; }
    int getSum() const { return Base::getSecret() + extra; }
};
// Derived now has 3 protected members: inherited setSecret, getSecret, and own extra

Inheritance access rules summary:

1. Only base class non-private members are inherited, and their access level is adjusted according to the inheritance mode.
2. External access via derived object: only public base members are accessible when using public inheritance.
3. Access inside derived class: all base members except private are accessible.

Virtual Functions

Base class virtual functions can be overridden in derived classes, but parameter and return types must match exactly:

• Pure virtual function: Declared but not implemented in the base class, must be overridden by derived classes.
• Abstract class: A class that contains at least one pure virtual function, cannot be instantiated.
• Interface: A class that contains only pure virtual functions.

Derived classes can add the virtual keyword when overriding to allow further overriding in subsequent subclasses:

class Person {
public:
    virtual void introduce() {
        cout << "I am a person";
    }
    virtual float getArea() = 0; // Pure virtual function
};
class Student : public Person {
public:
    float radius;
    void introduce() override {
        cout << "I am a student";
    }
    float getArea() override {
        return 3.14f * radius * radius;
    }
};
int main() {
    Student s;
    s.introduce();
    return 0;
}

Polymorphism

Binding is the process of resolving which implementation of a same-name function to call:

1. Runtime polymorphism (dynamic binding): Achieved via virtual function override + base class pointer pointing to a derived class object.
2. Compile-time polymorphism (static binding): Achieved via function overloading.

Example:

#include <iostream>
using namespace std;
class Shape {
public:
    virtual float getArea() = 0;
};
class Rectangle : public Shape {
public:
    float width, height;
    Rectangle(float w, float h) {
        width = w;
        height = h;
    }
    float getArea() override {
        return width * height;
    }
};
class Circle : public Shape {
public:
    float radius;
    Circle(float r) {
        radius = r;
    }
    float getArea() override {
        return 3.14f * radius * radius;
    }
};
void printArea(Shape *shape) {
    cout << shape->getArea() << endl;
}
int main() {
    Circle c(10.0);
    Rectangle r(5.5, 6.0);
    printArea(&c);
    printArea(&r);
    Shape *p = &c;
    cout << p->getArea(); // Calls Circle's getArea, uses the Circle's radius member
    return 0;
}

Friend

Friend allows external functions or other classes to access private members of the current class. Rules: friend relationship is not inherited, is one-way, and not transitive.

Friend Function

#include <iostream>
using namespace std;
class Box {
private:
    double volume;
public:
    friend void printBoxVolume(Box box);
    void setVolume(double v) {
        volume = v;
    }
};
void printBoxVolume(Box box) {
    cout << box.volume << endl; // Access private member
}
int main() {
    Box myBox;
    myBox.setVolume(9.5);
    printBoxVolume(myBox);
    return 0;
}

Friend Class

#include <iostream>
using namespace std;
class Inner {
private:
    double calculate(double input) {
        return input;
    }
public:
    friend class Outer;
};
class Outer {
private:
    double val;
public:
    void setVal(double v) {
        val = v;
    }
    void printResult() {
        cout << Inner().calculate(val); // Access private method of Inner
    }
};
int main() {
    Outer obj;
    obj.setVal(5.0);
    obj.printResult();
    return 0;
}

To declare a member function of another class as friend: friend void ClassA::show(ClassB &obj);

Templates

Templates allow functions and classes to work with arbitrary data types, you specify the type when using the template:

#include <iostream>
#include <string>
using namespace std;
template<typename T>
T getLarger(T a, T b) {
    return a > b ? a : b;
}

template<typename T, typename U>
class MultiType {
public:
    void printValues(T first, U second) {
        cout << first << "\t" << second << endl;
    }
    T returnFirst(T input) {
        return input;
    }
};

int main() {
    int x = 10, y = 20;
    cout << getLarger<int>(x, y) << endl; // Output 20
    double m = 3.14, n = 2.718;
    cout << getLarger<double>(m, n) << endl; // Output 3.14

    MultiType<string, int> instance;
    cout << instance.returnFirst("hello") << endl;
    instance.printValues("test", 100);
    return 0;
}

Operator Overloading and Function Objects (Functors)

A function object is an object that can be called like a regular function, achieved by overloading operator(). It can hold internal state and be passed as a parameter.

Conversion operators convert a class object to another type. Syntax: operator TargetType() {}, rules: must be a class method, no return type declared, no parameters. Use explicit to prevent unintended implicit conversion.

Example:

#include <iostream>
#include <string>
using namespace std;
class Counter {
public:
    int count;
    Counter() : count(0) {}
    operator int() {
        cout << "Converting to int" << endl;
        return 1;
    }
    explicit operator double() {
        cout << "Explicit conversion to double" << endl;
        return 1.5;
    }
    string operator()(string a, string b) {
        return a.append(b);
    }
};
int main() {
    Counter cnt;
    int b = int(cnt); // Explicit conversion
    cout << b << endl;
    cout << (double)cnt << endl; // Explicit conversion
    cout << cnt("Hello ", "World!") << endl; // Output "Hello World!"
    return 0;
}

Operator overloading can be implemented as a class member function or a global friend function:

#include <iostream>
using namespace std;
class Point {
public:
    int x;
    double y;
    Point() {}
    Point(int x, double y) : x(x), y(y) {}
    ~Point() {}
    Point operator+(const Point& other) const {
        Point res;
        res.x = x + other.x;
        res.y = y + other.y;
        return res;
    }

    friend Point operator-(const Point& a, const Point& b) {
        Point res;
        res.x = a.x - b.x;
        res.y = a.y - b.y;
        return res;
    }
};
int main() {
    Point p1(1, 1.1);
    Point p2(2, 2.2);
    Point sum = p1 + p2;
    Point diff = p1 - p2;
    cout << sum.x << "\t" << sum.y << endl; // 3  3.3
    cout << diff.x << "\t" << diff.y << endl; // -1 -1.1
    return 0;
}

File Input/Output

Use \ for path separators on Windows, / on Linux. Core classes:

• ifstream: Read from file
• ofstream: Write to file
• fstream: Read/write access

Common file operations:

Function	Purpose
seekg()	Move the read file pointer to the specified position
seekp()	Move the write file pointer to the specified position
tellg()	Get the current position of the read pointer
eof()	Check if the file pointer has reached the end of the file
good()	Check if the last file operation succeeded

Open mode flags:

Mode Flag	Behavior
std::ios::in	Open for reading
std::ios::out	Open for writing. Creates new file if not exists, truncate existing content if exists
std::ios::app	Open for appending. Creates new if not exists, append to end if exists
std::ios::binary	Open in binary mode
std::ios::ate	Open file and position pointer at end
std::ios::trunc	Truncate existing file when opening for writing
std::ios::beg	Calculate offset from the start of the file
std::ios::end	Calculate offset from the end of the file
std::ios::cur	Calculate offset from the current pointer position

Example:

#include <iostream>
#include <fstream>
#include <string>
using namespace std;
int main() {
    // Write to file
    ofstream outFile("./output.txt");
    if (outFile.is_open()) {
        outFile << "Hello, C++ World!" << endl;
        outFile.close();
    } else {
        cout << "Failed to open file for writing" << endl;
    }
    // Read from file
    string line;
    ifstream inFile("./output.txt");
    if (inFile.is_open()) {
        while (getline(inFile, line)) {
            cout << line << endl;
        }
        inFile.close();
    } else {
        cout << "Failed to open file for reading" << endl;
    }
    return 0;
}

C++ Memory Management

C/C++ memory is divided into 6 regions:

1. Kernel space: Stores kernel code and environment variables
2. Stack: Stores non-static local variables, function parameters, return values, grows downward
3. Memory mapped segment: Efficient I/O mapping for shared dynamic libraries, used for shared memory and inter-process communication
4. Heap: Used for dynamic memory allocation at runtime, grows upward
5. Data segment: Stores global and static data
6. Code segment: Stores executable code and read-only constants

new and delete

For built-in types, new/delete behave almost the same as malloc/free. For custom types, there is a key difference:

• new allocates memory + calls the constructor to initialize the object; delete calls the destructor to clean up + frees memory
• malloc only allocates memory; free only frees memory

Example:

#include <iostream>
using namespace std;
int main()
{
    // Built-in type examples
    // Allocate single int
    int *p1 = (int*)malloc(sizeof(int));
    free(p1);
 
    int *p2 = new int; // int *p2 = new int(10); allocates and initializes to 10
    delete p2;
	
    // Allocate array of 5 ints
    int *p3 = (int*)malloc(sizeof(int) * 10);
    free(p3);
 
    int *p4 = new int[5]; // new throws exception on allocation failure
    // C++11 allows: int *p4 = new int[5]{1,2,3,4}; to initialize array elements
    delete[] p4; // Always use [] for array delete with new, otherwise undefined behavior for custom types
	
	return 0;
}

Memory Leak

A memory leak occurs when you lose the pointer reference to allocated memory but never free it. It causes wasted memory and degraded program performance.

STL Common Containers

Common Container Methods

Method	Purpose
push_back(5)	Add element 5 to the end of the container
pop_back()	Remove the last element from the container
push_front(-1)	Add element -1 to the front of the container
pop_front()	Remove the first element from the container
size()	Return the number of elements in the container
resize(5)	Resize container to hold 5 elements, delete extra if smaller than original size, not supported by array
resize(5, 0)	Resize to 5 elements, initialize new elements to 0 if larger, not supported by array
empty()	Check if container is empty
clear()	Remove all elements from the container
front()	Return reference to the first element
back()	Return reference to the last element
at(2)	Return element at index 2 (0-based), throws exception if out of bounds
erase(container.begin() + 1)	Delete element at specified position
remove(8)	Delete all elements with value 8 (only for list)
insert(container.begin() + 1, 5)	Insert 5 before the position at index 1
fill_n(container.begin(), 5, 4)	Fill 5 positions with value 4
a.swap(b)	Swap contents of containers a and b
auto it = container.begin()	Returns iterator pointing to first element, use *it to get value
auto it = container.end()	Returns iterator pointing to one past the last element
rbegin()	Returns reverse iterator pointing to the end of the container (start of reverse traversal)
rend()	Returns reverse iterator pointing to one past the start of the container (end of reverse traversal)

Iterator Categories

1. Unidirectional: For forward_list, unordered_set/unordered_map, only support increment ++
2. Bidirectional: For list, set/map, support ++ and --
3. Random access: For string, vector, deque, underlying is contiguous array, support ++, --, +, - arbitrary offset

Vector (Dynamic Array)

#include <vector>
#include <iostream>
using namespace std;
int main(){
    vector<int> v1; // Empty dynamic int array
    vector<float> v2(3); // Initialize with 3 default-constructed elements
    vector<char> v3(3, 'a'); // Initialize with 3 'a' characters
    vector<char> v4(v3); // Copy all elements from v3 to v4
    return 0;
}

Usage example:

#include <vector>
#include <iostream> 
#include <algorithm>
using namespace std;
bool compareDesc(int a, int b){
	return a > b; // Sort from largest to smallest
}
void printVector(vector<int> vec){
    for(size_t i = 0; i < vec.size(); i++){
		cout << vec[i] << ' ';
	}
	cout << endl;
}
int main(){
	vector<int> nums;
    nums.push_back(1);
	nums.push_back(2);
	nums.push_back(3);
	nums.push_back(4);
	nums.push_back(5);
	sort(nums.begin(), nums.end(), compareDesc);
	printVector(nums); // Output 5 4 3 2 1
    vector<int>::iterator it = nums.begin();
    cout << *it << endl; // Output 5
	return 0;
}

Algorithm Library Common Functions

Function	Purpose
sort(begin, end, comparator)	Sort elements, default ascending order
auto it = find(begin, end, value)	Find first occurrence of value, returns iterator to it
int sum = accumulate(begin, end, init)	Sum all elements, add initial value init
string res = accumulate(begin, end, string(""))	Concatenate all elements into a single string starting from empty string
copy(v1.begin(), v1.end(), v2.begin())	Copy elements from v1 to v2
random_shuffle(begin, end)	Shuffle elements randomly, need to seed with srand((unsigned int)time(NULL)) first
transform(a.begin(), a.end(), b.begin(), func)	Apply func to each element of a, store result in b
reverse(begin, end)	Reverse order of elements in container
auto it = unique(begin, end)	Remove consecutive duplicate elements, returns iterator to end of unique region
int count = count(begin, end, value)	Return number of elements equal to value
replace(begin, end, old_val, new_val)	Replace all occurrences of old_val with new_val
for_each(begin, end, func)	Apply func to every element in container

Example:

#include <vector>
#include <iostream> 
#include <algorithm>
using namespace std;
int square(const int &a){
	return a * a;
}
void printVector(vector<char> &vec){
    size_t i;
	for(i = 0; i < vec.size(); i++){
		cout << vec.at(i) << ' ';
	}
	cout << endl;
}
int main(){
	vector<int> nums, squared;
	for(int i = 1; i < 6; i++){
        nums.push_back(i);
    }
	auto it = find(nums.begin(), nums.end(), 1);
	if(it != nums.end()){
		cout << "Found at index: " << (it - nums.begin()) << endl; // Found at 0
	}else{
		cout << "Not found" << endl;
	}
    
	squared.resize(nums.size());
	transform(nums.begin(), nums.end(), squared.begin(), square);
	
    vector<char> chars(5, 'x');
	printVector(chars);
	return 0;
}

Set operations for sorted ranges:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
void printVector(vector<int> vec) {
    for (auto num : vec) {
        cout << num << " ";
    }
    cout << endl;
}
int main() {
    vector<int> s1 = { 1,2,3,5,7,9 };
    vector<int> s2 = { 2,4,6,8,10,1 };
    sort(s1.begin(), s1.end());
    sort(s2.begin(), s2.end());

    vector<int> intersection(min(s1.size(), s2.size()));
    auto endIt = set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), intersection.begin());
    intersection.erase(endIt, intersection.end());

    vector<int> unionSet(s1.size() + s2.size());
    endIt = set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), unionSet.begin());
    unionSet.erase(endIt, unionSet.end());

    vector<int> difference(max(s1.size(), s2.size()));
    endIt = set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), difference.begin());
    difference.erase(endIt, difference.end());

    printVector(intersection);
    printVector(unionSet);
    printVector(difference);
    return 0;
}

Deque (Double-Ended Queue)

#include <deque>
using namespace std;
deque<int> dq1;
deque<int> dq2 = {1,2,3};
deque<int> dq3(5); // Size 5
fill_n(dq3.begin(), 5, 10); // Fill all 5 positions with 10
deque<int> dq4(10, 6); // 10 elements of 6
vector<int> tmp(5, 3);
deque<int> dq5(tmp.begin(), tmp.end());

List (Doubly Linked List)

List is a linear doubly linked list, supports fast insert/delete anywhere, but slow random access and does not support [] operator:

#include <list>
using namespace std;
list<int> l1;
list<int> l2(4, 100);
list<int> l3(l2.begin(), l2.end());
list<int> l4(l3);

l1.merge(l2); // Merge sorted l2 into sorted l1, both must be sorted before call

Array (Fixed-Size Array)

Array has a fixed compile-time size, does not support resize():

#include <array>
using namespace std;
array<int, 6> arr;
fill(arr.begin(), arr.end(), 0);
cout << *arr.data(); // Get pointer to first element
array<int, 4> arr2 = {1,2,3,4}; 
array<int, 4> arr3 = arr2; // Both arrays must have same size to copy

Set

Set stores unique ordered elements, underlying implementation is a red-black tree with O(log n) lookup:

1. Elements are unique and cannot be modified after insertion
2. Default ordered ascending by value

pair is a template utility for storing two values:

#include <utility>
#include <iostream>
int main() {
    std::pair<int, double> myPair(1, 3.14);
    std::pair<int,double> p = std::make_pair(9, 5.5);
    std::cout << "First element: " << myPair.first << '\n';
    std::cout << "Second element: " << myPair.second << '\n';
    return 0;
}

Set example:

#include <utility>
#include <iostream>
#include <set>
#include <functional>
using namespace std;
struct CompareGreater {
    bool operator()(int a, int b) const{
        return a > b;
    }
};
int main() {
    set<int> s1;
    pair<set<int>::iterator, bool> res = s1.insert(6);
    cout << *res.first << endl; // Output 6, res.second is true if insert succeeded

    set<int> s2 = { 1,2,3,4,5,6 }; // Default ascending
    s2.erase(3); // Delete element 3
    s2.erase(s2.begin(), s2.end()); // Delete all elements in [begin, end)
    cout << s2.empty() << endl; // Output 1 (true)

    set<int, CompareGreater> s4 = {1,2,3,4,5,6}; // Sort descending
    // Can also use set<int, greater<int>> s4 for built-in comparator
    for (int num : s4) {
        cout << num; // Output 654321
    }
    return 0;
}

Map (Key-Value Mapping)

Map stores ordered key-value pairs with unique keys, underlying is red-black tree:

#include <map>
#include <string>
#include <iostream>
using namespace std;
int main() {
    map<string, int> countMap;
    countMap.insert(pair<string, int>("apple", 3));
    countMap["left"]; // Insert key "left" with default value 0
    countMap["right"] = 2; // Insert if not exists, update if exists
    int val = countMap["apple"]; // val = 3

    string fruits[] = { "watermelon", "watermelon", "apple", "watermelon", "apple", "apple", "watermelon", "apple", "banana", "apple", "banana", "pear" };
    for (string &fruit : fruits) {
        countMap[fruit]++;
    }
    for (pair<string, int> entry : countMap) {
        cout << entry.first << ": " << entry.second << endl;
    }
    return 0;
}

STL Functors

Functors that return bool are called predicates; binary predicates accept two parameters.

Arithmetic Functors

• plus<T>: addition
• minus<T>: subtraction
• multiplies<T>: multiplication
• divides<T>: division
• modulus<T>: modulus
• negate<T>: negation

Example:

#include <iostream>
#include <functional>
using namespace std;

void calculate(int a, int b){
    minus<int> subtract;
    cout << "Result: " << subtract(a, b) << endl;
}
int main(){
    calculate(50, 40); // Output 10
    return 0;
}

Relational Functors

• equal_to<T>: equal
• not_equal_to<T>: not equal
• greater<T>: greater than
• greater_equal<T>: greater or equal
• less<T>: less than
• less_equal<T>: less or equal

Example:

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

int main() {
    vector<int> nums;
    for (int i = 0; i < 5; i++) {
        nums.push_back(i);
    }
    sort(nums.begin(), nums.end(), greater<int>());
    for (vector<int>::iterator it = nums.begin(); it != nums.end(); it++) {
        cout << *it << "\t";
    }
    cout << endl;
    return 0;
}

Logical Functors

• logical_and<T>: logical AND
• logical_or<T>: logical OR
• logical_not<T>: logical NOT

Example:

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

int main() {
    vector<bool> input, output;
    for (int i = 0; i < 8; i++) {
        input.push_back(bool(i % 2));
    }
    output.resize(input.size());
    transform(input.begin(), input.end(), output.begin(), logical_not<bool>());
    for (vector<bool>::iterator it = output.begin(); it != output.end(); it++) {
        cout << *it << "\t";
    }
    cout << endl;
    return 0;
}