Modern C++ Programming Best Practices and Pitfalls: A Comprehensive Overview

L

a

b

2

Feedback from Lab 1, C-strings, memory management,

common C++ mistakes, archaic vs modern C++

9

. 10. 2023

O

u

t

l

i

n

e

2023/2024

Programming in C++ (labs)

2

•

Feedback

 from Lab 1

•

Task 2 introduction

•

Brief overview of C-strings/std::string/std::string_view

•

Brief overview of smart vs raw pointers

•

Pitfalls of using old C++/C constructs

•

Do not use prinft in modern C++

•

Task 2 coding

L

a

b

1

:

C

+

+

s

t

a

c

k

v

s

h

e

a

p

a

l

l

o

c

a

t

i

o

n

2023/2024

Programming in C++ (labs)

3

•

In contrast to other languages, C++ gives you full control over where your

variables are allocated

•

Stack vs heap

•

B

y

d

e

f

a

u

l

t

y

o

u

d

o

n

'

t

u

s

e

t

h

e

n

e

w

k

e

y

w

o

r

d

t

o

a

l

l

o

c

a

t

e

o

n

t

h

e

s

t

a

c

k

.

•

Keyword new allocates on the heap and returns a pointer.

•

In modern C++, new keyword should be avoided

•

 Containers or smart pointers shall do allocation.

int

 a;

 // Stack

int

*

 p_a 

=

new

int

();

 // Heap

array

<

int

, 

3

>

 arr;

 // Stack

array

<

int

, 

3

>*

 p_arr 

=

new

array

<

int

, 

3

>();

 // Heap

string 

s

(

"Hey"

);

 // Stack

string

*

 p_s 

=

new

string

(

"Hey"

);

 // Heap

•

What is going on here?

•

How to compare C-strings?

char*

const char*

ptr compare

std::string

const char*

thanks to std::string on the

left, it looks for operator==

implementation on

std::string

ctor const char* -> std::string: 

https://en.cppreference.com/w/cpp/string/basic_string/basic_string

cmp of std::string + std::string: 

https://en.cppreference.com/w/cpp/string/basic_string/operator_cmp

F

u

r

t

h

e

r

r

e

a

d

i

n

g

No such overload exists, but

there is an implicit

conversion from const char*

to std::string

C function strcmp.

L

a

b

1

:

W

e

u

s

e

d

a

u

t

o

&

&

?

2023/2024

Programming in C++ (labs)

5

•

l

v

a

l

u

e

•

Denotes an object that you can repeatedly access from your program.

•

named variables, array elements, members

An lvalue reference (&) binds to an lvalue.

int i = 10;

int& ri = &i;

•

r

v

a

l

u

e

•

If it is not lvalue, then it's rvalue.

•

D

e

n

o

t

e

s

a

n

o

b

j

e

c

t

t

h

a

t

c

a

n

n

o

t

b

e

a

c

c

e

s

s

e

d

i

n

y

o

u

r

c

o

d

e

a

n

d

t

h

u

s

i

t

s

r

e

s

o

u

r

c

e

s

c

a

n

b

e

r

e

u

s

e

d

.

•

Usually, temporary objects!

An rvalue reference (&&) binds to an rvalue.

MyClass( 

vector<int>{1, 2 } 

)

const int& x = 

foo()

; // int foo();

https://www.fluentcpp.com/2018/02/06/understanding-lvalues-rvalues-and-their-references/

https://en.cppreference.com/w/cpp/language/value_category

F

u

r

t

h

e

r

r

e

a

d

i

n

g

// Range-based for loop

for

 (

auto

&&

 x : xs)

    cout 

<<

 x 

<<

 endl;

void

foo

(

const

vector

<

int

>

&

xs

) { cout 

<<

"lvalue"

<<

 endl; }

vector

<

int

>

 xs 

=

vector

<

int

>({ 

1

,

2

,

3

 });

foo

(

vector

<

int

>({ 

1

,

2

,

3

 })); 

