C++

---

Timeline

Timeline

2025-10-03

init

2025-10-12

add next_permutation to generate all permutations of a sequence

2025-10-19

add string

This article introduces the core fundamentals of the C++ programming language, including the concepts of lvalues and rvalues, reference types (lvalue references and rvalue references) and their application scenarios. It details standard input/output methods, such as the usage rules of cin, the getline() function for reading strings containing spaces, and the basic usage of output functions. It also explains the functions and common operations of the three classes in the sstream header file (stringstream, istringstream, ostringstream), including techniques such as string splitting, number parsing, and concatenation. In addition, the article summarizes the usage of common containers in the STL (Standard Template Library): vector supports random access, dynamic expansion, and multiple traversal methods, and gives the time complexity of each operation; queue provides FIFO queue operations, all with O(1) complexity; priority_queue implements a max heap by default, supports custom comparators to construct a min heap, and introduces advanced techniques such as lazy deletion. The overall content is aimed at C++ beginners, covering syntax essentials, input/output handling, and STL container practice, helping readers quickly master common functions and precautions.

---

Syntax

& and &&, lvalues and rvalues

• Lvalue

  • Has a name and can take its address.

  • Can appear on the left side of an assignment operator.

  • Example:

    int x = 5; // x is an lvalue
    x = 10;    // Can be assigned
    int* p = &x; // Can take address

• Rvalue

  • Temporary objects or literals, no name, cannot take address.

  • Usually appears on the right side of an assignment operator.

  • Example:

    int y = x + 2; // x+2 is an rvalue
    int z = 42;    // 42 is an rvalue

  Note: rvalues can be bound to rvalue references (&&)。

• Reference types

Reference	meaning
T&	Lvalue reference (can only bind to lvalues)
T&&	Rvalue reference (can only bind to rvalues)

Example:

int a = 5;
int &lref = a;   // Lvalue reference, a is an lvalue
int &&rref = 5;  // Rvalue reference, 5 is an rvalue

• Lvalue references can modify lvalues:

lref = 10; // a = 10

• Rvalue references are often used for move semantics:

vector<int> v1 = {1,2,3};
vector<int> v2 = std::move(v1); // Rvalue references allow moving resources

Input/Output

Input

First, in C++ language, to use standard input, you need to include the header file.

• cin

cin is the standard input stream object in C++. Below are two uses of cin: reading individually and reading in batches. The principle of cin, simply put, is that there is a buffer. Data entered from the keyboard is first stored in the buffer, and cin can be used to read data from the buffer.

Note 1: cin can continuously read data from the keyboard.

Note 2: cin uses spaces, tabs, and newline characters as delimiters.

Note 3: cin starts reading from the first non-space character and stops reading when it encounters a delimiter.

• getline()

istream& getline (char* s, streamsize n );
istream& getline (char* s, streamsize n, char delim );

From the notes on cin, it can also be seen that when the string we need to read contains spaces in the middle, cin will not read the entire string. In this case, the getline() function can be used to solve the problem.

Note 1: When using the getline() function, you need to include the header file.<string>

Note 2: The getline() function reads a line, the read string includes spaces, and ends when a newline character is encountered.

• getchar()

This function reads a character from the buffer and is often used to determine whether there is a line break.

output

Similarly, in C++ language, to use standard output, you also need to include the header file.<iostream>

On the output side, we mainly introduce one function, which is the most used.coutNote that if outputendlwhen outputting an object, a newline character will be output, similar to\n。

sstream

Include header file

#include <sstream>
using std::stringstream;
using std::istringstream;
using std::ostringstream;

Three classes

Class name	Function	Scenario
stringstream	Supports both read and write	General
istringstream	Read-only input stream	Parse strings
ostringstream	Write-only output stream	Construct strings

Common operations:

function	Function	example
str()	Get/Set internal string	ss.str("123 456")
clear()	Clear stream state	Must be called when reusing
operator>>	Extract data (split by whitespace)	ss >> x;
operator<<	Insert data	ss << 42;
getline()	Read line by line	getline(ss, s)
good()fail()	Check stream state	Determine if parsing succeeded

Note: must call clear when reusing

Example:

Split string

#include <sstream>
using std::stringstream;

string s = "apple banana orange";
stringstream ss(s);
string word;
while (ss >> word) {
    cout << word << endl;
}

Purpose	Method	example	Description	Common pitfalls
Whitespace tokenization	ss >> word	ss >> w1 >> w2	Split by spaces, newlines, and tabs	Does not split on non-whitespace characters such as commas
Custom delimiter	getline(ss, word, ',')	getline(ss, word, ',');	In,Split	must usegetline，>>Cannot customize delimiter
Parse numbers	ss >> num	int x; ss >> x;	String numbers → int/double	Non-numeric input fails the stream; must checkss.fail()
Concatenate strings	oss << val	oss << "ID=" << 5;	Efficiently construct dynamic strings	After output endsoss.str()Only then can the complete content be obtained

STL

vector

Include header file

#include <vector>
using std::vector;

Construct

// Empty vector
vector<int> v1;

// Specify size, default initialized to 0
vector<int> v2(5);  // 5 elements, each 0

// Specify size and initial value
vector<int> v3(5, 42);  // 5 elements, each 42

// Via initializer_list
vector<int> v4 = {1, 2, 3, 4};

// Copy another vector
vector<int> v5(v4);

// Construct from array
int arr[] = {10, 20, 30};
vector<int> v6(arr, arr + 3);

Access element

• Returns a reference to the element

• Access with bounds checking; throws if out of range std::out_of_range exception

// Access by index (no bounds checking)
int a = v[0];

// Access via at() (with bounds checking)
int b = v.at(1);

// Access first and last elements
int first = v.front();
int last = v.back();

Modify elements

v[2] = 10;     // Modify the value at index 2
v.push_back(5); // Insert element at the end
v.pop_back();   // Remove element at the end
v.insert(v.begin() + 1, 20); // Insert 20 at index 1
v.erase(v.begin() + 2);      // Erase the element at index 2
v.clear();                   // Clear all elements

Iterate over elements

