Practices and Common Issues

Names and Scopes

Common Mistake: type != variable name

struct IntegerNode
{
    int data;
    IntegerNode *next;
};

struct IntegersLL
{
    IntegerNode *head;
};

int size( IntegersLL &lst )
{
    // Find mistakes
    front = IntegersLL.head; // Error

    // Who is front?

    // Who is IntegersLL?

    // Who is IntegersLL.head?
}
  • Don’t use any name unless it is declared. front is undeclared.
  • IntegersLL is a type not a name of a variable.

Common Mistake: when passing by reference don’t mess with input data

int size( IntegersLL &lst )
{
    // Find mistakes
    int count = 0;
    while( lst.head != nullptr )
    {
        count++;
        lst.head = lst.head->next;
    }
    return count;
}

Common Mistake: Pointer to struct != Reference to a struct != Name to a struct

struct IntegerNode
{
    int data;
    IntegerNode *next;
};

struct IntegersLL
{
    IntegerNode *head;
};


int size( IntegersLL &lst )
{
    // Find two mistakes
    int count = 0;
    IntegersNode *current = lst->head; // Error

    while( current != nullptr )
    {
        count++;
        current = current.next; // Error
    }
    return count;
}

Functions

Bad Practice: Global Variables

As a rule of thumb, inside a function, all what you have got is the function input.

struct IntegerNode
{
    int data;
    IntegerNode *next;
};

struct IntegersLL
{
    IntegerNode *head;
};

// Never do this. You are breaking the concept of a function!
IntegersLL myList; // A global variable

int size( IntegersLL &lst ) // unused input lst!
{
    int count = 0;

    // This function will only work with the global variable `myList`
    // We cannot apply this function to any other Linked List of integers!
    IntegersNode *current = myList.head;

    while( current != nullptr )
    {
        count++;
        current = current->next;
    }
    return count;
}

The correct solution

struct IntegerNode
{
    int data;
    IntegerNode *next;
};

struct IntegersLL
{
    IntegerNode *head;
};

int size( IntegersLL &lst )
{
    int count = 0;
    IntegersNode *current = lst.head;

    while( current != nullptr )
    {
        count++;
        current = current->next;
    }
    return count;
}

Common mistakes in calling functions

#include "linkedlist.hpp"
#include <iostream>

int main()
{
    list::IntegersLL samples;

    // Why you do this?
    std::cout << "size:" << list::size( IntegersLL &lst ); // error

    // Or this?
    std::cout << "size:" << list::size( IntegersLL &samples ); // error

    // We already declared samples of type list::IntegersLL
    std::cout << "size:" << list::size( samples ); // good
}

Main Function

Useful Application

The main function is the program entry point. In practice, developers build libraries over libraries, in order to be finally used in the main function. Recall the diagrams of week 3.

multiple

dependencies

Testing Application

It is always useful to make a file with a main function to test the functions and structures you have just developed so:

  1. You feel satisfied about what you have developed.
  2. Detecting any unexpected behavior, and accordingly helps you debug your code.

Each member in a group assignment is required to make a file with a main function to test his/her developed functions. Due discussion date.

Advanced: Unit Testing

In practice, testing libraries is carried out in a more formal and standardized methodologies. Although it is currently an advanced topic, you can read about Test-Driven Development (TDD) in the summer. In C++, there are famous unit testing frameworks, for example:

Data Structures: Big Picture

Complexity Analysis: Big-Oh Notation

Segmentation Fault (Core Dumped)

Fact Although your application did compile without errors, doesn’t mean it is logically correct or should run as expected. So far, errors in C++ development can be classified into:

  1. Compilation errors.
  2. Run-time errors (bugs), and can be classified into:
    • Logical error: you don’t get the expected output.
    • Critical error: you are abusing the memory access. This will result in a crash with an ambiguous message emitted Segmentation fault (Code Dumped).

The Segmentation fault error typically results after:

  • Dereferencing a nullptr.
  • Dereferencing an un-initialized pointer, as a side-effect of undefined behavior.
  • Dereferencing a pointer of a de-allocated place:
    • De-allocated place in stack memory after going out of scope.
    • De-allocated place in heap memory after deleteing that place using its pointer.
  • Exceeding array boundaries.

Memory Management and Memory Leakage

Valgrind

Installing Valgrind

sudo apt-get install valgrind

Running Valgrind