// lvalue

, but arg is rvalue

foo

(xs);

 // 

l

value

void

foo

(

vector

<

int

>

&&

xs

) { cout 

<<

"rvalue"

<<

 endl; }

void

foo

(

const

vector

<

int

>

&

xs

) { cout 

<<

"lvalue"

<<

 endl; }

vector

<

int

>

 xs 

=

vector

<

int

>({ 

1

,

2

,

3

 });

foo

(

vector

<

int

>({ 

1

,

2

,

3

 })); 

// rvalue

foo

(xs);

 // lvalue

Without the rvalue overload

With the rvalue overload

Wait, how is this useful?

rvalue reference

overload preferred

P

e

r

f

o

r

m

a

n

c

e

!

Move semantics -> future labs

// Range-based for loop

for

 (

auto

&&

 x : xs)

    cout 

<<

 x 

<<

 endl;

for

 (

const

int

&

 x : xs)

    cout 

<<

 x 

<<

 endl;

for

 (

int

&

 x : xs)

    cout 

<<

 x 

<<

 endl;

for

 (

int

 x : xs)

    cout 

<<

 x 

<<

 endl;

Use for range-based for loops where

you don't care about modifying the

items -> concise syntax

Later use it in templates…

L

a

b

1

:

M

i

n

o

r

t

h

i

n

g

s

2023/2024

Programming in C++ (labs)

8

•

Good

•

Decomposition of code to smaller functions

•

ternary if operator

•

<bool expr> ? <true expr> : <false expr>

•

It is an expression and thus it has value.

•

Not ideal

•

Manual indexing to containers

•

One solution used at least checked boundaries 

xs.at(i)

•

Using C function printf

•

Initialising bool variables with int literal (implicit conversion to bool).

•

#include <stdio.h>

•

Prefer C++ constructs

•

If you really have to, include C libs wrapped in STD namespace -> #include <cstdio>

•

Put tasks from labs (micro-homeworks) into "labs" directory.

•

Naming C++ files with suffixes .cpp, .h, .hpp …

•

Modules: .ixx, .cppm, and .cxx

// Using reverse iterators (without C++20 ranges)

for

 (

auto

 it 

=

xs

.

rbegin

(); it 

!=

xs

.

rend

(); 

++

it)

    cout 

<<

*

it 

<<

 endl;

// Using C++20 ranges with pipe syntax

for

 (

auto

&&

 x : (xs 

|

views

::reverse))

    cout 

<<

 x 

<<

 endl;

// Using C++20 ranges without pipes

for

 (

auto

&&

 x : 

ranges

::

reverse_view

(xs))

    cout 

<<

 x 

<<

 endl;

// Reverse iteration over the container

for

 (

int

 i 

=

prefix

.

size

() 

-

1

; i 

>=

0

; i

--

) {

    cout 

<<

prefix

[i] 

<<

" "

;

}

c

a

d

g

i

data()

size()

b

h

char

 a[] = 

"a

ho

y"

;

const char

* b = 

"

aho

y"

;

char

* c = a;

string

 d(

"ahoy"

);

string

 e(a);

string_view 

g(

"ahoy"

);

string_view 

h(

c

);

string_view 

i(

d

);

raw pointer to

 C-string

array of char

≡ 

C-string

non-owning view

Do not use if not necessary

e

B

r

i

e

f

l

y

:

T

y

p

i

c

a

l

u

s

a

g

e

o

f

s

t

r

i

n

g

s

a

n

d

s

t

r

i

n

g

v

i

e

w

s

Programming in C++ (labs)

11

void

foo

(

string_view

s

){ .... }

string

x

(

"ahoy"

);

string

y

(

x

);

f

(x);

f

(y);

f

(

"ahoy"

);

typical usage:

std::

string 

ctor with variable

/C-string literál

implicit conversion std::string -> std::string_view

You can concatenate

std::strings with operator+

std::string x = a + b + c

string

a

(

"Hey"

);

string

b