// Index iteration
for (size_t i = 0; i < v.size(); ++i)
    std::cout << v[i] << " ";

// Iterator iteration
for (auto it = v.begin(); it != v.end(); ++it)
    std::cout << *it << " ";

// Range-based for (C++11+)
for (auto &x : v)
    std::cout << x << " ";

Time complexity

Operation	Time complexity	Description
v[i]	O(1)	Random access
v.at(i)	O(1)	Random access with bounds checking
push_back(x)	O(1) amortized	Average constant time, occasional O(n) expansion
pop_back()	O(1)	Remove element at the end
insert(v.begin() + i, x)	O(n)	Inserting in the middle, moving n/2 elements on average
erase(v.begin() + i)	O(n)	Deleting an element in the middle, moving n/2 elements on average
front()/back()	O(1)	Access first and last elements
size()/empty()	O(1)	Get size / check if empty
clear()	O(n)	Clear elements (calls destructors)
sort(v.begin(), v.end())	O(n log n)	Sort using STL algorithms

queue

Include header file

#include <queue>
using std::queue;

Construct

// Empty queue
queue<int> q1;

// Copy constructor
queue<int> q2(q1);

Access front and back of queue

// View front/back element
int front_val = q.front();
int back_val  = q.back();

Enqueue and dequeue

// Enqueue (insert at back)
q.push(10);
q.push(20);

// Dequeue (remove from front)
q.pop();

Time complexity

Operation	Time complexity
push()	O(1)
pop()	O(1)
front()	O(1)
back()	O(1)
empty()	O(1)
size()	O(1)

priority_queue

• Priority queue, internally uses a max heap by default

• When dequeuing, always pops the element in the queue that is largest element(default max heap).

• Custom comparator can be implemented. Min-heap。

priority_queue has no iterators; you can only traverse it using pop() and top().

Include header file

#include <queue>
using std::priority_queue;

Construct

In the template parameters of priority_queue, the first is the type of stored elements, the second is the container for storing elements (defaults to vector), and the third is the comparator for elements.

Note that priority_queue only supports popping the top; it does not support directly modifying or deleting an element in the heap.

• If you want to delete a priority_element in the queue, consider whether you can use unordered_map implementationLazy deletion(Only delete when an invalid element reaches the top; otherwise, just mark it.)

// Default constructor
priority_queue<int> pq1;
// All parameters of the default constructor
priority_queue<int,vector<int>,std::less<int>> pq_full;
// Copy constructor
priority_queue<int> pq2(pq1);

// Construct from container
#include <vector>
std::vector<int> v = {1, 3, 2};
priority_queue<int> pq3(v.begin(), v.end()); // Default max-heap

Access the top of the heap

priority_queue<int> pq;
int top_val = pq.top(); // 20

Pop the top element

pq.pop();

Custom comparator

Method 1: Use std::greaterImplement a min-heap

priority_queue<int, vector<int>, std::greater<int>> min_pq;

Method 2: Custom struct/lambda

struct cmp {
    bool operator()(int a, int b) { return a > b; } // Minimum value first
};
priority_queue<int, vector<int>, cmp> pq_custom;

Method 3: If it is a struct, directly overload the < operator

struct Person {
    string name;
    int age;

    // Overload the < operator
    bool operator<(const Person& other) const {
        return age < other.age;  // Max heap by default, older age has higher priority.
    }
};

priority_queue<Person> pq;

Time complexity

Operation	Average complexity
push	O(log n)
pop	O(log n)
top	O(1)
size	O(1)
empty	O(1)

stack

Stack, first in last out

stackNo iterator, cannot useforLoop to traverse directly. Traversal can only be done throughtop()+pop()。

Include header file

#include <stack>
using std::stack;

Construct

stack<int> s1;          // Empty stack
stack<int> s2(s1);      // Copy constructor

Push/Pop

stack<int> s;
// Push (push to top of stack)
s.push(20);

// Pop (pop the top element)
s.pop();

Access the top element of the stack

// View the top element of the stack
int top_val = s.top();  // Top element of the stack

Time complexity

Operation	Average complexity
push	O(1)
pop	O(1)
top	O(1)
size	O(1)
empty	O(1)

map, unordered_map

• map

  • mapYes Ordered associative container, usually implemented with Red-black tree implementation.

  • Each element is key-value pair, key is unique, automatically sorted by key.

  • Suitable for needs access in key order scenarios.

• unordered_map

  • unordered_mapYes Hash table, unordered storage of key-value.
  • The average time complexity of search, insertion, and deletion is O(1).
  • Suitable for fast lookup,Order doesn’t matter。

  GCC’sunordered_mapSince C++11, there is an optimization:

  • When the linked list length in a bucket exceeds a certain threshold (usually 8), the linked list is converted to a red-black tree.。
  • This prevents the O(n) complexity caused by worst-case hash collisions, reducing the lookup complexity from O(n) to O(log n).
  • That is:linked list → red-black tree, rather than the entire hash table degenerating into a red-black tree.

Include header file

map

// map
#include <map>
using std::map;

unordered_map

// unordered_map
#include <unordered_map>
using std::unordered_map;

Construct

map

// empty map
map<int, string> m1;

// Copy constructor
map<int, string> m2(m1);

// Initializer list
map<int, string> m3 = {{1, "one"}, {2, "two"}};

unordered_map

// empty table
unordered_map<int, string> um1;

// Copy constructor
unordered_map<int, string> um2(um1);

// Initializer list
unordered_map<int, string> um3 = {{1,"one"}, {2,"two"}};

Access element

map

map<int, string> m;

// Access element
string s = m[1];       // The key must exist, otherwise a default value will be created.

unordered_map

unordered_map<int, string> um;

// Access element
string s = m[1];       // The key must exist, otherwise a default value will be created.

Insert, modify, and delete elements

map

map<int, string> m;

// Insert elements
m.insert({3, "three"});
m[1] = "one";     // Insert or modify
m[2] = "two";

unordered_map

unordered_map<int, string> um;

// Insert
um.insert({3, "three"});
um[1] = "one";
um[2] = "two";

Find elements

map