In order to trace your code to the point of the crash you need to compile your code with an additional flag -g. The flag -g tells your compiler to compiler your program in Debugging mode.

g++ -g -std=c++11 -Wall test.cpp -o test
  • -g for debugging mode.
  • -std=c++11 to use the C++ standards of 2011.
  • -Wall to emit any compilation warnings, very useful flag.
  • test.cpp the source file that has a main function.
  • -o test a flag for the compiler output followed by the output name of the executable.
valgrind -v --leak-check=full --show-leak-kinds=all ./test

How to interpret a commit at github

As you already know, git commits are line-oriented, i.e documents changes in lines. green lines represents added lines in that commit, while red lines represents removed lines from that commit.

Each team member at github can be visualized his/her contribution in the repository.

If we wish to count lines of code, we should not regard them as “lines produced” but as “lines spent”. — Edsger Dijkstra

Where are we now

Week Data Structures & C++ Ecosystem & Miscellaneous
1 Introduction: Brief intro to DS; C++ Basics Briefly: Unix, compilation, git, github
2 C++ Memory Model, C++ Pointers and References Your Code Readability
3 Static and Dynamic Arrays; Categorize your logic with namespace scopes; Processing command line arguments (argc & argv); Compilation of multiple files; Basic Unix commands; bitbucket
4 Stacks (ADT); Queues (ADT); Linked Lists; Array-Based Stack; LL-Based Stack; Array-Based Queue; LL-Based Queue; Functions Overloading; Naming conventions; Const correctness; C++ classes and objects Brief intro to git for teams; Brief intro to build systems
5 Recursion; Briefly: CMake; Git on large scale
6 Bubble sort; Selection sort; Binary Trees Open source vs. proprietary software
7 C++ template structs and template functions; std::string; std::vector; std::array; std::list; std::stack …

Data Structures and Algorithms: What you must know for this semester until week 7

C++ is just a powerful tool to prove our computation theories!

Focus on concepts

Week 1: C++ Basics

  • Essential: Primitive data types (PDT)
  • Essential: Variables, declaration, and initialization
  • Essential: Functions, namespaces, and scopes
  • Essential: main function and basic compilation
  • Extra: git, github, bitbucket, and Linux.

Week 2: C++ Memory Model

  • Essential: Pointers and references
  • Essential: Static allocations (static)
  • Essential: Heap allocations (dynamic)
  • Extra: Code styling and best practices

Week 3: Arrays

  • Essential: Static arrays
  • Essential: Dynamic arrays
  • Extra: Processing command line arguments
  • Extra: Compilation of multiple files
  • Extra: Separating libraries and application files

Week 4: Linked Lists, Stacks, and Queues

  • Essential: Stack (ADT)
  • Essential: Queue (ADT)
  • Essential: Linked list
  • Essential: Array implementation of stack
  • Essential: Linked list implementation of stack
  • Essential: Linked list implementation of queue
  • Essential: Custom types using struct
  • Extra: Function overloading
  • Extra: Naming conventions
  • Extra: Const-correctness
  • Extra: Basic OOP at glance
  • Extra: Build Systems (CMake)
  • Extra: Git for teams

Week 5: Recursion and Big-Oh Notation

  • Essential: Big-Oh notation
  • Essential: Recursion
  • Extra: Markdown

Week 6: Recursion and Big-Oh Notation

  • Essential: Sorting
  • Essential: Bubble sort and Selection Sort

Week 7: Revision, Common Mistakes, and Best Practices

  • Essential: List using array
  • Extra: Type normalization: C++ templates
  • Extra: std::string, std::vector, std::array, std::list, std::stack.

C++ Templates: Towards Polymorphism and DRY Solutions

As some of you have realized the latest assignment you have implemented a linked list, stack, or a queue for a certain data type, then you repeated your logic for the other data types. In C++, there are many polymorphism techniques can be employed to achieve more DRY solutions for such situations.

Type Normalization in C++

// mylist.hpp
#include <cstdlib>
namespace list
{

template< typename T >
struct Node
{
    T data;
    Node *next;
};

template< typename T >
struct LL
{
    Node< T > *head = nullptr;
};

template< typename T >
void insertFront( LL< T > &lst ,  T data )
{
    auto newNode = new Node< T >{ data , lst.head };
    lst.head = newNode;
}

template< typename T >
void removeFront( LL< T > &lst )
{
    auto discard = lst.head;
    lst.head = lst.head->next;
    delete discard;
}

template< typename T >
T front( LL< T > &lst )
{
    if( lst.head )
        return lst.head->data;
    else exit( 1 );
}

template< typename T >
bool isEmpty( LL< T > &lst )
{
    return lst.head == nullptr;
}

}

