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 basic syntax of the C++ programming language and the core components of the Standard Template Library (STL). It discusses in detail the concepts of lvalues, rvalues, and reference types, the operation methods of standard input/output streams and sstream string streams, and summarizes the usage and time complexity of common containers such as vector, queue, and priority_queue.

---

Syntax

& and &&, lvalues and rvalues

• Lvalue

  • Has a name and can have its address taken.

  • 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 have its address taken

• Rvalue

  • Temporary objects or literals, without a name, cannot have their address taken.

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

  • Example:

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

  Note: Rvalues can bind 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 commonly used for move semantics:

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

Input and Output

Input

First, in C++, 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: single read and batch read. The principle of cin is, simply put, that there is a buffer. Data entered from the keyboard is first stored in the buffer, and cin can 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 want to read contains spaces, 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, and the read string includes spaces, ending when a newline character is encountered

• getchar()

This function reads a character from the buffer and is often used to determine whether a newline occurs

Output

Similarly, in C++, 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 commonly used.coutIt should be noted that if outputtingendlan 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 reading and writing	General purpose
istringstream	Read-only input stream	Parse string
ostringstream	Write-only output stream	Construct string

Common operations:

Function	Purpose	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 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;
}

Usage	Method	Example	Description	Common Pitfall
Whitespace Tokenization	ss >> word	ss >> w1 >> w2	Split by spaces, newlines, and tabs	Does not split on non-whitespace like commas
Custom Delimiter	getline(ss, word, ',')	getline(ss, word, ',');	Split by,splitting	Must usegetline，>>Cannot customize delimiter
Parsing Numbers	ss >> num	int x; ss >> x;	String numbers to int/double	Non-numeric values cause stream failure, must checkss.fail()
Concatenate strings	oss << val	oss << "ID=" << 5;	Efficiently construct dynamic strings	After output endsoss.str()Can only get the complete content

STL

vector

Include header file

#include <vector>
using std::vector;

Construction

// Empty vector
vector<int> v1;

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

// Specify size and initial value
vector<int> v3(5, 42);  // 5 elements, each is 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 elements

• Returns a reference to the element

• Access with bounds checking throws if out of boundsstd::out_of_rangeexception

// Access by index (without 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);      // Remove element at index 2
v.clear();                   // Clear all elements

Iterate over elements

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

// Iterator traversal
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) reallocation
pop_back()	O(1)	Remove last element
insert(v.begin() + i, x)	O(n)	Insert in middle, average move n/2 elements
erase(v.begin() + i)	O(n)	Remove middle element, average move n/2 elements
front()/back()	O(1)	Access first/last element
size()/empty()	O(1)	Get size / check if empty
clear()	O(n)	Clear elements (destructor call)
sort(v.begin(), v.end())	O(n log n)	Sort using STL algorithms

queue

Include header file

#include <queue>
using std::queue;

Construction

// Empty queue
queue<int> q1;

// Copy construction
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 max-heap by default

• When dequeuing, always pop thelargest element(default max-heap).

• A custom comparator can be used to implementa min-heap。

priority_queue has no iterators; traversal can only be done using pop() and top()

Include header file

#include <queue>
using std::priority_queue;

Construction

The template parameters of priority_queue: the first is the element type, the second is the underlying container (default vector), and the third is the comparator

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

• If you want to delete a specific element from priority_queue, consider whether you can use unordered_map to implementlazy deletion(only delete when the invalid element reaches the top, otherwise just mark it)

// Default constructor
priority_queue<int> pq1;
// All parameters of default constructor
priority_queue<int,vector<int>,std::less<int>>;
// 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 top of heap

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

Pop top element of heap

pq.pop();

Custom comparator

Method 1: Use std::greaterImplement 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’s a struct, directly overload < operator

struct Person {
    string name;
    int age;

    // Overload < operator
    bool operator<(const Person& other) const {
        return age < other.age;  // Default max heap, older age first
    }
};

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, Last In First Out

stackNo iterator, cannot usefordirect loop traversal. Traversal can only be done viatop()+pop()。