map<int, string> m;

bool hasKey = um.count(2); // 0 or 1

auto it = m.find(2);   // Returns an iterator, or m.end() if not found
bool hasKey = um.count(2); // 0 or 1

unordered_map

unordered_map<int, string> um;

auto it = um.find(2);  // Returns an iterator, or um.end() if not found
bool hasKey = um.count(2); // 0 or 1

Erase elements

map

map<int, string> m;

// Erase elements
m.erase(1);            // Erase by key
m.erase(m.begin());    // Erase by iterator

unordered_map

unordered_map<int, string> um;

// Delete
um.erase(1);
um.erase(um.begin());    // Erase by iterator

traverse

map

map is traversed in order of key

map<int, string> m;

for (auto &[key, value] : m) {
    cout << key << " -> " << value << endl;
}

unordered_map

Note:unordered_mapis unordered, traversal order is not fixed.

for (auto &[key, value] : um) {
    cout << key << " -> " << value << endl;
}

Custom comparator (only supported by map)

map<int, string, std::greater<int>> m; // Descending order by key

Time complexity

map

Operation	Average complexity
Insertion/Deletion	O(log n)
Lookup	O(log n)
traverse	O(n)
Access element	O(log n)

unordered_map

Operation	Average complexity	Worst-case complexity
Insert	O(1)	O(n)
Lookup	O(1)	O(n)
Delete	O(1)	O(n)
traverse	O(n)	O(n)

set, unordered_set

• set
  • setYes Ordered set, usually implemented with Red-black tree implementation.
  • Store Unique elements, automatically sorted by element value.
  • Suitable for needs ordered access and fast lookup of unique elements scenarios.
• unordered_set
  • unordered_setYes Hash table set, stores unique elements in no particular order.
  • Average search, insertion, and deletion complexity is O(1).
  • Suitable for fast lookup, order is not a concern.

    GCC’sunordered_setalso supports When the linked list length exceeds the threshold, the bucket is treeified., avoiding worst-case O(n).

Include header file

set

#include <set>
using std::set;

unordered_set

#include <unordered_set>
using std::unordered_set;

---

Construct

set

set<int> s1;               // empty set
set<int> s2(s1);           // Copy constructor
set<int> s3 = {1, 2, 3};   // Initializer list

unordered_set

unordered_set<int> us1;              // empty set
unordered_set<int> us2(us1);         // Copy constructor
unordered_set<int> us3 = {1, 2, 3};  // Initializer list

---

Insertion and modification

set

set<int> s;

s.insert(10);  // Insert elements
s.insert(20);
s.insert(10);  // Duplicate elements are not inserted.

unordered_set

unordered_set<int> us;

us.insert(10);
us.insert(20);
us.insert(10);  // Duplicate elements are not inserted.

---

Find elements

set

set<int> s = {1,2,3};

auto it = s.find(2);   // Returns an iterator; returns s.end() if not found.
bool exists = s.count(2); // Returns 0 or 1

unordered_set

unordered_set<int> us = {1,2,3};

auto it = us.find(2);   // Returns an iterator; returns us.end() if not found.
bool exists = us.count(2); // Returns 0 or 1

Erase elements

set

s.erase(2);        // Erase by element value
s.erase(s.begin()); // Erase by iterator

unordered_set

us.erase(2);
us.erase(us.begin());

traverse

set

Iterate in ascending order of elements

for (auto &val : s) {
    cout << val << " ";
}

unordered_set

Iteration order is not fixed

for (auto &val : us) {
    cout << val << " ";
}

Custom comparator (set only)

set<int, std::greater<int>> s; // Sorted in descending order

Time complexity

set

Operation	Average complexity
Insertion/Deletion	O(log n)
Lookup	O(log n)
traverse	O(n)

unordered_set

Operation	Average complexity	Worst-case complexity
Insert	O(1)	O(n)
Lookup	O(1)	O(n)
Delete	O(1)	O(n)
traverse	O(n)	O(n)

string

In the vast majority of modern C++ compilers (such as GCC/Clang/MSVC),std::stringThe implementation is similar to:

• Internally usesdynamic arrayto store characters
• automatically maintains the trailing null terminator'\0'(compatible with C-string)
• eachstringAlso maintainssizeandcapacity

String capacity growth usually followsexponential growth (e.g., doubling), to reduce repeated memory allocations.

Small String Optimization (SSO)

SSO isstd::stringthe core performance optimization technique.

Purpose: reduce heap memory allocations and speed up small string operations.

When the string length is short (usually ≤ 15 characters), many implementations willdirectly store it in a small buffer inside the object, without allocating heap memory.

string s = "hello";  // Likely no heap memory allocation (SSO)

Advantages:

• Avoid frequentnew/delete
• Improve performance
• Reduce memory fragmentation

Include header file

#include <string>
using std::string;

Construct

Construction methods	Prototype	Description	example
Default constructor	string()	Create empty string	string s1; // ""
Copy constructor	string(const string& str)	Copy existing string	string s2(s1);
Move construction	string(string&& str)	Move existing string (since C++11)	string s3(std::move(s1));
C string	string(const char* s)	From a\0C string ending with	string s4("hello");
C string + length	string(const char* s, size_t n)	Take only the first n characters	string s5("hello world", 5); // "hello"
Repeated character	string(size_t n, char c)	Create a string of n identical characters	string s6(4, 'a'); // "aaaa"
Range construction	template<class InputIt> string(InputIt first, InputIt last)	Initialize with iterator range	vector<char> v{'x','y','z'}; string s7(v.begin(), v.end());
initializer_list	string(std::initializer_list<char> ilist)	Initialize with list of characters (C++11)	string s8({'a','b','c'}); // "abc"

Default constructor

string s1;
cout << s1.size(); // 0

• Common pitfalls: of an empty stringc_str()still valid, returns""。

---

Copy constructor

string s2("hello");
string s3(s2);
cout << s3; // "hello"

• Performance suggestions: for large strings, prefer to useconst string&pass by reference to avoid copying

---

Move construction (C++11+)

string s4(std::move(s2));

