Data Structure and Algorithm Design

Sections

• Modular Development in C++

• Testing for C++

Modular Development in C++

Outline

• Overview

  • Definition

  • Motivation and benefits

  • Source code organization

  • C++ building model

• Building using GNU g++

  • Preprocessing directives

  • One step compilation

  • Step-wise modular compilation

• Automate the building process using GNU make

  • Makefile

  • Modular compilation using make

• Pitfalls and common errors

TL;DR

• Must go modular in this course!

• No longer have single-cpp-file projects.

• Organize source code as header and source files.

• Logically organized as drivers and modules.

• Use g++ step-wise compilation

• Learn basic makefile syntax

Modular Development Overview

• Definition

  Modular development in C++ refers to the practice of designing and structuring a software application as a collection of independent and reusable modules or components. Each module encapsulates a specific set of functionality, and these modules can be developed, tested, and maintained separately from each other.

• Motivation and benefits

  • Code reusability

  • Simplicity

  • Encapsulation

  • Parallel development

  • Flexibility

  • Testability

Source Code Organization

Quick Quiz

In a project with files: main.cpp, table.hpp, table.cpp, and list.hpp, find which files belongs to the following categories:

1. Driver

2. Module (paired files)

3. Module (header only)

C++ Building Model

• The process of translating source codes into executables or libraries is called building.

• Inherited from C, C++ building process is complicated and tedious.

• The building process consists of three stages:

  • Preprocessing

    • process all preprocessor directives

    • the #include directive injects hpp file contents into cpp files

  • Compiling

    • compile cpp files into object files

    • one object file for each cpp file

  • Linking

    • link object files into an executable

    • link object files with libraries (FYI)

Building using GNU g++

• Overview

  g++ is the GNU C++ compiler invocation command. It builds C++ source codes to produce libraries or executables. It serves as pre-processor, compiler, and linker for C++ projects.

• g++ command syntax

  g++ [options] [files]

  • files: source files, object files

  • options: a list of options to control the building process

Preprocessing directives

• Commands to the preprocessor.

• They start with # and end with no semicolon.

• #include <header>: inject the content of header file into the current file.

• #define: define a macro (text replacement rule).

• Header guards: prevent header files from being included multiple times.

  #ifndef HEADER_GUARD
  #define HEADER_GUARD
  
  // header file content
  
  #endif

Two building approaches: One step

• Not recommended for modular projects.

• Should be limited to simple projects.

• Preprocessing + Compilation + Linking all at once

• Generate one executable from a single driver and other source files for modules

g++ -std=c++14 -I<path/to/headers> -o <executable> <list of .cpp files>

Two building approaches: Step-wise

• Recommended for modular projects.

• Allows fine control over the building process of complicated modular projects.

• Preprocessing + Compilation

  • g++ flag: -c

  • generate one object file for each cpp file

  g++ -c -Wall -std=c++14 -I<path/to/headers> <file>.cpp

• Linking

  • generate one executable from object file of a driver and other object files of modules

  g++ -o <executable> <list of .o files>

• Common errors: link

Never Do This!

• Include cpp files using #include directive

• File name mismatch between #include directive and actual file name; Commonly caused by the use of capital letters in file names

• Include header file names in the g++ command line

• Linking object files of multiple drivers into one executable

• Forget to include header guards in header files

• Forget -c flag in the compilation command

Quick Quiz

What is wrong with the following commands? What type of building approach is?

• g++ -o main main.cpp grade-book.cpp grades.hpp

• g++ -o main.o main.cpp

• g++ -c -o main.o main.cpp grade-book.cpp

Automate the building process using GNU make

# declare virtual targets
.PHONY: clean

# Linking to provide the executable
main: main.o grade-book.o student.o grades.o
    g++ -o main main.o grade-book.o student.o grades.o

# Compile. One cpp file a time.
main.o: main.cpp grade-book.hpp student.hpp
    g++ -std=c++14 -Wall -g -c main.cpp