(

"there"

);

string s 

=

 a 

+

" "

+

 b 

+

"!"

;

overloaded operator+

for std::string

B

r

i

e

f

l

y

:

S

m

a

r

t

p

o

i

n

t

e

r

v

s

r

a

w

p

o

i

n

t

e

r

2023/2024

Programming in C++ (labs)

12

S

m

a

r

t

p

o

i

n

t

e

r

s

•

They take ownership of their memory seriously and will deallocate once when no

one is using the memory.

•

No double frees or memory leaks.

•

They are usually as performant as raw pointers.

•

Whenever possible, use std::unique_ptr -> next lab

R

a

w

p

o

i

n

t

e

r

s

•

You may think they take ownership seriously, but they couldn't be bothered.

•

If you don't delete the memory, no one will -> memory leak.

•

If you delete the memory twice, anything can happen (UB).

•

Use them only as non-owning observer pointers

W

h

a

t

c

o

u

l

d

g

o

w

r

o

n

g

?

2023/2024

Programming in C++ (labs)

13

•

The answer is, almost everything!

•

The worst nightmares of a C++ programmer:

•

M

e

m

o

r

y

l

e

a

k

s

–

u

n

u

s

e

d

h

e

a

p

m

e

m

o

r

y

o

n

w

h

i

c

h

t

h

e

r

e

w

a

s

n

’

t

c

a

l

l

e

d

d

e

l

e

t

e

•

You can go OOM (not Out Of Mana, Out Of Memory)

•

D

o

u

b

l

e

f

r

e

e

s

–

a

l

l

o

c

a

t

e

d

m

e

m

o

r

y

o

n

w

h

i

c

h

t

h

e

r

e

w

a

s

c

a

l

l

e

d

d

e

l

e

t

e

m

o

r

e

t

h

a

n

o

n

c

e

•

Undefined Behaviour

•

D

e

r

e

f

e

r

e

n

c

i

n

g

i

n

v

a

l

i

d

p

o

i

n

t

e

r

•

Segmentation fault or you read garbage data and may not notice.

•

R

e

a

d

i

n

g

u

n

i

n

i

t

i

a

l

i

z

e

d

m

e

m

o

r

y

•

You’re using garbage data but it is not always obvious.

•

B

u

f

f

e

r

o

v

e

r

f

l

o

w

s

–

C

a

r

r

a

y

s

/

C

-

s

t

r

i

n

g

s

h

a

v

e

n

o

b

o

u

n

d

s

c

h

e

c

k

i

n

g

a

n

d

w

i

l

l

l

e

t

y

o

u

w

r

i

t

e

o

u

t

s

i

d

e

o

f

i

t

w

i

t

h

o

u

t

e

v

e

n

b

l

i

n

k

i

n

g

•

M

e

m

o

r

y

c

o

r

r

u

p

t

i

o

n

-

A

c

c

i

d

e

n

t

l

y

r

e

w

r

i

t

i

n

g

b

y

t

e

s

o

f

y

o

u

r

o

t

h

e

r

s

t

r

u

c

t

u

r

e

s

.

https://msrc.microsoft.com/blog/2019/07/a-proactive-approach-to-more-secure-code/

https://www.chromium.org/Home/chromium-security/memory-safety/

T

h

e

s

e

p

r

o

b

l

e

m

s

a

r

e

r

e

a

l

Working with garbage data

and now knowing is …

~70% of serious bugs is related

to memory management

W

h

a

t

a

b

o

u

t

C

-

s

t

r

i

n

g

s

a

n

d

p

r

i

n

t

f

?

2023/2024

Programming in C++ (labs)

14

•

Yes, C-string functions are very unsafe and there is always some UB waiting around the corner.

•

Invalid 

n

ull 

t

ermination

•

Going past the null terminating byte

•

Unmatching buffer sizes

•

Unsafe printf

•

Illegal format string

•

Not enough arguments for format specifier

char

 str[

5

];

str[

0

] = 