• Features：s2the contents are moved, and the original object is empty
• Advantages: avoids copying memory and improves performance

---

C string construction

string s5("hello");
string s6("hello world", 5); // "hello"

• Use case: initialize from a string literal or C-style array
• Performance suggestions: if the length is known, use the second parameter to avoid unnecessary scanning
• Common pitfalls: passing a non-\0terminated string, you must specify the length

---

Repeated character construction

string s7(5, 'x'); // "xxxxx"

---

Range construction (iterators)

vector<char> v{'a','b','c'};
string s8(v.begin(), v.end()); // "abc"

---

initializer_list construction (C++11+)

string s9({'x','y','z'}); // "xyz"

Access and assignment operations

Subscript accessoperator[]

string s = "hello";
char c = s[1]; // 'e'
s[0] = 'H';    // "Hello"

• Description：

  • No bounds checking is performed; out-of-bounds access leads to undefined behavior.

  • After move construction or reallocation, pointers or references to the original characters may be invalidated.

Safe accessat()

char c = s.at(1); // 'e'
s.at(0) = 'H';    // "Hello"

• Description：
  • performs bounds checking and throws when out of boundsstd::out_of_rangeException.

---

Accessing first and last characters

char f = s.front(); // 'H'
char b = s.back();  // 'o'

s.front() = 'h';
s.back()  = '!';    // "hello!"

• Description：
  • Calling when the string is emptyfront()orback()is undefined behavior.
• Common pitfalls：
  • Accessing an empty string triggers UB (undefined behavior).

---

String assignment: assign()

assign()Yesstd::stringA multi-purpose assignment function with rich overloads:

Prototype	Description	example
string& assign(const string& str)	Copy another string	s.assign(s2);
string& assign(string&& str)	Move another string	s.assign(std::move(s2));
string& assign(const string& str, size_t pos, size_t count)	Assign from a substring of str	s.assign(s2, 1, 3); // take s2[1..3]
string& assign(const char* s)	C string assignment	s.assign("world");
string& assign(const char* s, size_t n)	Assign the first n characters	s.assign("hello world", 5); // "hello"
string& assign(size_t n, char c)	Assign repeated characters	s.assign(4, 'x'); // "xxxx"
template<class InputIt> string& assign(InputIt first, InputIt last)	Range assignment	vector<char> v{'a','b'}; s.assign(v.begin(), v.end());
string& assign(initializer_list<char> il)	List assignment (C++11+)	s.assign({'x','y','z'}); // "xyz"

Modification operations

Append: append()

Prototype	Description	example
string& append(const string& str)	Append an entire string	s.append(s2);
string& append(const string& str, size_t pos, size_t count)	Append a substring of str	s.append(s2, 1, 3);
string& append(const char* s)	Append a C string	s.append("world");
string& append(const char* s, size_t n)	Append the first n characters of a C string	s.append("hello world", 5); // "hello"
string& append(size_t n, char c)	Append n identical characters	s.append(3, '!'); // "!!!"
template<class InputIt> string& append(InputIt first, InputIt last)	Append a range	vector<char> v{'a','b'}; s.append(v.begin(), v.end());
string& push_back(char c)	Append a single character	s.push_back('x');

Performance suggestions

Optimize concatenation operations — default concatenation is inefficient

string s;
s.reserve(1000);  // Reserve space in advance to reduce reallocations

• When modifying frequently, it is recommended to usestd::ostringstreamorstd::string_view

Insert

Prototype	Description	example
string& insert(size_t pos, const string& str)	Insert an entire string at pos	s.insert(2, s2);
string& insert(size_t pos, const string& str, size_t subpos, size_t count)	Insert a substring of str	s.insert(1, s2, 0, 2);
string& insert(size_t pos, const char* s)	Insert a C string	s.insert(0, "Hi");
string& insert(size_t pos, const char* s, size_t n)	Insert the first n characters of a C string	s.insert(0, "Hello World", 5);
string& insert(size_t pos, size_t n, char c)	Insert n copies of a character	s.insert(3, 4, '*');
iterator insert(const_iterator p, char c)	Insert a single character	s.insert(s.begin()+1, 'x');
template<class InputIt> void insert(const_iterator p, InputIt first, InputIt last)	Insert Interval	s.insert(s.begin(), v.begin(), v.end());

Erase

Prototype	Description	example
string& erase(size_t pos = 0, size_t count = npos)	Erase count characters starting from pos	s.erase(2,3);
iterator erase(const_iterator p)	Erase the character pointed to by the iterator	s.erase(s.begin()+1);
iterator erase(const_iterator first, const_iterator last)	Erase a range	s.erase(s.begin(), s.begin()+3);

Replace

Prototype	Description	example
string& replace(size_t pos, size_t count, const string& str)	Replace count characters starting at pos with str	s.replace(0,2,"Hi");
string& replace(size_t pos, size_t count, const string& str, size_t subpos, size_t subcount)	Replace with a substring of str	s.replace(0,2,s2,1,2);
string& replace(size_t pos, size_t count, const char* s)	Replace with a C string	s.replace(0,2,"OK");
string& replace(size_t pos, size_t count, const char* s, size_t n)	Replace with the first n characters of a C string	s.replace(0,2,"Hello World",5);
string& replace(size_t pos, size_t count, size_t n, char c)	Replace with n copies of a character	s.replace(0,2,3,'*');
iterator replace(const_iterator first, const_iterator last, InputIt first2, InputIt last2)	Replace an iterator range	s.replace(s.begin(), s.begin()+2,v.begin(),v.end());

Find operations