Include Header File

#include <stack>
using std::stack;

Construction

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

Push/Pop

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

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

Access Top Element

// View Top Element
int top_val = s.top();  // top element of 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

  • mapisordered associative container, typically implemented usingred-black tree.

  • Each element is akey-valuepair, with unique keys, automatically sorted by key.

  • Suitable for scenarios requiringaccess in key order.

• unordered_map

  • unordered_mapisHash table, stores key-value pairs in no particular order.
  • Average time complexity for search, insertion, and deletion is O(1).
  • Suitable for fast lookups,order is not important。

GCC’sunordered_maphas had an optimization since C++11:

• When the linked list in a bucket exceeds a certain threshold (usually 8), the list is converted to a red-black tree。
• This preventsthe O(n) complexity caused by worst-case hash collisions, reducing 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;

Construction

map

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

// Copy construction
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 construction
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];       // Key must exist, otherwise a default value will be created

unordered_map

unordered_map<int, string> um;

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

Insert, modify, and element

map

map<int, string> m;

// Insert element
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 element

map

map<int, string> m;

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

auto it = m.find(2);   // Returns iterator, returns 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 iterator, returns um.end() if not found
bool hasKey = um.count(2); // 0 or 1

Delete element

map

map<int, string> m;

// Delete element
m.erase(1);            // Delete by key
m.erase(m.begin());    // Delete by iterator

unordered_map

unordered_map<int, string> um;

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

Traverse

map

Map is traversed in order by key

map<int, string> m;

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

unordered_map

Note:unordered_mapis unordered, and the traversal order is not fixed.

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

Custom comparator (map only)

map<int, string, std::greater<int>> m; // Sort by key in descending order

Time complexity

map

Operation	Average complexity
Insert/Delete	O(log n)
Search	O(log n)
Traversal	O(n)
Access element	O(log n)

unordered_map

Operation	Average complexity	Worst-case complexity
Insert	O(1)	O(n)
find	O(1)	O(n)
delete	O(1)	O(n)
traverse	O(n)	O(n)

set, unordered_set

• set
  • setisordered set, usually implemented withred-black tree.
  • Storesunique elements, automatically sorted by element size.
  • Suitable for scenarios requiringordered access and fast lookup of unique elements.
• unordered_set
  • unordered_setisHash table set, stores unique elements in no particular order.
  • Average search, insertion, and deletion complexity is O(1).
  • Suitable for fast lookups when order is not important.

GCC’sunordered_setalso supportstreeification within buckets when the linked list length exceeds a threshold, avoiding the worst-case O(n).

Include header file

set

#include <set>
using std::set;

unordered_set

#include <unordered_set>
using std::unordered_set;

---

Construction

set

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

unordered_set

unordered_set<int> us1;              // Empty set
unordered_set<int> us2(us1);         // Copy construction
unordered_set<int> us3 = {1, 2, 3};  // Initialization list

---

Insertion and modification

set

set<int> s;

s.insert(10);  // Insert element
s.insert(20);
s.insert(10);  // Duplicate elements will not be inserted

unordered_set

unordered_set<int> us;

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

---

Find element

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

Delete element

set

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

unordered_set

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

Traversal

set

Traverse in ascending order of elements

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

unordered_set

Traversal order is not fixed

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

Custom comparator (only supported by set)

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

Time complexity

set

Operation	Average complexity
Insert/Delete	O(log n)
Search	O(log n)
Traversal	O(n)

unordered_set

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

string

In most modern C++ compilers (such as GCC/Clang/MSVC),std::stringthe implementation is similar to:

• Internally usesa dynamic arrayto store characters
• automatically maintains a trailing'\0'(compatible with C-string)
• Eachstringalso maintainssizeandcapacity

String expansion usually follows**exponential growth (e.g., doubling)**to reduce repeated memory allocations.

Small String Optimization (SSO)

SSO isstd::stringa core performance optimization technique.

Purpose: Reduce heap memory allocation and speed up small string operations.