'H’

;

str[

1

] = 

'i'

; 

// Forgot to null-terminate

// Any operation expecting null-termination is UB

char

 str[] = 

"hello"

;

for

(

int

 i = 

0

; i <= 

10

; ++i) {

    char

 c = str[i];

 // Undefined behavior when i > 5

}

char

 dest[

5

];

strncpy

(dest, 

"hello, world"

, 

12

); 

// No space for null-terminator

printf

("%d %s\n"

, 10

); 

// 

UB, missing arguments

printf

("%d"

, 

3.14f

);

 // UB

,

conversion specification is invalid

M

o

d

e

r

n

C

+

+

f

o

r

t

h

e

r

e

s

c

u

e

!

2023/2024

Programming in C++ (labs)

15

•

 The good news is that modern C++ can help with these.

•

The worst nightmares of a C++ programmer:

•

M

e

m

o

r

y

l

e

a

k

s

&

d

o

u

b

l

e

f

r

e

e

s

–

s

m

a

r

t

p

o

i

n

t

e

r

s

•

D

e

r

e

f

e

r

e

n

c

i

n

g

i

n

v

a

l

i

d

p

o

i

n

t

e

r

–

s

m

a

r

t

p

o

i

n

t

e

r

s

+

o

b

s

e

r

v

e

r

p

o

i

n

t

e

r

s

•

The observer pointers are still dangerous if the programmer is not cautious.

•

R

e

a

d

i

n

g

u

n

i

n

i

t

i

a

l

i

z

e

d

m

e

m

o

r

y

–

c

o

n

t

a

i

n

e

r

s

•

Containers do not force us to initialize, but at least give us an easy interface to do so.

•

B

u

f

f

e

r

o

v

e

r

f

l

o

w

s

–

c

o

n

t

a

i

n

e

r

s

&

i

t

e

r

a

t

o

r

s

•

M

e

m

o

r

y

c

o

r

r

u

p

t

i

o

n

-

c

o

n

t

a

i

n

e

r

s

&

i

t

e

r

a

t

o

r

s

•

raw arrays do not know their size, containers do know!

•

M

i

s

s

i

n

g

n

u

l

l

s

t

r

i

n

g

t

e

r

m

i

n

a

t

i

o

n

–

s

t

d

:

:

s

t

r

i

n

g

i

s

n

o

t

n

u

l

l

-

t

e

r

m

i

n

a

t

e

d

,

i

t

k

n

o

w

s

t

h

e

s

i

z

e

•

G

o

i

n

g

p

a

s

t

t

h

e

n

u

l

l

t

e

r

m

i

n

a

t

i

n

g

b

y

t

e

–

N

o

t

p

o

s

s

i

b

l

e

i

f

u

s

i

n

g

i

t

e

r

a

t

o

r

s

.

•

U

n

m

a

t

c

h

i

n

g

b

u

f

f

e

r

s

i

z

e

s

–

T

h

e

c

o

p

y

i

n

g

i

s

h

a

n

d

l

e

d

b

y

t

h

e

l

i

b

r

a

r

y

-

d

e

f

i

n

e

d

o

p

e

r

a

t

o

r

s

.

•

U

n

s

a

f

e

p

r

i

n

t

f

–

M

u

c

h

h

a

r

d

e

r

t

o

m

e

s

s

s

o

m

e

t

h

i

n

g

w

i

t

h

s

t

d

:

:

c

o

u

t

,

s

t

d

:

:

f

o

r

m

a

t

(

C

+

+

2

0

)

,

a

n

d

s

t

d

:

:

p

r

i

n

t

(

C

+

+

2

3

)

•

Additionally, you get very nice and unified interface and utility functions on those classes

•

std::string – contains, starts_with, ends_with, (r)find, operator+

•

u

n

i

q

u

e

_

p

t

r

,

s

h

a

r

e

d

_

p

t

r

–

t

h

e

y

b

e

h

a

v

e

a

l

m

o

s

t

l

i