Function prototype	Description	example
size_t find(const string& str, size_t pos=0) const	Find the first occurrence of a substring starting from pos	s.find("world"); // 6
size_t find(const char* s, size_t pos=0) const	Find C string starting from pos	s.find("lo"); // 3
size_t find(const char* s, size_t pos, size_t n) const	Find the first n characters of the C string	s.find("hello world", 0, 5); // find "hello"
size_t find(char c, size_t pos=0) const	Find first occurrence of character	s.find('o'); // 4
size_t rfind(const string& str, size_t pos=npos) const	Find substring from right to left	s.rfind("lo");
size_t rfind(char c, size_t pos=npos) const	Find character from right to left	s.rfind('o');
size_t find_first_of(const string& chars, size_t pos=0) const	Find first occurrence of any character in the specified set	s.find_first_of("aeiou");
size_t find_last_of(const string& chars, size_t pos=npos) const	Find last occurrence of any character in the specified set	s.find_last_of("aeiou");
size_t find_first_not_of(const string& chars, size_t pos=0) const	Find the first position not in the character set	s.find_first_not_of("aeiou");
size_t find_last_not_of(const string& chars, size_t pos=npos) const	Find the last position not in the character set	s.find_last_not_of("aeiou");

String comparison

Function prototype	Description	example	Performance
int compare(const string& str) const	Compare the entire string with str	s.compare("hello");	O(min(n, m))
int compare(size_t pos, size_t count, const string& str) const	Compare substrings[pos, pos+count)with str	s.compare(0,2,"he");	O(count)
int compare(size_t pos, size_t count, const string& str, size_t subpos, size_t subcount) const	Compare substring of s with substring of str	s.compare(0,2,s2,1,2);	O(subcount)
int compare(const char* s) const	Compare with C string	s.compare("hello");	O(n)
int compare(size_t pos, size_t count, const char* s) const	Compare substring with C string	s.compare(0,2,"he");	O(count)
int compare(size_t pos, size_t count, const char* s, size_t n) const	Compare substring with first n characters of C string	s.compare(0,2,"hello",2); // "he"	O(n)

Return value:

• Return value < 0 → s < str
• Return value = 0 → s == str
• Return value > 0 → s > str

You can also use operators to compare

operator	Function	example	Return type	Comparison method
==	Determine whether they are equal	s == "hello"	bool	Case-sensitive & character-by-character comparison
!=	Check if not equal	s != t	bool	same as above
<	Lexicographically less than	"abc" < "abd"	bool	Compare by ASCII/Unicode
<=	Less than or equal to	"abc" <= "abc"	bool	same as above
>	Lexicographically greater than	"dog" > "cat"	bool	same as above
>=	Greater than or equal to	"hi" >= "ha"	bool	same as above

Substring

Function prototype	Description	example	Return value	Note	Performance
string substr(size_t pos = 0, size_t count = npos) const	From positionposstart, extract a substring of lengthcountsubstring	s.substr(2, 4)	Returns a new string	pos > size()Throws an exception	Creates a new string copy; be mindful of performance

Character checking and case conversion

Requires including the C standard library

#include <cctype>

Common character checking functions

function	Function	example
isalnum(c)	Whether it is a letter or digit	'A','z','3'
isalpha(c)	Whether it is a letter	'A','b'
isdigit(c)	Whether it is a digit	'0'~'9'
islower(c)	Whether it is a lowercase letter	'a'
isupper(c)	Whether it is an uppercase letter	'Z'
isspace(c)	Whether it is a whitespace character (space/newline/tab)	' ','\n','\t'
ispunct(c)	Whether it is a punctuation character	',' '.' '!'
isxdigit(c)	Whether it is a hexadecimal digit	'0'~'9','a'~'f'
isprint(c)	Whether it is a printable character	ordinary character
iscntrl(c)	whether it is a control character	'\n' '\r'

case conversion functions

function	Description	example
tolower(c)	convert character to lowercase	tolower('A') → 'a'
toupper(c)	convert character to uppercase	toupper('b') → 'B'

these two functionsonly operate on a single character, to process strings, you need to combine withtransform()：

#include <algorithm>
#include <cctype>
using std::string;

int main(){
    string s = "HeLLo";
	std::transform(s.begin(), s.end(), s.begin(), ::tolower);  // s = "hello"

}

::tolowerin::refers toGlobal scope operator, indicating that the<cctype>the global defined intolowerfunction, to avoid confusion with<locale>instd::tolowerconfusion with (the overloaded version that takes a locale parameter).

conversion between strings and numbers

string to integer conversion function table

function	Function prototype	Parameter description	return value description	example
stoi	int stoi(const string& str, size_t* pos = 0, int base = 10);	str: input stringpos: returns the number of characters successfully convertedbase: base (2~36)	convertedint	stoi("123") → 123stoi("1A", nullptr, 16) → 26
stol	long stol(const string& str, size_t* pos = 0, int base = 10);	same as above	is converted tolong	stol("99999") → 99999L
stoll	long long stoll(const string& str, size_t* pos = 0, int base = 10);	same as above	is converted tolong long	stoll("1234567890123")

---

string to floating-point conversion function table

function	Function prototype	Parameter description	return value description	example
stof	float stof(const string& str, size_t* pos = 0);	str: stringpos: returns the length of parsed characters	converted tofloat	stof("3.14") → 3.14f
stod	double stod(const string& str, size_t* pos = 0);	same as above	converted todouble	stod("2.71828")
stold	long double stold(const string& str, size_t* pos = 0);	same as above	converted tolong double	stold("1.6180339887")

---

number to string conversion (to_string)

function	Function prototype	Parameter description	return value description	example
to_string	string to_string(int value);	value: number	Returns the converted string	to_string(42) → "42"
to_string	string to_string(double value);	same as above	Float to string	to_string(3.14) → "3.140000"
to_string	string to_string(long long value);	same as above	Supports long integers	to_string(1234567890123)

---

Return values and exception summary

Case	behavior
Input is not a number	Throwsstd::invalid_argument
Number out of range	Throwsstd::out_of_range
Automatically removes leading spaces	✅ Supported" 123"
Supports signs	✅"-42"" +88"
Supports partial parsing	✅"123abc"→ 123

Strings and streams

Include header file

#include <sstream>
using std::stringstream;
using std::istringstream;
using std::ostringstream;

Three classes

Class name	Function	Scenario
stringstream	Supports both read and write	General
istringstream	Read-only input stream	Parse strings
ostringstream	Write-only output stream	Construct strings

Common operations:

