0 From C to C++

C++ is harder to learn than C, where exactly is the difficulty?
A sensuous understanding of the beauty of C++?

Course Content#

Q: Why is the C++ 11 standard the focus of learning?

A: There are significant changes from C++ 03 to 11, while changes from 11 to 14 and 17 are minimal. The 20 standard is very new and not yet widespread, so starting with the C++ 11 standard is a very good choice.

Language Features of C++#

Main Features#

Header files: 130 (C language: 29)
STL
Classes and Objects
Templates
Lambda (C++ 11)
Exception Handling (C++ 11)

Interpretation#

There are many header files, and one cannot rely on just reading header files as a learning method.
STL

Originally not part of the standard header files, developed by the big shots at HP Labs, C++ later incorporated it.

Object-oriented (Classes and Objects)
Generic Programming (Templates): Developing one function is equivalent to developing a hundred functions.
Functional Programming (Lambda)

Compared to the procedural programming paradigm of C, C++ adds three programming paradigms. In engineering projects, generally, 1 to 2 paradigms are used simultaneously, with procedural and object-oriented being more common.
The essential role of new programming paradigms: to improve development efficiency.
- Different programming paradigms correspond to different development efficiencies, considering the time for writing code + testing + maintenance.
- As time goes on, development efficiency may be higher, but the difficulty of writing code also increases.
- The main scenario for using new programming paradigms: can improve development efficiency.
PS: C can also implement object-oriented paradigms, refer to Microsoft's COM in plain C.

Exception Mechanism

A mechanism to recover from certain specific runtime errors that would otherwise cause the program to crash.
Design philosophy: Logic errors in the program should first manifest as compile-time errors, and then as runtime errors.

PS:

After learning C++, if you need to learn Java, you can categorize your learning according to programming paradigms.
C++ inherits the vast majority of features (syntax rules) from C.
- C++ removes some features from C, but they are not critical.

Input and Output Program Comparison [C, C++]#

cin, cout
- No need to specify types (format placeholders).
- Left shift, right shift operators [<<, >>]: involves operator overloading.
printf
- "%lf": defaults to 6 decimal places.
- "%g": outputs all significant digits, following the rules used by cout.
scanf and printf are functions; while cin and cout are not functions, they are objects.
[PS] endl: newline + clear buffer.

STL: Built-in Data Structures#

queue, stack, string, unordered_map, map... compared to implementing these in C, here it conveniently supports any type of elements. For details, see “Interview and Written Test Algorithms” — 5 Using and Practicing STL “Containers”.

deque#

Double-ended queue.
Can implement a monotonic queue; cannot use queue because maintaining monotonicity requires dequeuing from the back. For details, see “Interview and Written Test Algorithms” — 3 Monotonic Queue and Monotonic Stack.

string#

C's strcmp vs C++'s ==.
C's strcat vs C++'s +=.
C's strlen vs C++'s length().
- The implementation principles are somewhat different.
- strlen: must scan the character array from start to end each time until it encounters '\0' --> O(N).
- .length(): member property --> O(1).
substr(pos, n): takes n characters starting from pos.

Based on hash table [unordered]

Amortized time complexity for storage and lookup: O(1).
[C++ 11] unordered_map.
[Before C++ 11, non-standard] hash_map.

Based on red-black tree [ordered]

map.

PS:

Externally resembles an array but is much more powerful.
find(key): returns end() if not found [the end position of the hash table].

Code Demonstration#

Comparison of strlen and length()#

The time taken shows slight differences, but not significant; the original environment may have optimized strlen.
- Refer to Does for(i=0; i<strlen(s); i++) execute strlen every time? — Zhihu.
c_str() — cppplus.

Comparison of map and unordered_map#

First, feel the use of iterators, with type definitions clearly marked, later you can use the auto keyword instead❗.
Orderliness is reflected when traversing elements.
- unordered_map is unordered for both keys and values and will also disrupt the original order.
- map can be used as a sorting tool.
  - Use of the auto keyword.
    - Compare with the previous complete iterator type definition, first feel it out.
    - Very powerful, somewhat like the difference between cin and scanf, can automatically determine the type of iter.
  - Sorting results.
    - Although it looks a bit like counting sort, it is not.
    - Time complexity involves the underlying red-black tree: O(NlogN).