k

e

d

r

o

p

-

i

n

r

e

p

l

a

c

e

m

e

n

t

s

f

o

r

r

a

w

p

o

i

n

t

e

r

s

T

a

s

k

2

:

L

e

t

'

s

c

o

d

e

2023/2024

Programming in C++ (labs)

16

•

Takes an arbitrary number of ASCII strings from STDIN separated by a newline until the ‘=

END

=‘.

•

The program builds a BST from these strings for subsequent searches

•

Case insensitive, no duplicates in the tree.

•

The tree is not guaranteed to be balanced. It does not matter for our cause.

•

After that, the program waits for newline-separated input from STDIN in a loop.

•

Upon getting some input, the program shall find if the string is in the BST.

•

I

f

y

e

s

,

i

t

s

h

a

l

l

d

e

l

e

t

e

t

h

e

n

o

d

e

a

n

d

o

u

t

p

u

t

i

t

s

v

a

l

u

e

t

o

S

T

D

O

U

T

(

p

r

e

f

i

x

e

d

w

i

t

h

"

D

:

"

)

;

o

t

h

e

r

w

i

s

e

,

i

t

s

h

a

l

l

d

o

n

o

t

h

i

n

g

.

•

T

h

e

r

e

’

s

a

c

a

t

c

h

t

h

o

u

g

h

.

Y

o

u

m

u

s

t

i

m

p

l

e

m

e

n

t

i

t

w

i

t

h

o

u

t

C

+

+

s

t

r

i

n

g

a

n

d

s

m

a

r

t

p

o

i

n

t

e

r

s

.

Hints:

•

#include 

<cstring>

, str(n)cpy, str(n)cat, strlen, str(n)cmp

C

o

d

e

:

T

h

e

p

r

o

b

l

e

m

a

p

p

r

o

a

c

h

2023/2024

Programming in C++ (labs)

17

•

BST is a binary tree (no duplicates).

•

R

o

o

t

e

d

,

e

a

c

h

n

o

d

e

h

a

s

a

t

m

o

s

t

t

w

o

c

h

i

l

d

r

e

n

(

l

e

f

t

,

r

i

g

h

t

)

.

•

For each node:

•

The left subtree contains only smaller items.

•

The right subtree contains only greater items.

•

Strings in C/C++ use 

lexicographical ordering

.

•

Beware that you must have the same case to achieve

alphabetic

al

 ordering!

•

E.g. "B" < "a" < "b"

https://en.wikipedia.org/wiki/Binary_search_tree

https://pruvodce.ucw.cz/

 (kapitola Bin

ární vyhledávací stromy

)

F

u

r

t

h

e

r

r

e

a

d

i

n

g

h

ey

h

ey

j

ude

,

don

’

t

m

ake

it

bad.

=

end

=

j

ude,

don

’

t

make

it

bad.

C

o

d

e

:

R

e

p

r

e

s

e

n

t

t

h

e

n

o

d

e

s

&

e

d

g

e

s

2023/2024

Programming in C++ (labs)

18

•

struct Node

•

Node* p_left

•

Node* p_right

•

char*

 data

•

We will traverse it from the root

•

The whole tree is represented by the root Node

h

ey

h

ey

j

ude

,

don

’

t

m

ake

it

bad.

=

end

=

j

ude,

don

’

t

make

it

bad.

struct Node

Node*

stack

heap

This is not accurate the C-strings in the

nodes are allocated somewhere else on

the heap as well

data

h

ey

…

…

Node*

I

n

t

e

r

m

e

z

z

o

:

t

y

p

e

s

p

e

c

i

f

i

e

r

a

u

t

o

2023/2024

Programming in C++ (labs)

19

•

N

o

d

y

n

a

m

i

c

t

y

p

e

s

!

A

l

l

t

y

p

e

s

m

u

s

t

b

e

k

n

o

w

n

a

t

c

o

m

p

i

l

e

t

i

m

e

!

•

