Learning Objectives: Fundamentals of C++ Programming Language
Learning Content: Basic Syntax
This article is aimed at beginners and introduces the basic usage of C++, including control statements, commonly used data structures from the standard library, etc., to help quickly get started with coding challenges.
For example:
- Standard Output
- Control Statements
- Basic Data Structures
- Summary
Standard Output:
The standard output in C++ is cout, which uses the << operator to pass the content to be printed to cout, and endl is the newline character.
int a = 10; // Output: 10
cout << a << endl; // Can chain output
// Output: Hello, World!
cout << "Hello" << ", " << "World!" << endl;
string s = "abc"; // Output: abc 10
cout << s << " " << a << endl;Of course, the printf function from C can also be used, but cout is more convenient, so we generally use cout.
Control Statements:
Control statements in programming languages are generally quite simple, the most common being conditional statements and loops, which will be briefly introduced below.
Conditional Statement if else
int a = 10;
if (a > 5) {
cout << "a > 5" << endl;
} else if (a == 5) {
cout << "a == 5" << endl;
} else {
cout << "a < 5" << endl;
} // Output: a > 5Loop for/while
Both for and while can be used for loops, with for loops generally used when the number of iterations is known, while while loops are used when the number of iterations is unknown.
// 0 1 2 3 4
for (int i = 0; i < 5; i++) {
cout << i << " ";
}
int num = 100; // 100 50 25 12 6 3 1
while (num > 0) {
cout << num << " ";
num /= 2;
}Basic Data Structures
For commonly used data structures from the standard library, you can create data structures directly using keywords like vector, set, map, etc., but you also need to include the corresponding header files.
Dynamic Array vector
vector is the dynamic array of the C++ standard library.
When learning C, you must have learned to create static arrays using malloc, int[n], etc., but this method is very cumbersome and error-prone. When solving algorithm problems, we generally use dynamic arrays vector, and the input provided in the problems is usually of vector type.
The initialization methods for vector are as follows:
#include <vector>
int n = 7, m = 8; // Initialize an empty int array nums
vector<int> nums; // Initialize an array nums of size n, with all values defaulting to 0
vector<int> nums(n); // Initialize an array nums with elements 1, 3, 5
vector<int> nums{1, 3, 5}; // Initialize an array nums of size n, all values are 2
vector<int> nums(n, 2); // Initialize a 2D int array dp
vector<vector<int>> dp; // Initialize a boolean array dp of size m * n, with all values initialized to true
vector<vector<bool>> dp(m, vector<bool>(n, true));Common Operations of vector:
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n = 10; // Array size is 10, all element values are 0
vector<int> nums(n);
// Output 0 (false)
cout << nums.empty() << endl;
// Output: 10
cout << nums.size() << endl;
// Insert an element 20 at the end of the array
nums.push_back(20);
// Output: 11
cout << nums.size() << endl;
// Get a reference to the last element of the array
// Output: 20
cout << nums.back() << endl;
// Delete the last element of the array (no return value)
nums.pop_back();
// Output: 10
cout << nums.size() << endl;
// You can directly access or modify values using brackets
nums[0] = 11;
// Output: 11
cout << nums[0] << endl;
// Insert an element 99 at index 3
nums.insert(nums.begin() + 3, 99);
// Delete the element at index 2
nums.erase(nums.begin() + 2);
// Swap nums[0] and nums[1]
swap(nums[0], nums[1]);
// Traverse the array
// 0 11 99 0 0 0 0 0 0 0
for (int i = 0; i < nums.size(); i++) {
cout << nums[i] << " ";
}
cout << endl;
}The above are the commonly used methods of C++ vector in the article, which mainly involve using indices to access elements and the push_back, pop_back methods. For algorithm problems, these are sufficient.
Because according to the characteristics of “arrays”, accessing elements using indices is very efficient, and adding or deleting elements from the end is also very efficient; however, adding or deleting elements from the middle or front involves moving data, which is very inefficient.
Doubly Linked List list:
list is a doubly linked list container in the C++ standard library. Initialization methods:
#include <list>
using namespace std;
int n = 7; // Initialize an empty doubly linked list lst
list<int> lst; // Initialize a linked list lst of size n, with all values defaulting to 0
list<int> lst(n); // Initialize a linked list lst containing elements 1, 3, 5
list<int> lst{1, 3, 5}; // Initialize a linked list lst of size n, all values are 2
list<int> lst(n, 2);Common Methods of list:
#include <iostream>
#include <list>
using namespace std;
int main() {
// Initialize the linked list
list<int> lst{1, 2, 3, 4, 5};
// Check if the linked list is empty, output: false
cout << lst.empty() << endl;
// Get the size of the linked list, output: 5
cout << lst.size() << endl;
// Insert element 0 at the head of the linked list
lst.push_front(0);
// Insert element 6 at the tail of the linked list
lst.push_back(6);
// Get the head and tail elements of the linked list, output: 0 6
cout << lst.front() << " " << lst.back() << endl;
// Delete the head element of the linked list
lst.pop_front();
// Delete the tail element of the linked list
lst.pop_back();
// Insert an element in the linked list
auto it = lst.begin();
// Move to the third position
advance(it, 2);
// Insert 99 at the third position
lst.insert(it, 99);
// Delete an element in the linked list
it = lst.begin();
// Move to the second position
advance(it, 1);
// Delete the element at the second position
lst.erase(it);
// Traverse the linked list
// Output: 1 99 3 4 5
for (int val : lst) {
cout << val << " ";
}
cout << endl;
return 0;
}Generally speaking, when we want to add or delete elements at the head, we will use a doubly linked list because it is more efficient than vector for adding or deleting elements at the head. However, when accessing elements by index, we will use vector.
Queue queue
queue is a queue container in the C++ standard library, based on the first-in-first-out (FIFO) principle. Queues are suitable for scenarios where elements can only be added from one end (the tail) and removed from the other end (the head).
#include <iostream>
#include <queue>
using namespace std;
int main() {
// Initialize an empty integer queue q
queue<int> q;
// Add elements to the tail of the queue
q.push(10);
q.push(20);
q.push(30);
// Check if the queue is empty, output: false
cout << q.empty() << endl;
// Get the size of the queue, output: 3
cout << q.size() << endl;
// Get the head and tail elements of the queue, output: 10 and 30
cout << q.front() << " " << q.back() << endl;
// Delete the head element
q.pop();
// Output the new head element: 20
cout << q.front() << endl;
return 0;
}Stack stack
A stack is a last-in-first-out (LIFO) data structure, suitable for scenarios where elements can only be added or removed from one end (the top of the stack).
stack is a stack container in the C++ standard library, regarding the implementation principles and usage scenarios of stacks.
#include <iostream>
#include <stack>
using namespace std;
int main() {
// Initialize an empty integer stack s
stack<int> s;
// Add elements to the top of the stack
s.push(10);
s.push(20);
s.push(30);
// Check if the stack is empty, output: false
cout << s.empty() << endl;
// Get the size of the stack, output: 3
cout << s.size() << endl;
// Get the top element of the stack, output: 30
cout << s.top() << endl;
// Delete the top element
s.pop();
// Output the new top element: 20
cout << s.top() << endl;
return 0;
}Hash Table unordered_map
unordered_map is a hash table implementation in the C++ standard library, providing storage based on key-value pairs, with constant time complexity for searching, inserting, and deleting key-value pairs.
#include <unordered_map>
using namespace std;
// Initialize an empty hash table map
unordered_map<int, string> hashmap;
// Initialize a hash table map containing some key-value pairs
unordered_map<int, string> hashmap{{1, "one"}, {2, "two"}, {3, "three"}};Common Methods of unordered_map:
Note: Accessing a non-existent key will automatically insert a key-value pair. In C++ hash tables, if you access a non-existent key, it will automatically create this key, with the corresponding value being the default constructed value. This is different from other languages and requires special attention. Remember to check if the key exists before accessing the value, otherwise, you may accidentally create a new key, leading to algorithm errors. See the example below.
#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
// Initialize hash table
unordered_map<int, string> hashmap{{1, "one"}, {2, "two"}, {3, "three"}};
// Check if the hash table is empty, output: 0 (false)
cout << hashmap.empty() << endl;
// Get the size of the hash table, output: 3
cout << hashmap.size() << endl;
// Check if a specified key exists
// Note: contains method is new in C++20
// Output: Key 2 -> two
if (hashmap.contains(2)) {
cout << "Key 2 -> " << hashmap[2] << endl;
} else {
cout << "Key 2 not found." << endl;
}
// Get the value corresponding to a specified key, if it does not exist, it will return the default constructed value
// Output empty string
cout << hashmap[4] << endl;
// Insert a new key-value pair
hashmap[4] = "four";
// Get the newly inserted value, output: four
cout << hashmap[4] << endl;
// Delete a key-value pair
hashmap.erase(3);
// Check if key 3 exists after deletion
// Output: Key 3 not found.
if (hashmap.contains(3)) {
cout << "Key 3 -> " << hashmap[3] << endl;
} else {
cout << "Key 3 not found." << endl;
}
// Traverse the hash table
// Output (order may vary):
// 4 -> four
// 2 -> two
// 1 -> one
for (const auto &pair: hashmap) {
cout << pair.first << " -> " << pair.second << endl;
}
// Special note, accessing a non-existent key will automatically create this key
unordered_map<int, string> hashmap2;
// Number of key-value pairs is 0
cout << hashmap2.size() << endl; // 0
// Accessing a non-existent key will automatically create this key, with the corresponding value being the default constructed value
cout << hashmap2[1] << endl; // empty string
cout << hashmap2[2] << endl; // empty string
// Now the number of key-value pairs is 2
cout << hashmap2.size() << endl; // 2
return 0;
}Hash Set unordered_set
unordered_set is a hash set implementation in the C++ standard library, used to store unique elements, commonly used for deduplication.
#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
// Initialize hash set
unordered_set<int> hashset{1, 2, 3, 4};
// Check if the hash set is empty, output: 0 (false)
cout << hashset.empty() << endl;
// Get the size of the hash set, output: 4
cout << hashset.size() << endl;
// Check if a specified element exists
// Output: Element 3 found.
if (hashset.contains(3)) {
cout << "Element 3 found." << endl;
} else {
cout << "Element 3 not found." << endl;
}
// Insert a new element
hashset.insert(5);
// Delete an element
hashset.erase(2);
// Output: Element 2 not found.
if (hashset.contains(2)) {
cout << "Element 2 found." << endl;
} else {
cout << "Element 2 not found." << endl;
}
// Traverse the hash set
// Output (order may vary):
// 1
// 3
// 4
// 5
for (const auto &element : hashset) {
cout << element << endl;
}
return 0;
}Pass by Value and Pass by Reference
In C++, there are mainly two ways to pass function parameters: pass by value and pass by reference. Understanding the differences between them is crucial for writing efficient algorithm code, especially when dealing with large amounts of data or needing to modify the original data.
Pass by Value
Pass by value means passing a copy of the function parameter to the function, and modifications to that copy within the function do not affect the original data. Here is an example:
#include <iostream>
using namespace std;
void modifyValue(int x) {
x = 10; // Only modifies the copy, does not affect the original data
}
int main() {
int num = 5;
modifyValue(num);
// Output: 5
cout << "After modifyValue, num = " << num << endl;
return 0;
}In the above code, the value of num does not change after calling modifyValue because what was passed was a copy of num, and modifications within the function only affect the copy.
Pass by Reference
Pass by reference means passing the address of the actual parameter to the function, allowing the function to directly manipulate the original data. This means that modifications to the parameter will directly affect the original data.
Here is an example:
#include <iostream>
using namespace std;
void modifyReference(int &x) {
x = 10; // Modifies the original data
}
int main() {
int num = 5;
modifyReference(num);
// Output: 10
cout << "After modifyReference, num = " << num << endl;
return 0;
}In the above code, the value of num is modified to 10 because we passed the reference of num, and modifications to x directly affect num.
Choice when solving algorithm problems
Based on experience, if passing basic types like int, bool, etc., passing by value is more common because these types generally do not need to be modified within the function, and the cost of copying is small.
If passing container data structures like vector, unordered_map, etc., passing by reference is more common because it avoids the overhead of copying data copies, and containers generally need to be modified within the function.
Be particularly cautious of a potential issue: when a recursive function has container data structures as parameters, do not use pass by value, otherwise, a data copy will be created with each recursion, consuming a lot of memory and time, which can easily lead to timeout or out-of-memory errors.
Summary
The usage of these basic syntax and data structures can help us complete some basic algorithm exercises, so interested friends can message me to learn together. Your attention is my motivation to keep updating!
This article is reproduced from my SCND blog: students interested in learning can follow my WeChat public account and SCDN blog – Stick man or my Bilibili account – StickMan8
Original link:https://blog.csdn.net/Matchstickmen/article/details/146946485