function	Function	example
str()	Get/Set internal string	ss.str("123 456")
clear()	Clear stream state	Must be called when reusing
operator>>	Extract data (split by whitespace)	ss >> x;
operator<<	Insert data	ss << 42;
getline()	Read line by line	getline(ss, s)
good()fail()	Check stream state	Determine if parsing succeeded

Note: must call clear when reusing

Example:

Split string

#include <sstream>
using std::stringstream;


string s = "apple banana orange";
stringstream ss(s);
string word;
while (ss >> word) {
    cout << word << endl;
}

Purpose	Method	example	Description	Common pitfalls
Whitespace tokenization	ss >> word	ss >> w1 >> w2	Split by spaces, newlines, and tabs	Does not split on non-whitespace characters such as commas
Custom delimiter	getline(ss, word, ',')	getline(ss, word, ',');	In,Split	must usegetline，>>Cannot customize delimiter
Parse numbers	ss >> num	int x; ss >> x;	String numbers → int/double	Non-numeric input fails the stream; must checkss.fail()
Concatenate strings	oss << val	oss << "ID=" << 5;	Efficiently construct dynamic strings	After output endsoss.str()Only then can the complete content be obtained

multiset/multimap

multiset

• Element Allows duplicates, automatically sorted by key
• Underlying usually uses Red-black tree
• Does not support subscript access, only iterators
• Suitable for needs Fast lookup and sequential traversal of duplicate elements

multimap<K,V>

• key Allows duplicates, sorted by key
• Underlying usually uses Red-black tree
• Can pass throughequal_rangeFind all elements with a given key

Include header file

// multiset
#include <set>
using std::multiset;

// multimap
#include <map>
using std::multimap;

Construct

multiset

multiset<int> ms;            // Empty multiset
multiset<int> ms2(ms);        // Copy constructor
multiset<int> ms3 = {1,2,2,3}; // Initializer list

multimap

multimap<int,string> mm;            // Empty multimap
multimap<int,string> mm2(mm);       // Copy constructor
multimap<int,string> mm3 = {{1,"a"},{2,"b"},{2,"c"}}; // Initializer list

Insert elements

// multiset
ms.insert(2);
ms.insert(2); // Duplicates allowed

// multimap
mm.insert({2,"b"});
mm.insert({2,"c"}); // Keys can be repeated

Find elements

// multiset
auto it = ms.find(2);       // Returns an iterator to the first 2
size_t cnt = ms.count(2);   // Number of occurrences of 2

// multimap
auto range = mm.equal_range(2); // Returns the range of elements with key=2 [first, second)
for(auto it = range.first; it != range.second; ++it) {
    cout << it->first << " -> " << it->second << endl;
}

Erase elements

// multiset
ms.erase(2);          // Remove all elements with value 2
auto it = ms.find(2);
ms.erase(it);         // Remove the element pointed to by a single iterator

// multimap
mm.erase(2);          // Remove all elements with key=2
auto it2 = mm.find(2);
mm.erase(it2);        // Remove the element pointed to by a single iterator

traverse

// multiset
for(auto &x : ms) {
    cout << x << " ";
}
cout << endl;

// multimap
for(auto &[key,value] : mm) {
    cout << key << " -> " << value << endl;
}

Time complexity

Operation	multiset / multimap
Insert	O(log n)
Lookup	O(log n)
Delete	O(log n)
traverse	O(n)

tuple

Include header file

#include <tuple>
using std::tuple;

Construct

tuple<int,int,int> tp ={1,2,3};

auto tp2 = std::make_tuple(1, 2.5, "hi"); // Automatic type deduction

Access element

• Cannot access like pair, use std::get<0>(tuple)

  Note, here getRequires index to be a constant, a compile-time constant, so it cannot be used to iterate

int a = std::get<0>(tp);
int b = std::get<1>(tp);
int c = std::get<2>(tp);

• Since C++17, structured bindings can be used, which is more elegant

auto [a, b, c] = tp;

• You can also use std::tie

int a, b, c;
std::tie(a, b, std::ignore) = tp;

Modify

std::get<1>(tp) = 6;

Get length

// tuple length
constexpr size_t n = std::tuple_size<decltype(tp)>::value; // n=3

traverse

Not commonly used, use structured bindings + fold expressions

auto tp = make_tuple(1, 2.5, "hi");

// Fold expression traversal
std::apply([](auto&&... args) {
    ((cout << args << " "), ...);
}, tp);

algorithm

Include header file

#include <algorithm>

sort

Basic usage

#include <functional> // std::greater<int>
vector<int> v={3,2,4};
// Sort in non-decreasing order (ascending)
std::sort(v.begin(), v.end());
// Sort in non-increasing order (descending)
std::sort(v.begin(), v.end(),std::greater<int>)

Custom comparator

struct Person {
    string name;
    int age;
};

vector<Person> people = {{"Alice", 25}, {"Bob", 30}, {"Carol", 20}};

// Sort by age ascending
std::sort(people.begin(), people.end(), [](const Person &a, const Person &b){
    return a.age < b.age;
});

// Sort by age descending
std::sort(people.begin(), people.end(), [](const Person &a, const Person &b){
    return a.age > b.age;
});

std::sort does not guarantee stability; if you need a stable sort, use std::stable_sort

• Stable sort: If two elements are equal, their relative order before sorting remains unchanged after sorting.
• Unstable sort: The relative order of equal elements may be disrupted after sorting.

min, max

Basic usage

int a = 5, b = 10;

int mi = std::min(a, b); // mi = 5
int ma = std::max(a, b); // ma = 10

Custom comparator

struct Person {
    std::string name;
    int age;
};

Person p1{"Alice", 25}, p2{"Bob", 30};

// Return the one with smaller age
auto youngest = std::min(p1, p2, [](const Person &x, const Person &y){
    return x.age < y.age;
});

auto oldest = std::max(p1, p2, [](const Person &x, const Person &y){
    return x.age < y.age;
});

Accepts initializer_list (C++11 and above)

int x = std::min({3, 1, 4, 2}); // x = 1
int y = std::max({3, 1, 4, 2}); // y = 4

min_element/max_element

min_element and max_Iterator returned by element