The keyword auto just says "Please compiler, just deduce the type for me"

•

E.g. based on the expression on the right

•

Necessary to define the type of lambdas (later labs…)

•

The compilers get more powerful with their deduction capabilities over time.

•

Saves you keystrokes!

https://en.cppreference.com/w/cpp/language/auto

F

u

r

t

h

e

r

r

e

a

d

i

n

g

since C++11

// Without auto

vector

<

map

<

size_t

, unique_ptr

<

double

>>>

 names;

vector

<

map

<

size_t

, 

unique_ptr

<

double

>>>::iterator it 

=

names

.

begin

();

// With auto

vector

<

map

<

size_t

, unique_ptr

<

double

>>>

 names;

auto

 it 

=

names

.

begin

();

I

n

t

e

r

m

e

z

z

o

:

n

u

l

l

p

t

r

2023/2024

Programming in C++ (labs)

20

•

Since C++11 we have the nullptr keyword.

•

I

t

r

e

p

r

e

s

e

n

t

s

a

n

u

l

l

/

i

n

v

a

l

i

d

p

o

i

n

t

e

r

b

u

t

h

a

s

t

h

e

c

o

r

r

e

c

t

p

o

i

n

t

e

r

t

y

p

e

.

•

R

e

a

d

a

b

i

l

i

t

y

•

T

y

p

e

s

a

f

e

t

y

•

Use it to represent invalid/null pointers.

•

Avoid C approaches - 0 (int) or NULL (preprocessor define)

https://www.modernescpp.com/index.php/the-null-pointer-constant-nullptr/

https://en.cppreference.com/w/cpp/language/nullptr

F

u

r

t

h

e

r

r

e

a

d

i

n

g

since C++11

I

n

t

e

r

m

e

z

z

o

:

t

u

p

l

e

/

p

a

i

r

2023/2024

Programming in C++ (labs)

21

•

Heterogeneous container with known size at compile-time.

https://en.cppreference.com/w/cpp/utility/tuple

F

u

r

t

h

e

r

r

e

a

d

i

n

g

since C++11

pair

<

bool

, 

double

> 

p

(

false

, 

3.6

);

tuple

<

int

, 

float

, 

char

> 

t

(

10

, 

20.0f

, 

'x'

);

p

.

first

;

 // first item, not method!

p

.

second

;

 // second item, not method!

get

<

0

>(p);

 // first item

get

<

1

>(p);

 // second item

get

<

0

>(t);

 // first item

get

<

1

>(t);

 // second item

get

<

1

>(t);

 // third item

get

<

3

>(t);

 // ERROR: Compile-time check

// since C++17

tuple

<

int

, 

float

, 

char

> 

foo

() {

return

tuple

(

10

, 

20.0f

, 

'x'

);

}

// since C++11

tuple

<

int

, 

float

, 

char

> 

foo

() {

return

make_tuple

(

10

, 

20.0f

, 

'x'

);

}

Stronger type deduction

Helper functions,

make_*

#include <tuple>

I

n

t

e

r

m

e

z

z

o

:

s

t

r

u

c

t

u

r

e

d

b

i

n

d

i

n

g

s

2023/2024

Programming in C++ (labs)

22

•

Simple way to unpack tuple-like, array or struct types.

https://en.cppreference.com/w/cpp/language/structured_binding

https://devblogs.microsoft.com/oldnewthing/20201014-00/?p=104367

F

u

r

t

h

e

r

r

e

a

d

i

n

g

since C++17

// Array

int

a

[

2

] 

=

 {

1

, 

2

};

auto

 [x, y] 

=

 a;

    // x == 1, y == 2

auto

&

 [xr, yr] 

=

 a;

  // xr refers to a[0], yr refers to a[1]

// Tuple-like

tuple

<

float

, 

char

, 

int

> 

tpl

(

0.2f

, 

'a'

, 

42

);

auto

 [a, b, c] 

=

 tpl;

auto

&

 [ar, br, cr] 

=

 tpl;

