Skip to main content

C++ Basics

labuladongOriginalAbout 2526 words

This article is intended for beginners and introduces the basic usage of C++, including control statements and commonly used data structures from the standard library, to help you quickly get started with problem-solving.

Standard Output

The standard output in C++ is cout. Use the << operator to send the content you want to print to cout, and endl is used as a newline character.

int a = 10;

// output: 10
cout << a << endl;

// can concatenate output
// output: Hello, World!
cout << "Hello" << ", " << "World!" << endl;

string s = "abc";
// output: abc 10
cout << s << " " << a << endl;

Of course, the printf function in C language 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, with the most common being conditional statements and loops. Below is a brief introduction.

Conditional Statements: 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 > 5

Loops: for/while

Both for and while can be used for loops. A for loop is typically used when the number of iterations is known, while a while loop is generally 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

Common data structures from the standard library are automatically imported on the LeetCode platform. This means you can directly use keywords like vector, set, and map to create data structures when solving algorithm problems.

Dynamic Array vector

vector is a dynamic array in the C++ Standard Library.

In the past, when learning C language, you might have used malloc, int[n] to create static arrays. This method is cumbersome and prone to errors. When solving algorithm problems, we typically use the dynamic array vector, and the input provided in problems is usually of the vector type.

I will explain the differences between dynamic arrays and static arrays in detail in a later section titled Implementing Dynamic Arrays.

vector can be initialized as follows:

#include <vector>

int n = 7, m = 8;

// initialize an empty integer array nums
vector<int> nums;

// initialize an array nums of size n, with default values of 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, with all values set to 2
vector<int> nums(n, 2);

// initialize a two-dimensional integer 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 for vector:

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

int main() {
    int n = 10;
    // array size is 10, all elements 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 the reference to the last element of the array
    // output: 20
    cout << nums.back() << endl;

    // remove the last element of the array (no return value)
    nums.pop_back();
    // output: 10
    cout << nums.size() << endl;

    // can access or modify using square brackets
    nums[0] = 11;
    // output: 11
    cout << nums[0] << endl;

    // insert an element 99 at index 3
    nums.insert(nums.begin() + 3, 99);

    // remove the element at index 2
    nums.erase(nums.begin() + 2);

    // swap nums[0] and nums[1]
    swap(nums[0], nums[1]);

    // iterate over 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 mentioned are the common methods for using C++ vector in this book, which mainly involve accessing elements by index and using push_back and pop_back methods. For solving algorithm problems, these are sufficient.

Due to the characteristics of "arrays," accessing elements using indices is very efficient, as is adding or removing elements from the end. However, adding or removing elements from the middle or the beginning involves shifting data, which is inefficient. The specific reasons will be explained in detail in the later section Array Basics.

Doubly Linked List list

list is a doubly linked list container in the C++ Standard Library.

Initialization method:

#include <list>

int n = 7;

// initialize an empty doubly linked list lst
std::list<int> lst;

// initialize a list lst of size n, with default values of 0
std::list<int> lst(n);

// initialize a list lst containing elements 1, 3, 5
std::list<int> lst{1, 3, 5};

// initialize a list lst of size n, with all values as 2
std::list<int> lst(n, 2);

list 的常用方法：

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

int main() {
    // initialize the list
    list<int> lst{1, 2, 3, 4, 5};

    // check if the list is empty, output: false
    cout << lst.empty() << endl;

    // get the size of the list, output: 5
    cout << lst.size() << endl;

    // insert element 0 at the front of the list
    lst.push_front(0);
    // insert element 6 at the back of the list
    lst.push_back(6);

    // get the front and back elements of the list, output: 0 6
    cout << lst.front() << " " << lst.back() << endl;

    // remove the front element of the list
    lst.pop_front();
    // remove the back element of the list
    lst.pop_back();

    // insert elements into the 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 from the list
    it = lst.begin();
    // move to the second position
    advance(it, 1);
    // remove the element at the second position
    lst.erase(it);

    // iterate through the list
    // output: 1 99 3 4 5
    for (int val : lst) {
        cout << val << " ";
    }
    cout << endl;

    return 0;
}

In general, when we want to add or remove elements at the head, we use a doubly linked list because it is more efficient than a vector for such operations. However, when accessing elements by index, we use a vector.

The characteristics of linked lists and their applicable scenarios compared to dynamic arrays like vector will be introduced in Implementing Linked Lists. Here, we will introduce some of its common APIs.

Queue queue

The queue is a container in the C++ Standard Library based on the First-In-First-Out (FIFO) principle. Queues are suitable for scenarios where elements are added from one end (the back) and removed from the other end (the front).

The implementation principles and use cases of queues will be discussed in later chapters on this site. Here, we will introduce some of its common APIs.

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

int main() {
    // initialize an empty integer queue q
    queue<int> q;

    // add elements to the back 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 front and back elements of the queue, output: 10 and 30
    cout << q.front() << " " << q.back() << endl;

    // remove the front element of the queue
    q.pop();

    // output the new front element: 20
    cout << q.front() << endl;

    return 0;
}

Stack

A stack is a data structure that follows the Last In, First Out (LIFO) principle. It is suitable for scenarios where elements are only added or removed from one end, known as the top of the stack.

stack is a stack container in the C++ Standard Library. The implementation principles and use cases of a stack will be introduced in later sections of this site. Here, we will only cover its common APIs.

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

int main() {

    // initialize an empty integer stack s
    stack<int> s;

    // push elements onto 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;

    // pop the top element of the stack
    s.pop();

    // output the new top element of the stack: 20
    cout << s.top() << endl;

    return 0;
}

Hash Table unordered_map

unordered_map is an implementation of a hash table in the C++ Standard Library. It offers key-value pair storage and supports constant time complexity for operations like lookup, insertion, and deletion of key-value pairs.

Hash tables are classic data structures. I will detail their principles and code implementation in Basics of Hash Tables. Here, I will only introduce its commonly used APIs.

Initialization method:

#include <unordered_map>
using namespace std;

// initialize an empty hash table map
unordered_map<int, string> hashmap;

// initialize a hash table map with some key-value pairs
unordered_map<int, string> hashmap{{1, "one"}, {2, "two"}, {3, "three"}};

The common methods of unordered_map are as follows.

Special Note: Accessing a Non-existent Key Automatically Inserts a Key-Value Pair

In C++ hash tables, if you access a key that does not exist, it will automatically create this key with a default-constructed value.

This behavior is different from other languages and requires special attention. Remember to check if a key exists before accessing its value, otherwise you might unintentionally create a new key, leading to algorithm errors. See the example below for more details.

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

int main() {
    // initialize the hashmap
    unordered_map<int, string> hashmap{{1, "one"}, {2, "two"}, {3, "three"}};

    // check if the hashmap is empty, output: 0 (false)
    cout << hashmap.empty() << endl;

    // get the size of the hashmap, output: 3
    cout << hashmap.size() << endl;

    // check if a specific key exists
    // note that the 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 for a specified key, returns default value if not found
    // output an 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;
    }

    // iterate over the hashmap
    // output (order may vary):
    // 4 -> four
    // 2 -> two
    // 1 -> one
    for (const auto &pair: hashmap) {
        cout << pair.first << " -> " << pair.second << endl;
    }

    // note: accessing a non-existent key will automatically create it
    unordered_map<int, string> hashmap2;

    // the number of key-value pairs is 0
    cout << hashmap2.size() << endl; // 0

    // accessing a non-existent key will automatically
    // create it, with the corresponding value as the default
    cout << hashmap2[1] << endl; // empty string
    cout << hashmap2[2] << endl; // empty string

    // the number of key-value pairs is now 2
    cout << hashmap2.size() << endl; // 2

    return 0;
}