sort#

Demonstrates four programming paradigms of C++.
CMP() is a callable object.
Lambda expressions are a new feature introduced in C++11.
The difference between struct and class here, refer to In-depth Understanding: The Difference Between Struct and Class — Blog.

In-class Exercises#

HZOJ-245: Warehouse Location Selection#

Sample Input

5
1 3 5 6 10

Sample Output

Thought Process
- Note: Input may be unordered.
- Problem Transformation
  - Randomly select a point p, the current total distance is s1.
  - When point p moves a small distance Δ, the total distance s2 = s1 + (n1 - n2) * Δ.
    - n1: number of stores to the left of point p; n2: number of stores to the right of point p.
  - 【Goal】s2 < s1.
    - When n1 - n2 < 0, Δ > 0 --> s2 < s1: when there are more stores on the right, moving point p to the right can yield a better solution.
    - When n1 - n2 > 0, Δ < 0 --> s2 < s1: when there are more stores on the left, moving point p to the left can yield a better solution.
  - 【Final Goal】n1 = n2, so find the coordinate of the n / 2-th element.
    - n is the total number of stores, with indexing starting from 0.
Code
- Solution 1: sort method.
  - The main time consumption is in input and summation.
  - For details on sort usage, see “Interview and Written Test Algorithms” — 2 Binary Search Topic — Additional Knowledge Points, the termination position is the next position of the last element.
- Solution 2: nth_element method.
  - nth_element
    - Based on Quick Select Algorithm — Zhihu, borrowing from the partition process of quicksort, but does not sort the entire sequence.
    - After execution, the 【k-th position holds the k-th smallest element in ascending order】❗.
  - Small Assignment: For usage methods and techniques of nth_element, see link.
- Method Comparison
  - Solution 1: complete sorting.
  - Solution 2: partial sorting, directly obtaining the k-th position.

HZOJ-166: String Manipulation 1#

Sample Input

AAAAAA
2
xxx

Sample Output

6
AxxxAAAAA
6

Thought Process
- Examines string manipulation and common methods.
- Insert string B into string A.
Code
- string class
  - size() and length() are the same.
  - insert.
  - rfind.
    - Searches from the right but returns its index (in the forward direction).
    - In this scenario, you can also use find_last_of method, focusing on matching any character in the string. Refer to the difference between string's find and find_first_of — Geek Share.
- Small Assignment: For more uses of string, see link.

HZOJ-216: Get Names and Sort#

Sample Input

5
Mr.DMY
Mr.ZY
Mr.LYH
Ms.Grace
Mr.Bill

Sample Output

Bill
DMY
Grace
LYH
ZY

Thought Process
- Can use sort.
- Can also use map structure, which is based on a red-black tree, sorted by key by default.
Code
- Using map.
- Understand the use of iterator iter, where ->first represents the key and ->second represents the value.
- Note
  - Need to first extract the names.
  - The value is used for counting, as names may be duplicated.

HZOJ-287: Merge Fruits#

Sample Input

3
1 2 9

Sample Output

Thought Process
- Initially, the smaller the better, so a minimum heap can be used.
- Small Assignment: Discuss the relationship between merging fruits and Huffman coding, see link.
Code
- priority_queue
  - It is a template, with types placed in <> and defaults to a max heap.
  - To change it to a min heap, you need to first define the container type: vector; then,
    - Method 1: Define a CMP class, overload the () operator to make it callable (i.e., functor).
    - Method 2, Method 3: Use template classes, to be learned later.

HZOJ-256: King's Game#

Sample Input

Sample Output