vector<int> v= {1,2,4,8};
// Find minimum/maximum value
int mn = *std::min_element(v.begin(), v.end());
int mx = *std::max_element(v.begin(), v.end());

reverse

Reverse an ordered container

vector<int> v = {1,2,4,8};
std::reverse(v.begin(), v.end());

find

• Sequentially find the first element in the range equal to the given value, return an iterator. If not found, returnend。

vector<int> v = {1, 3, 5, 7};
auto it = std::find(v.begin(), v.end(), 5); // it points to 5
if(it != v.end()) {
    cout << "Found: " << *it << endl;
}

count

• Count the number of occurrences of a value in the range

vector<int> v = {1,2,2,3,2};
int cnt = std::count(v.begin(), v.end(), 2); // cnt = 3

transform

// Single-argument transformation (Unary Operation)
template<class InputIt, class OutputIt, class UnaryOperation>
OutputIt transform(InputIt first, InputIt last, OutputIt d_first, UnaryOperation unary_op);

// Two-argument transformation (Binary Operation)
template<class InputIt1, class InputIt2, class OutputIt, class BinaryOperation>
OutputIt transform(InputIt1 first1, InputIt1 last1, InputIt2 first2,
                   OutputIt d_first, BinaryOperation binary_op);

Example:

std::transform(s.begin(), s.end(), s.begin(), ::tolower);

Uses Single-argument version(Unary Operation), meaning:

• Input range:[s.begin(), s.end())
• Output range start:s.begin()(modify the string in place)
• Apply the operation to each character:::tolower

::tolowerin::refers toGlobal scope operator, indicating that the<cctype>the global defined intolowerfunction, to avoid confusion with<locale>instd::tolowerconfusion with (the overloaded version that takes a locale parameter).

You can also not usetolower, pass your own processing logic:

transform(s.begin(), s.end(), s.begin(), [](char c) {
    return c >= 'a' && c <= 'z' ? c - 32 : c;
});

---

two-argument transform

add elements of two arrays

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

int main() {
    vector<int> a = {1, 2, 3, 4};
    vector<int> b = {10, 20, 30, 40};
    vector<int> result(a.size());

    // result[i] = a[i] + b[i]
    transform(a.begin(), a.end(), b.begin(), result.begin(),
              [](int x, int y) { return x + y; });

    for (int x : result) cout << x << " ";  // Output: 11 22 33 44
}

binary_search

• Perform binary search on a sorted sequence, returningbool, determine whether it exists

vector<int> v = {1,3,5,7};
std::sort(v.begin(), v.end());
bool found = std::binary_search(v.begin(), v.end(), 5); // true

lower_bound/upper_bound

• returns an iterator，requires the sequence to be sorted
• lower_bound(begin,end,val): returns the first >= val the position of
• upper_bound(begin,end,val): returns the first > val the position of

vector<int> v = {1,2,2,3,5};
auto lb = std::lower_bound(v.begin(), v.end(), 2); // points to the first 2
auto ub = std::upper_bound(v.begin(), v.end(), 2); // points to 3

int distance = std::distance(std::lower_bound(vec.begin(), vec.end(), startTime),
                         std::upper_bound(vec.begin(), vec.end(), endTime));

equal_range

• Return[lower_bound, upper_bound)a pair of iterators, the range contains all elements equal to the given value

auto range = std::equal_range(v.begin(), v.end(), 2);
for(auto it = range.first; it != range.second; ++it) {
    cout << *it << " "; // output all 2s
}

next_permutation/prev_permutation

Generate the next lexicographic permutation.If the sequence is initially the lexicographically smallest, repeatedly calling it until it returns false generates all permutations.

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

int main() {
    // v is initially the lexicographically smallest
    std::vector<int> v = {1, 2, 3};

    do {
        for (int x : v) std::cout << x << " ";
        std::cout << "\n";
    } while (std::next_permutation(v.begin(), v.end()));
}

Output:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

• also used forgenerate all combinations of length m of numbers in an array

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

int main() {
    std::vector<int> vec = {1, 2, 3, 4};
    int m = 2;
    int n = vec.size();

    // Initialize the marker array
    std::vector<int> select(n, 0);
    std::fill(select.end() - m, select.end(), 1); // The last m elements are 1

    do {
        // Generate combinations based on select
        for (int i = 0; i < n; ++i) {
            if (select[i]) std::cout << vec[i] << " ";
        }
        std::cout << "\n";
    } while (std::next_permutation(select.begin(), select.end()));
}

output

1 2
1 3
2 3
1 4
2 4
3 4

You can also use prev_permutation

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

int main() {
    std::vector<int> vec = {1, 2, 3, 4};
    int m = 2; // Combination length
    int n = vec.size();

    // 1. Create the selection marker array
    std::vector<int> select(n, 0);
    std::fill(select.begin(), select.begin() + m, 1); // The first m are selected

    std::vector<std::vector<int>> result;

    // 2. Use prev_permutation to generate all combinations
    do {
        std::vector<int> combo;
        for (int i = 0; i < n; ++i) {
            if (select[i]) combo.push_back(vec[i]);
        }
        result.push_back(combo);
    } while (std::prev_permutation(select.begin(), select.end()));

    // output
    for (auto& c : result) {
        for (auto x : c) std::cout << x << " ";
        std::cout << "\n";
    }
}

fill

• fill(begin,end,val): Fill the entire range with the specified value

vector<int> v(5);
std::fill(v.begin(), v.end(), 7); // v = {7,7,7,7,7}


std::vector<int> select(n, 0);
std::fill(select.begin(), select.begin() + m, 1);

iota

• iota(begin,end,start): Generate a sequence of consecutive integers

#include <numeric>
vector<int> v(5);
std::iota(v.begin(), v.end(), 10); // v = {10,11,12,13,14}

copy / swap / replace / remove / remove_if

• copy(begin,end,out_it): Copy a range to another container

vector<int> src = {1,2,3};
vector<int> dst(3);
std::copy(src.begin(), src.end(), dst.begin());

• swap(a,b)/iter_swap(it1,it2): Swap elements

std::swap(a,b);
std::iter_swap(v.begin(), v.begin()+1);