// Struct types

struct

S

 {

int

 x1;

double

 y1;

};

S

f

() { 

return

 S{ 

1

, 

2.3

 }; }

auto

 [i, j] 

=

f

();

const

auto

&

 [icr, rcr] 

=

f

();

auto

&

 [ir, jr] 

=

f

();

 // Invalid

Other languages may call this

unpacking, deconstructing,

destructuring

// Existing variables

int

 a 

=

0

;

double

 b 

=

0.0

;

char

 c 

=

' '

;

// Some tuple

tuple

<

int

, 

double

, 

char

>

 t 

=

make_tuple

(

42

, 

3.14

, 

'x'

);

// Unpack the tuple into existing variables

tie

(a, b, c) 

=

 t;

With existing variables, you can

fill them with std::tie

I

n

t

e

r

m

e

z

z

o

:

s

t

d

:

:

o

p

t

i

o

n

a

l

2023/2024

Programming in C++ (labs)

23

•

T

y

p

e

r

e

p

r

e

s

e

n

t

i

n

g

a

v

a

l

u

e

o

f

t

y

p

e

T

O

R

n

o

t

h

i

n

g

/

n

u

l

l

/

n

o

v

a

l

u

e

https://en.cppreference.com/w/cpp/utility/optional

F

u

r

t

h

e

r

r

e

a

d

i

n

g

since C++17

optional

<

string

> 

create

(

bool

b

) {

if

 (b)

return

"Godzilla"

;

return

 nullopt;

}

cout 

<<

"create(false) returned "

<<

create

(

false

).

value_or

(

"empty"

) 

<<

 endl;

cout 

<<

"create(false) returned "

<<

*

create

(

false

) 

<<

 endl;

 // UB, cannot get the value

// True if optional is not null

if

 (

auto

 str 

=

create

(

true

))

    cout 

<<

"create2(true) returned "

<<

*

str 

<<

 endl;

Use for types, where "empty" is

a valid state

#include <optional>

C

o

d

e

:

P

r

i

n

t

t

r

e

e

2023/2024

Programming in C++ (labs)

24

•

Prints all the values in their order

•

It means, in order if you scan from left to right

in symmetric tree

•

print_tree(p_root)

•

print_tree(p_root->left)

•

print(p_root->val)

•

print_tree(p_root->right)

h

ey

h

ey

j

ude

,

don

’

t

m

ake

it

bad.

=

end

=

j

ude,

don

’

t

make

it

bad.

struct Node

stack

heap

Node*

You can concatenate

std::vectors with xs.insert()

vector

<

int

>

a

({ 

1

, 

2

, 

3

 });

vector

<

int

>

b

({ 

3

, 

4

, 

5

 });

// Taking copies

a

.

insert

(

a

.

end

(), 

b

.

begin

(), 

b

.

end

());

// With move semantics

a

.

insert

(

a

.

end

(), 

make_move_iterator

(

b

.

begin

()), 

make_move_iterator

(

b

.

end

()));

C

o

d

e

:

B

u

i

l

d

i

n

g

t

h

e

t

r

e

e

2023/2024

Programming in C++ (labs)

25

•

In a loop reading STDIN until line "=END="

•

We start with 

Node* tree = nullptr

•

With each word, allocate Node with new  and attach it

•

smaller -> go/attach left

•

greater -> go/attach right

•

Compare C-strings with 

strcmp

h

ey

h

ey

j

ude

,

don

’

t

m

ake

it

bad.

=

end

=

j

ude,

don

’

t

make

it

bad.

struct Node

stack

heap

Node*

// Convert ASCII string to lowercase

string

s

(

"HeLlO!"

);

for

 (

char

&

 c : s)

    c 

=

tolower

(

static_cast

<

unsigned

char

>

(c));

Parameter of tolower

must be representable

by unsigned char

char can be both signed or

unsinged (impl-defined)

unsigned char, signed char

uint8_t, int8_t

C

o

d

e

:

D

e

l

e