Thought Process
- Goal: Find the minimum of the maximum value.
- The algorithm thinks: perturbation.
  - Let
    - The sequence of numbers in everyone's left hand be $a_0,a_1,a_2,...,a_i,...,a_n$,
    - The sequence of numbers in everyone's right hand be $b_0,b_1,b_2,...,b_i,...,b_n$,
    - The product of the numbers in the left hand of all the ministers in front of this minister is $A_{i-1}=a_0*...*a_{i-1}$,
  - Then
    - The number of gold coins each minister receives is $G_i=A_{i-1}/b_i$.
  - Suppose there is a permutation 1 of
    - $G_1,G_2,...,[G_{i-1},G_i],...,G_n$, where $G_i$ is the maximum.
  - At this time, if the positions of two adjacent ministers are swapped, i.e., $(a_{i-1},b_{i-1})$ and $(a_i,b_i)$, a new permutation 2 is generated.
    - $G_1,G_2,...,[G_{i}^{'} ,G_{i-1}^{'}],...,G_n$.
    - ❗ Which is closer to the goal, permutation 1 or permutation 2? Just focus on the relationship between the changed gold coins $G_{i}^{'},G_{i-1}^{'}$ and the maximum gold coins $G_i$. If both are less than, then permutation 2 is closer to the goal.
  - Analysis
    - Only the gold coins of the two ministers being swapped change.
      - Known: $G_i=A_{i-1}/b_i$.
      - After swapping: $G_{i}^{'}=A_{i-2}/b_i$, $G_{i-1}^{'}=A_{i-2}*a_i/b_{i-1}$.
    - It is easy to see that $G_{i}^{'}<G_{i}$,
    - And if $G_{i-1}^{'}<G_i$ also holds, then permutation 2 is closer to the goal, i.e.,
      - $G_{i-1}^{'}<G_i$.
      - ↓
      - $A_{i-2}*a_i/b_{i-1}<A_{i-1}/b_{i}$.
      - ↓
      - $A_{i-2}*a_i/b_{i-1}<A_{i-2}*a_{i-1}/b_{i}$.
      - ↓
      - $a_i*b_{i}<a_{i-1}*b_{i-1}$.
  - 👉 Condition for ministers to swap positions:
    - $a_i*b_{i}<a_{i-1}*b_{i-1}$.
Code
- Algorithm: Based on the idea of perturbation, design a sorting rule.
  - Use pair type to conveniently organize the numbers in the left and right hands.
  - The king is always at the front and does not participate in sorting.
- ⭐ Data Structure: Big Integers.
  - Encapsulate a method to handle carry separately, using once at the end of multiplication and division processes.
  - ❓ Can directly use push_back() in the constructor, focus on this in future learning.
  - The design of division mainly utilizes remainders, which may produce leading zeros, so it needs to be handled.
  - ❓ Overloading the less-than operator requires adding const at the end of the method, otherwise it will not take effect, and may prioritize using vector's less-than comparison, the specific reason will be learned later.
- PS: Here, the data structure and algorithm are truly separated, which is also an advantage of object-oriented programming over procedural programming.

Tips#

Not only should you know the reasons, but also understand the multiple reasons behind them.
There are no standard answers in learning C++, so discuss more with each other.
Learn to check cppreference.
Recommendations
- Books: C++ Primer, Effective C++, Deep Exploration of C++ Object Model...
- Videos: Teacher Hou Jie.
  - Learn C++ comprehensively to enhance skills — C++ Development Engineer (2016).
  - Link: https://pan.baidu.com/s/1G7v0w4nH64SVH1FpE5czzQ.
  - Extraction code: y8tu.

0 From C to C++

Course Content#

Language Features of C++#

Main Features#

Interpretation#

Input and Output Program Comparison [C, C++]#

STL: Built-in Data Structures#

deque#

string#

Related to map#

Code Demonstration#

Comparison of strlen and length()#

Comparison of map and unordered_map#

sort#

In-class Exercises#

HZOJ-245: Warehouse Location Selection#

HZOJ-166: String Manipulation 1#

HZOJ-216: Get Names and Sort#

HZOJ-287: Merge Fruits#

HZOJ-256: King's Game#

Tips#