Appendix B
C++ comparison
In this chapter
Purpose
The main chapters and laboratories use C11. This appendix shows the same pair-counting idea in C++17 so that C++ examination material can be read without mixing language syntax into the C implementations.
B.1 The algorithm stays the same
An inversion has i < j and a[i] > a[j]. The following C++ program stores four values in std::array, compares every pair, checks the answer and prints it.
#include <array>
#include <cassert>
#include <cstddef>
#include <iostream>
int main()
{
const std::array<int, 4> a{8, 4, 2, 1};
std::size_t inversions = 0;
for (std::size_t i = 0; i < a.size(); ++i) {
for (std::size_t j = i + 1; j < a.size(); ++j) {
if (a[i] > a[j]) {
++inversions;
}
}
}
assert(inversions == 6);
std::cout << "Inversions: " << inversions << '\n';
}
Time is Θ(n²), with Θ(1) extra scalar workspace for this pair-counting method. For large n, the chosen count type must hold up to n(n − 1)/2. The fixed four-element demonstration has no overflow risk.
B.2 Keep the language boundaries explicit
| C11 | C++17 |
|---|---|
printf from <stdio.h> |
Stream output with std::cout from <iostream> |
struct Node * unless a typedef exists |
A declared structure name may be used directly as a type |
malloc / free for raw allocated storage |
Constructors/destructors and RAII support managed object lifetimes |
| No C++ reference types or classes | References and classes are language features |
Do not mix malloc with delete, or new with free. Prefer ownership-aware C++ containers and resource management rather than copying a C allocation pattern mechanically. The ADT invariants—LIFO, FIFO, BST ordering—remain meaningful in both languages.
Practice
- Change the array to
{1, 3, 2, 4}and predict the inversion count before running it. - Why does changing
>to>=alter the definition when duplicate values occur?
Programming laboratory
Download inversions.cpp · Contracts and run instructions
Compile this file on its own. Check the empty, boundary and ordinary cases before changing the implementation.
Read the complete C++17 program
#include <array>
#include <cassert>
#include <cstddef>
#include <iostream>
int main()
{
const std::array<int, 4> a{8, 4, 2, 1};
std::size_t inversions = 0;
for (std::size_t i = 0; i < a.size(); ++i) {
for (std::size_t j = i + 1; j < a.size(); ++j) {
if (a[i] > a[j]) {
++inversions;
}
}
}
assert(inversions == 6);
std::cout << "Inversions: " << inversions << '\n';
}