When the string length is short (typically ≤ 15 characters), many implementations willstore it directly 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;

Construction

Construction method	Prototype	Description	Example
Default constructor	string()	Create empty string	string s1; // ""
Copy constructor	string(const string& str)	Copy existing string	string s2(s1);
Move constructor	string(string&& str)	Move existing string (since C++11)	string s3(std::move(s1));
C string	string(const char* s)	From a C string ending with\0null-terminated C string	string s4("hello");
C string + length	string(const char* s, size_t n)	Take only first n characters	string s5("hello world", 5); // "hello"
Repeated character	string(size_t n, char c)	Create 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 construction

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

• Common pitfalls: Empty string’sc_str()is still valid, returns""。

---

Copy construction

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

• Performance advice: For large strings, prefer usingconst string&pass by reference to avoid copying

---

Move construction (C++11+)

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

• Characteristics：s2The content is moved, the original object becomes empty
• Advantages: Avoid copying memory to improve performance

---

C string construction

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

• Use cases: Initialize from literals or C-style arrays
• Performance tips: If the length is known, use the second parameter to avoid redundant scanning
• Common pitfalls: Passing a non-\0null-terminated string requires specifying 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; accessing out-of-bounds leads to undefined behavior.

  • After move construction or reallocation, pointers or references to the original characters may become invalid.

Safe Accessat()

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

• Description：
  • Performs range checking and throwsstd::out_of_rangeexception on out-of-bounds access.

---

Accessing First and Last Characters

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

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

• Description：
  • Callingfront()orback()on an empty string is undefined behavior.
• Common Pitfall：
  • Accessing an empty string triggers UB (undefined behavior).

---

String Assignment assign()

assign()isstd::stringVersatile assignment functions with rich overloading:

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); // 取 s2[1..3]
string& assign(const char* s)	C-string assignment	s.assign("world");
string& assign(const char* s, size_t n)	Assign 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)	Initializer list assignment (C++11+)	s.assign({'x','y','z'}); // "xyz"

Modifying operations

Append

Prototype	Description	Example
string& append(const string& str)	Append entire string	s.append(s2);
string& append(const string& str, size_t pos, size_t count)	Append substring of str	s.append(s2, 1, 3);
string& append(const char* s)	Append C string	s.append("world");
string& append(const char* s, size_t n)	Append first n characters of 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 range	vector<char> v{'a','b'}; s.append(v.begin(), v.end());
string& push_back(char c)	Append single character	s.push_back('x');

Performance advice

Optimize concatenation — default concatenation is inefficient

string s;
s.reserve(1000);  // Reserve space to reduce reallocation

• For frequent modifications, usestd::ostringstreamorstd::string_view

Insert

Prototype	Description	Example
string& insert(size_t pos, const string& str)	Insert entire string at pos	s.insert(2, s2);
string& insert(size_t pos, const string& str, size_t subpos, size_t count)	Insert substring of str	s.insert(1, s2, 0, 2);
string& insert(size_t pos, const char* s)	Insert C string	s.insert(0, "Hi");
string& insert(size_t pos, const char* s, size_t n)	Insert first n characters of C string	s.insert(0, "Hello World", 5);
string& insert(size_t pos, size_t n, char c)	Insert n identical characters	s.insert(3, 4, '*');
iterator insert(const_iterator p, char c)	Insert single character	s.insert(s.begin()+1, 'x');
template<class InputIt> void insert(const_iterator p, InputIt first, InputIt last)	Insert range	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)	Delete character pointed by iterator	s.erase(s.begin()+1);
iterator erase(const_iterator first, const_iterator last)	Delete 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 from 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 substring of str	s.replace(0,2,s2,1,2);
string& replace(size_t pos, size_t count, const char* s)	Replace with C string	s.replace(0,2,"OK");
string& replace(size_t pos, size_t count, const char* s, size_t n)	Replace with first n characters of 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 identical characters	s.replace(0,2,3,'*');
iterator replace(const_iterator first, const_iterator last, InputIt first2, InputIt last2)	Replace iterator range	s.replace(s.begin(), s.begin()+2,v.begin(),v.end());