student.o: student.cpp student.hpp
    g++ -std=c++14 -Wall -g -c student.cpp

grades.o: grades.cpp grades.hpp
    g++ -std=c++14 -Wall -g -c grades.cpp

grade-book.o: grade-book.cpp grade-book.hpp student.hpp grades.hpp
    g++ -std=c++14 -Wall -g -c grade-book.cpp

# the 'clean' virtual target to remove temporary files
clean:
    rm -rf *.o main *.gc* *.dSYM

Use GNU make to build

• Create a makefile in the project directory.

• Define rules for compiling and linking.

• Run make commands:

  • make: build the first target in the makefile, you can press tab to auto-complete the target name

  • make <target>: build the specified target

  • make clean: remove temporary files

• Common make targets in projects

  • make test-all: run all tests

  • make test-#-name: run test number #

  • make test-run: compile and run the program

Testing For C++

Outline

• Definition

• Motivation

• Types

• Learning outcomes

TL;DR

• “Debugging” is too hard! Use “testing” instead.

• Write drivers (cpp file with main function) to test your code.

• Feed input and check output.

• Writing more code (testing code) will actually save you time.

• Expect you to learn to read tests first in this course.

Overview

• Definition: Testing in software development is the process of evaluating and validating a software system to ensure its correctness, functionality, and performance. Automated testing is especially important for large projects.

• Motivation and benefits

  • Large projects are hard to test manually.

  • Automated testing is more efficient and reliable.

  • Tests can describe the functionality of the system (requirements).

  • Testable code is usually modular and well-organized.

• Types

  • Unit tests

  • Integration tests

  • System tests

• Test-driven development (FYI)

  • Write tests first

  • Write code to pass tests

Types of tests

• Unit tests

  • Test a single function or class method.

  • Test the correctness of the function/method.

  • Test the boundary cases.

  • Test the performance.

  • May need special techniques to isolate the function/method.

• Integration tests

  • Test the interaction between modules.

  • Test the correctness of the interaction.

• System tests

  • Test the system as a whole.

  • Test the correctness of the system.

  • Test the performance.

Write and run tests

• Workflow

  • Write test drivers that call functions/class methods to be tested.

  • Add building rules for test drivers in the makefile.

  • Frequently run tests to ensure the correctness of the code.

• Simple test driver

  Display the result of a function call for the tester to compare.

  #include <iostream>
  #include "store-item.hpp"
  
  void testStoreItem() {
    StoreItem item1("Apple");
    StoreItem item2("apple");
    if (item1.equals(item2))
      std::cout << "They are equal as expect!\n";
    else
      std::cout << "They are not equal, wrong!\n";
  }

Write and run tests (cont’d)

• Test driver using assert

  • assert is a macro that checks the truth of an expression.

  • If the expression is false, assert prints an error message and aborts the program.

  • assert is a simple way to write test drivers.

  • include <cassert> to use assert.

  #include <cassert>
  #include "store-item.hpp"
  
  void testStoreItem() {
    StoreItem item1("Apple");
    StoreItem item2("apple");
    assert(item1.equals(item2));
  }

Write and run tests (cont’d)

• Test driver using testing frameworks

  • Testing frameworks are libraries that provide tools to write tests.

  • They are more powerful than assert.

  • E.g. Google Test, Boost Test, Catch2 etc.

  • We use Catch2 in this course.

  #include "catch.hpp"
  #include "store-item.hpp"
  
  TEST_CASE("StoreItem equality and printing", "[StoreItem]") {
    SECTION("Case-insensitive comparison") {
      StoreItem item1("Apple");
      StoreItem item2("apple");
      CHECK(item1.equals(item2));
    }
  }

Learning outcomes

• Understand the importance of testing.

• Know how to write simple test drivers.

• Know how to write test drivers using assert macro.

• Know how to read test cases written with Catch2 framework and write code to pass the tests.