In the main function you just need to specialize your template struct at the point of usage. See the following example of the DNA complementary sequence solved using templates.

// main.cpp
#include "mylist.hpp"
#include "helpers.hpp"
#include <iostream>
#include <string>

char complementaryBase( char base )
{
    if( base == 'A' ) return 'T';
    else if( base == 'T' ) return 'A';
    else if( base == 'G' ) return 'C';
    else return 'G';
}

int main( int argc , char **argv )
{
    std::string dna = helpers::getLines( argv[1] )[0];

    list::LL< char > ls; // Declaration + Instantiation of template LL

    std::string cdna;

    for( char base : dna )
    {
        list::insertFront( ls , complementaryBase( base ));
    }

    while( ! list::isEmpty( ls ))
    {
        cdna.push_back( list::front( ls ));
        list::removeFront( ls );
    }

    std::cout << cdna;
}

Basic OOP: Revisited

template< typename T >
struct Node
{
    T data;
    Node *next;
};

template <typename T>
struct Node
{
    T data;
    Node *next;
};

template <typename T>
struct LL
{
    Node<T> *head = nullptr;

    void insertFront( T data)
    {
        auto newNode = new Node<T>{data, head};
        head = newNode;
    }

    void removeFront( )
    {
        auto discard = head;
        head = head->next;
        delete discard;
};

Now we can use our template structure as:

int main( int argc , char **argv )
{
    std::string dna = helpers::getLines( argv[1] )[0];

    list::LL< char > ls;

    std::string cdna;

    for( char base : dna )
    {
        ls.insertFront( complementaryBase( base ));
    }

    while( ! ls.isEmpty())
    {
        cdna.push_back( ls.front());
        ls.removeFront();
    }

    std::cout << cdna;
}

To clone the whole demo:

git clone https://github.com/sbme-tutorials/sbe201-week7-demo.git

Main Data Structures in the Standard Template Library (STL)

std::string

std::string official documentation. std::string represents a dynamic array of characters, with a lot of functionalities to avoid the pain of working with concrete array of characters (i.e char *).

  • operator= assigns values to the string
std::string text;
text = "Hello there!"; // Here we invoke the operator=
std::cout << text;

int main( int argc, char **argv )
{
    std::string input = argv[1]; // Invoked operator=
    std::cout << input;
}
  • operator[] accesses the specified character at given index
std::string text = "Yello SBME";
text[0] = 'H';
std::cout << text; // prints: Hello SBME
  • back returns last character, e.g (text.back()).
  • front returns first character, e.g (text.front()).
  • size returns the size of the string (text.back()).
  • empty returns true if the string is empty, false otherwise (text.empty()).
  • clear clears the content of the string, i.e becomes empty (text.clear()).
  • push_back adds a character to the end (text.push_back('?')).
  • pop_back removes the last element (text.pop_back()).

std::vector

std::vector official documentation. std::vector is a template class/struct that represents a dynamic array, with several functionalities.

  • operator[] accesses the specified character at given index
  • back returns last element, e.g (samples.back()).
  • front returns first element, e.g (samples.front()).
  • size returns the size of the vector.
  • empty returns true if the vector is empty, false otherwise.
  • clear clears the content of the string, i.e becomes empty.
  • push_back adds an element to the end.
  • pop_back removes the last element.

std::array

std::array official documentation. std::array is a template class/struct that represents a static array, with several functionalities. As expected you should introduce a type and the array size at compilation-time. E.g, to instantiate an std::array of 250 integers:

std::array< int , 250 > samples;
  • operator[] accesses the specified character at given index
  • back returns last element, e.g (samples.back()).
  • front returns first element, e.g (samples.front()).
  • size returns the size of the vector.
  • empty returns true if the vector is empty, false otherwise.

More Exercises

Soon

Central Dogma (Transcription and Translation)

Soon

Queues

Pangrams

Soon

http://exercism.io/exercises/cpp/pangram/readme

Demo files

git clone https://asem_abdelaziz@bitbucket.org/sbmetutorials/sbe201-week3-demo.git