Find operation

Function prototype	Description	Example
size_t find(const string& str, size_t pos=0) const	Find first occurrence of 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 first n characters of C string	s.find("hello world", 0, 5); // 查找 "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 from 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 from set	s.find_last_of("aeiou");
size_t find_first_not_of(const string& chars, size_t pos=0) const	Find first position not in character set	s.find_first_not_of("aeiou");
size_t find_last_not_of(const string& chars, size_t pos=npos) const	Find last position not in character set	s.find_last_not_of("aeiou");

String comparison

Function prototype	Description	Example	Performance
int compare(const string& str) const	Compare entire string with str	s.compare("hello");	O(min(n, m))
int compare(size_t pos, size_t count, const string& str) const	Compare substring[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 s substring with str substring	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 less than 0: s < str,

• Return value equal to 0: s == str,

• Return value greater than 0: s > str

Can also compare using operators

Operators	Function	Example	Return Type	Comparison Method
==	Check Equality	s == "hello"	bool	Case-Sensitive & Character-by-Character Comparison
!=	Check Inequality	s != t	bool	Same as Above
<	Lexicographically Less Than	"abc" < "abd"	bool	Compare by ASCII/Unicode
<=	Less Than or Equal	"abc" <= "abc"	bool	Same as Above
>	Lexicographically Greater Than	"dog" > "cat"	bool	Same as Above
>=	Greater Than or Equal	"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 length ofcountsubstring	s.substr(2, 4)	Returns a new string	pos > size()Throws exception	Creates a new string copy, be mindful of performance

Character checking and case conversion

Need to include C standard library

#include <cctype>

Common character judgment functions

Function	Purpose	Example
isalnum(c)	Is it alphanumeric	'A','z','3'
isalpha(c)	Is it a letter	'A','b'
isdigit(c)	Is it a digit	'0'~'9'
islower(c)	Is it a lowercase letter	'a'
isupper(c)	Is it an uppercase letter	'Z'
isspace(c)	Is it a whitespace character (space/newline/tab)	' ','\n','\t'
ispunct(c)	Is it a punctuation mark	',' '.' '!'
isxdigit(c)	Is it a hexadecimal digit	'0'~'9','a'~'f'
isprint(c)	Is it a printable character	Normal character
iscntrl(c)	Is it 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, they need to be used 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 tothe global scope operator, indicating the use ofthe global tolower functionto avoid ambiguity caused by having the same name as certain class members.

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 successfully converted charactersbase: 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	Convert tolong	stol("99999") → 99999L
stoll	long long stoll(const string& str, size_t* pos = 0, int base = 10);	Same as above	Convert tolong long	stoll("1234567890123")
stoi(C string)	int stoi(const char* str, size_t* pos = 0, int base = 10);	str: C-style string	convert toint	stoi("42") → 42

---

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 parsed character length	convert tofloat	stof("3.14") → 3.14f
stod	double stod(const string& str, size_t* pos = 0);	Same as above	convert todouble	stod("2.71828")
stold	long double stold(const string& str, size_t* pos = 0);	Same as above	convert tolong double	stold("1.6180339887")

---

Number → 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 integer	to_string(1234567890123)

---

Return Value and Exception Summary

Condition	Behavior
Input is not a number	Throwstd::invalid_argument
Number out of range	Throwstd::out_of_range
Automatically trim leading spaces	✅ Supported" 123"
Supports symbols	✅"-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	Purpose	Scenario
stringstream	Supports both reading and writing	General
istringstream	Read-only input stream	Parse string
ostringstream	Write-only output stream	Construct string

Common operations:

Function	Purpose	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 status	Determine if parsing was successful

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 like commas
Custom delimiter	getline(ss, word, ',')	getline(ss, word, ',');	by,split	must usegetline，>>cannot customize delimiter
parse numbers	ss >> num	int x; ss >> x;	string numbers → int/double	non-numeric values cause stream failure, need to checkss.fail()
concatenate strings	oss << val	oss << "ID=" << 5;	efficiently build dynamic strings	after output endsoss.str()can only get the complete content

multiset/multimap

multiset

• elementscan be repeated, automatically sorted by key
• underlying usually usesRed-black tree
• Does not support access via subscript; only iterators can be used
• Suitable for scenarios requiringfast lookup and sequential traversal of duplicate elements

multimap<K,V>

• key duplicates allowed, sorted by key
• Underlying implementation typically usesred-black tree
• Can useequal_rangeto find all elements with a given key

Include header file

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

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

Construction

multiset

multiset<int> ms;            // Empty multiset
multiset<int> ms2(ms);        // Copy construction
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 element

// multiset
ms.insert(2);
ms.insert(2); // can be duplicated

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

find element

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

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

delete element

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

// multimap
mm.erase(2);          // delete all elements with key=2
auto it2 = mm.find(2);
mm.erase(it2);        // delete 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)
search	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: getrequires index to be a constant known at compile time, so cannot use it to traverse

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] = tuple;