t

e

o

p

e

r

a

t

i

o

n

2023/2024

Programming in C++ (labs)

26

•

Find what to delete

•

with a pointer to the parent

•

with "am I left/right child" indicator

•

D

R

Y

–

D

o

n

'

t

r

e

p

e

a

t

y

o

u

r

s

e

l

f

•

Find a successor of a node

•

with a pointer to the parent

•

with "am I left/right child" indicator

h

ey

h

ey

j

ude

,

don

’

t

m

ake

it

bad.

=

end

=

j

ude,

don

’

t

make

it

bad.

struct Node

stack

heap

Node*

C

o

d

e

:

F

i

n

d

i

n

g

n

o

d

e

'

s

d

i

r

e

c

t

p

r

e

d

e

c

e

s

s

o

r

/

s

u

c

c

e

s

s

o

r

2023/2024

Programming in C++ (labs)

27

•

P

r

e

d

e

c

e

s

s

o

r

:

•

The maximum from the left subtree

•

The "rightest" node in the left subtree

•

S

u

c

c

e

s

s

o

r

:

•

The minimum from the right subtree

•

The "leftest" node in the right subtree

h

ey

h

ey

j

ude

,

don

’

t

m

ake

it

bad.

=

end

=

hey

j

ude,

don

’

t

make

it

bad.

struct Node

stack

heap

Node*

C

o

d

e

:

D

e

l

e

t

i

n

g

t

h

e

n

o

d

e

2023/2024

Programming in C++ (labs)

28

•

Case 1: Delete leaf node

•

find(D)

•

p_d_par->right/left = nullptr

h

ey

h

ey

j

ude

,

don

’

t

m

ake

it

bad.

=

end

=

make

j

ude,

don

’

t

make

it

bad.

struct Node

stack

heap

Node*

https://en.wikipedia.org/wiki/Binary_search_tree#Deletion

make

j

ude,

j

ude,

p_d

p_d_par

Watch out for case where

p_d_par is nullptr (deleting root)

C

o

d

e

:

D

e

l

e

t

i

n

g

t

h

e

n

o

d

e

2023/2024

Programming in C++ (labs)

29

•

Case 2: Delete node with one child

•

find(D)

•

p_d_par->left/right = p_s

h

ey

h

ey

j

ude

,

don

’

t

m

ake

it

bad.

=

end

=

don't

j

ude,

don

’

t

make

it

bad.

struct Node

stack

heap

Node*

https://en.wikipedia.org/wiki/Binary_search_tree#Deletion

don

’

t

bad.

bad.

p_d

p_d_par

p_s

Watch out for case where

p_d_par is nullptr (deleting root)

C

o

d

e

:

D

e

l

e

t

i

n

g

t

h

e

n

o

d

e

2023/2024

Programming in C++ (labs)

30

•

Case 3: Delete node with two children

•

Find successor S, swap with D, remove successor

•

Successor always has just one child

h

ey

h

ey

j

ude

,

don

’

t

m

ake

it

bad.

=

end

=

hey

j

ude,

don

’

t

make

it

bad.

struct Node

stack

heap

Node*

https://en.wikipedia.org/wiki/Binary_search_tree#Deletion

h

ey

don

’

t

don

’

t

j

ude,

j

ude,

it

it

nullptr

nullptr

C

o

d

e

:

D

e

l

e

t

i

n

g

t

h

e

n

o

d

e

2023/2024

Programming in C++ (labs)

31

1.

Swap contents of S and D

2.

i

f

p

_

s

_

p

a

r

!

=

p

_

d

:

p

_

s

_

p

a

r

-

>

l

e

f

t

=

p

_

s

-

>

r

i

g

h

t

3.

e

l

s

e

:

p

_

s

_

p

a

r

-

>

r

i

g

h

t

=

p

_

s

-

>

r

i

g

h

t

h

ey

h

ey

j

ude

,

don

’

t

m

ake

it

bad.

=

end

=

hey

j

ude,