Hash Set unordered_set

The unordered_set is an implementation of a hash set in the C++ Standard Library, used to store unique elements. A common use case is to remove duplicates from a collection.

In later sections of this site, we will introduce the implementation principles and code of hash sets. Here, we will only cover its commonly used APIs.

Initialization methods:

#include <unordered_set>
using namespace std;

// initialize an empty hash set
unordered_set<int> uset;

// initialize a hash set containing some elements
unordered_set<int> uset{1, 2, 3, 4};

Common methods of unordered_set:

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

int main() {
    // initialize the 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 specific 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);

    // remove 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;
    }

    // iterate over 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 two main ways to pass function arguments: pass by value and pass by reference. Understanding the difference between them is crucial for writing efficient algorithm code, especially when dealing with large amounts of data or when the original data needs to be modified.

Pass by Value

Pass by value means that a copy of the function argument is passed to the function. Any modifications made to this copy within the function will not affect the original data.

Here is an example:

#include <iostream>
using namespace std;

void modifyValue(int x) {
    // only modify 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 code above, the value of num does not change after calling modifyValue because a copy of num is passed in, and modifications within the function only affect the copy.

Pass by Reference

Pass by reference means passing the address of an argument to a function, allowing the function to directly manipulate the original data. This means that changes to the parameter will directly affect the original data.

Here is an example:

#include <iostream>
using namespace std;

void modifyReference(int &x) {
             // modify 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 a reference to num, and changes to x inside the function directly affect num.

Choosing Approaches for Algorithm Problems

From my experience, passing by reference is more common when solving algorithm problems. This is because passing by reference allows direct modification of the original data, avoiding the overhead of copying data. Additionally, algorithmic code is usually concise, so errors due to data modification within a function are rare.

One important thing to note is to avoid using pass-by-value for recursive function parameters. Otherwise, each recursion will create a data copy, consuming a lot of memory and time.

Conclusion

The foundational knowledge above is sufficient for you to start practicing problems.

Of course, C++ offers many other data structures with various methods and APIs, which are not covered in this article. Advanced data structures will be introduced gradually in later sections, and the API for each structure can be referenced in documentation as needed, so there's no need to memorize everything at once.

C++ official documentation: https://en.cppreference.com/w/

Next, I will guide you through some LeetCode algorithm problems to quickly apply these data structures and familiarize yourself with the problem-solving system.

Last update: 12/30/2024, 12:33:18 PM
© 2019 - 2024 labuladong