• You can also use std::tie

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

Modify

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

Get length

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

Traverse

Not commonly used, use structured binding + fold expression

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 in ascending order
std::sort(people.begin(), people.end(), [](const Person &a, const Person &b){
    return a.age < b.age;
});

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

The standard requirement of std::sort is that stability is not guaranteed. If stable sorting is needed, please 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 younger one
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 later)

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
int mn = *std::min_element(v.begin(), v.end());
int mx = *std::max_element(v.begin(), v.end());

reverse

Reverse ordered container

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

find

• Sequentially find the first element equal to a given value in the range, returns an iterator. Returnsend。

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 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

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

// 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);

Usingunary version(Unary Operation), meaning:

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

::tolowerin::refers toglobal scope operator, meaning usingthe global tolower functionto avoid ambiguity caused by having the same name as certain class members.

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-parameter transformation

Add two array elements

#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 if 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

• Return iterator，Requires the sequence to be sorted
• lower_bound(begin,end,val): returns the first**>= val**position
• upper_bound(begin,end,val): returns the first**> val**position

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); // point 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)iterator pair, 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 2
}

next_permutation/prev_permutation

generate the next lexicographical permutation, can be used forgenerate all permutations of a sequence

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

int main() {
    // v is the smallest lexicographically
    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 from 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 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

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 a selection marker array
    std::vector<int> select(n, 0);
    std::fill(select.begin(), select.begin() + m, 1); // First m selected

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

    // 2. Generate all combinations using prev_permutation
    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 a 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 used 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 besorted
• 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 consecutive duplicates

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}

Using std::unique requires elements to be already sorted

accumulate / all_of / any_of / none_of / for_each

• accumulate(begin,end,init): Range sum (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: Check if range elements satisfy 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	iterator to min/max element in range	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, requires sorted)	O(log n)	std::binary_search(v.begin(),v.end(),5);
lower_bound	first**>= val**(binary)	O(log n)	auto it=std::lower_bound(v.begin(),v.end(),2);
upper_bound	first**> val**(binary)	O(log n)	auto it=std::upper_bound(v.begin(),v.end(),2);
equal_range	return 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	consecutive 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 order)	O(n+m)	std::set_union(a.begin(),a.end(),b.begin(),b.end(),back_inserter(out));
set_intersection	Intersection (requires sorted order)	O(n+m)	std::set_intersection(...);
set_difference	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	Traverse 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;

Construction

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

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

Accessing elements

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

std::move

std::move actually converts the parameter t to an rvalue reference type, without copying memory, releasing resources, or calling constructors and destructors

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::vectoras 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 the vector’s move constructor instead of the copy constructor.
What the move constructor does:

• Directly “steals” a’s internal pointer and gives it to b.
• 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 is still a valid object)

Summary:
nums1 = std::move(vec);

• Old content is automatically released (done internally by move assignment)
• New content takes over
• vec becomes empty
  No need to manually call the destructor.