• replace(begin,end,old_val,new_val): Replace elements in a range

std::replace(v.begin(), v.end(), 2, 5);

• remove(begin,end,val)/remove_if(begin,end,pred): Logical removal (needs to be combined witherase）

v.erase(std::remove(v.begin(), v.end(), 5), v.end());
v.erase(std::remove_if(v.begin(), v.end(), [](int x){ return x%2==0; }), v.end());

set operations

• The sequence must be sorted
• merge(a,b,out): Merge two sorted sequences
• set_union(a,b,out): Union
• set_intersection(a,b,out): Intersection
• set_difference(a,b,out): Difference
• unique(begin,end): Remove adjacent duplicate elements

vector<int> a = {1,2,2,3};
vector<int> b = {2,3,4};
vector<int> out;

std::set_union(a.begin(),a.end(),b.begin(),b.end(),std::back_inserter(out));
// out = {1,2,2,3,4}

a.erase(std::unique(a.begin(),a.end()), a.end()); // Deduplicate a = {1,2,3}

std::unique only removes adjacent duplicate elements. To deduplicate the entire sequence (remove all duplicates), you must sort the sequence first.

accumulate / all_of / any_of / none_of / for_each

• accumulate(begin,end,init): Sum over a range (or custom operation)

#include <numeric>
vector<int> v = {1,2,3};
int sum = std::accumulate(v.begin(), v.end(), 0); // sum = 6

• all_of(begin,end,pred)/any_of/none_of: Determine whether range elements satisfy a condition

bool all_even = std::all_of(v.begin(), v.end(), [](int x){ return x%2==0; });
bool any_even = std::any_of(v.begin(), v.end(), [](int x){ return x%2==0; });

• for_each(begin,end,f): Range traversal

std::for_each(v.begin(), v.end(), [](int &x){ x++; });

Time complexity

algorithm	Function	Time complexity	Example code
sort	Sort (unstable)	O(n log n)	std::sort(v.begin(), v.end());
stable_sort	Stable sort	O(n log² n)Worst, averageO(n log n)	std::stable_sort(v.begin(), v.end());
min / max	Min/max of two numbers	O(1)	std::min(a,b); std::max(a,b);
min_element / max_element	Range min/max element iterator	O(n)	*std::min_element(v.begin(), v.end());
reverse	Reverse range	O(n)	std::reverse(v.begin(), v.end());
find	Sequential search	O(n)	auto it = std::find(v.begin(),v.end(),5);
count	Count occurrences	O(n)	std::count(v.begin(),v.end(),2);
binary_search	Exists (binary search, requires sorted)	O(log n)	std::binary_search(v.begin(),v.end(),5);
lower_bound	The first >= val(binary search)	O(log n)	auto it=std::lower_bound(v.begin(),v.end(),2);
upper_bound	The first > val(binary search)	O(log n)	auto it=std::upper_bound(v.begin(),v.end(),2);
equal_range	Return the range equal to val	O(log n)	auto r=std::equal_range(v.begin(),v.end(),2);
fill	Range assignment	O(n)	std::fill(v.begin(), v.end(), 7);
iota	Continuous assignment (requires<numeric>）	O(n)	std::iota(v.begin(),v.end(),10);
copy	Copy range	O(n)	std::copy(src.begin(),src.end(),dst.begin());
swap / iter_swap	Swap elements	O(1)	std::swap(a,b);
replace	Replace specified value	O(n)	std::replace(v.begin(),v.end(),2,5);
remove / remove_if	Logical deletion (requireserase）	O(n)	v.erase(std::remove(v.begin(),v.end(),5),v.end());
unique	Remove adjacent duplicates (logical deletion)	O(n)	v.erase(std::unique(v.begin(),v.end()),v.end());
set_union	Union (requires sorted)	O(n+m)	std::set_union(a.begin(),a.end(),b.begin(),b.end(),back_inserter(out));
set_intersection	Intersection (requires sorted)	O(n+m)	std::set_intersection(...);
set_difference	Set difference (requires sorted order)	O(n+m)	std::set_difference(...);
merge	Merge two sorted sequences	O(n+m)	std::merge(a.begin(),a.end(),b.begin(),b.end(),out.begin());
accumulate	Range accumulation (requires<numeric>）	O(n)	int sum=std::accumulate(v.begin(),v.end(),0);
all_of / any_of / none_of	Range condition check	O(n)	std::all_of(v.begin(),v.end(),[](int x){return x%2==0;});
for_each	Iterate and execute function	O(n)	std::for_each(v.begin(),v.end(),[](int &x){x++;});

utility

Include header file

#include <utility>

pair

Include header file

#include <utility>
using std::pair;

Construct

pair<int,int> p = {1,2};

auto p = std::make_pair(1, 2); // Automatic type deduction

Access element

int a = p.first;
int b = p.second;

std::move

std::move actually converts the parameter t to an rvalue reference type. It itself does not perform any resource copying or releasing, nor does it call constructors or destructors (the actual move operation is completed by the called move constructor/move assignment operator).

template <typename T>
typename std::remove_reference<T>::type&& move(T&& t) noexcept {
    return static_cast<typename std::remove_reference<T>::type&&>(t);
}

Take std::vector as an example:

std::vector<int> a = {1, 2, 3};
std::vector<int> b = std::move(a);

Here: std::move(a) turns a into an rvalue reference. The compiler will choose vector’s move constructor instead of the copy constructor.
What the move constructor does:

• It directly “steals” a’s internal pointer and gives it to b.
• It sets a’s pointer to null to avoid releasing the same memory during destruction.

So in the end: b holds the data {1,2,3}. a becomes empty (size()==0, but it is still a valid object).

Summary: Takeb = std::move(a)as an example (here it is move construction, b is a new object):

• b takes over a’s internal pointer (i.e., a’s resources are transferred to b)
• a is placed in a valid but unspecified state (for std::vector, a becomes empty, size()==0, and is still a valid object)
• When a is destructed, it releases the resources it currently holds (at this time it is empty, so it will not be released repeatedly)
• There is no need to manually call the destructor.