Object Oriented Programming

APM 50179 EP

Class definition 

// File matrix.hpp
class matrix
{
  public:

    matrix(std::size_t nb_rows, std::size_t nb_cols);

  private:

    std::size_t m_nb_rows;
    std::size_t m_nb_cols;
    std::vector<double> m_data;
};

Class definition 

// File matrix.cpp
matrix::matrix(std::size_t nb_rows, std::size_t nb_cols)
: m_nb_rows(nb_rows),
  m_nb_cols(nb_cols),
  m_data(nb_rows * nb_cols)
{}
              

// File main.cpp
int main(int argc, char* argv[])
{
  matrix m(2, 4);
  std::cout << m.m_nb_rows << std::endl;
  return 0;
}

Build the program 


# In the matrix folder:
mkdir build
cd build
cmake ..
make
or 

# In the matrix folder:
cmmake . -B build
cmake --build build

Method definition

Define methods that return m_nb_rows and m_nb_cols

// File matrix.hpp
class matrix
{
  public:

    matrix(std::size_t nb_rows, std::size_t nb_cols);

    size_t nb_rows() const;
    size_t nb_cols() const;

  private:

    std::size_t m_nb_rows;
    std::size_t m_nb_cols;
    std::vector<double> m_data;
};

Method definition 

// File matrix.cpp
size_t matrix::nb_rows() const
{
  return m_nb_rows;
}

size_t matrix::nb_cols() const
{
  return m_nb_cols;
}
              

int main(int argc, char* argv[])
{
  hpc::matrix m(2, 4);
  std::cout << m.nb_rows() << std::endl;
  std::cout << m.nb_cols() << std::endl;
  return 0;
}

Const - 1/2 


std::size_t matrix::nb_rows() const
{
  m_nb_rows = 0;    // Error
  return m_nb_rows;
}

Changing an attribute in a const method is forbidden

Method definition

Define a method that resizes the matrix


class matrix
{
  public:

    matrix(std::size_t nb_rows, std::size_t nb_cols);

    size_t nb_rows() const;
    size_t nb_cols() const;

    void resize(std::size_t nb_rows, std::size_t nb_cols);

  private:

    std::size_t m_nb_rows;
    std::size_t m_nb_cols;
    std::vector<double> m_data;

};
                

void matrix::resize(std::size_t nb_rows, std::size_t nb_cols)
{
  m_nb_rows = nb_rows;
  m_nb_cols = nb_cols;
  m_data.resize(m_nb_rows * m_nb_cols);
}

const - 2/2 


int main(int argc, char* argv[])
{
  const matrix m(2, 4);
  m.resize(3, 5);       // Error
  return 0;
}

Calling a non-const method on a const object is forbidden

const rules

  • Whenever a parameter won't be modified, make it const
  • Whenever a method does not change the object, make it const
  • If you're not sure, make it const
  • Think twice before removing a const

Constructors

Define a constructor taking a single parameter (for squared matrices), and a default constructor


class matrix
{
  public:

    matrix();
    matrix(std::size_t size);
    matrix(std::size_t nb_rows, std::size_t nb_cols);

  // ... as before
};

Constructors 


matrix::matrix()
: m_nb_rows(0),
  m_nb_cols(0),
  m_data()
{}

matrix::matrix(std::size_t size)
: m_nb_rows(size),
  m_nb_cols(size),
  m_data(size*size)
{}

matrix::matrix(std::size_t nb_rows, std::size_t nb_cols)
: m_nb_rows(nb_rows),
  m_nb_cols(nb_cols),
  m_data(nb_rows * nb_cols)
{}

Constructors 


class matrix
{
  public:

    matrix() = default; // Default constructor
    matrix(std::size_t size);
    matrix(std::size_t nb_rows, std::size_t nb_cols);

  // ... as before
};
                

/* matrix::matrix()
: m_nb_rows(0),
  m_nb_cols(0),
  m_data()
{}*/

matrix::matrix(std::size_t size)
: matrix(size, size) // Delegating constructor
{}

matrix::matrix(std::size_t nb_rows, std::size_t nb_cols)
: m_nb_rows(nb_rows),
  m_nb_cols(nb_cols),
  m_data(nb_rows * nb_cols)
{}

Delegating constructors 


class test
{
  public:

    test(int i, int j) : m_i(i), m_j(j) {}
    test(int i) : test(i, 0) {}                        // OK
    test(int i) : test(i, 0), m_d1(0.), m_d2(0.) {}    // Illegal
    test(double d1, double d2) : m_d1(d1), m_d2(d2) {}
    test(double d) : test(d, 0.) {}                    // Illegal, only one delegating
                                                       // constructor per class

  private:

    int m_i, m_j;
    double m_d1, m_d2;
};

Constructors 


class matrix
{
  public:

    //matrix() = default; // Default constructor
    matrix(std::size_t size = 0);
    matrix(std::size_t nb_rows, std::size_t nb_cols);

  // ... as before
};

initializer list 


// File main.cpp
int main(int argc, char* argv[])
{
  hpc::matrix m = {{1., 2.}, {3., 4.}};
  // ...
  return 0;
}
              

class matrix
{
  public:

    matrix(std::size_t size);
    matrix(std::size_t nb_rows, std::size_t nb_cols);
    matrix(std::initializer_list<std::initializer_list<double>> init);

  // ... as before
};

initializer list 


matrix::matrix(std::initializer_list<std::initializer_list<double>> init)
: m_nb_rows(init.size())
, m_nb_cols(init.size() ? init.begin()->size() : 0u)
, m_data(m_nb_rows, m_nb_cols)
{
  auto dest = m_data.begin();
  std::for_each(init.begin(), init.end(), [&dest](const auto& v)
  {
    dest = std::copy(v.begin(), v.end(), dest);
  });
}

Implicit conversion 


void compute(const matrix& m) { ... }

compute(4u);

// makes the compiler generate
matrix tmp(4u);
compute(tmp);
              

class matrix
{
  public:

    explicit matrix(std::size_t size);
    matrix(std::size_t nb_rows, std::size_t nb_cols);
    matrix(std::initializer_list<std::initializer_list<double>> init);

  // ... as before
};

Access operator 


matrix m = {{ 1., 2.}, {3., 4.}};
std::cout << m[0, 1] << std::endl; // Illegal, operator[] can accept only one parameter
              

class matrix
{
  public:

  // ...

    double& operator()(size_t i, size_t j);
    const double& operator()(size_t i, size_t j) const;
};
                

double& matrix::operator()(std::size_t i, std::size_t j)
{
  return m_data[i * m_nb_cols + j];
}

const double& matrix::operator()(std::size_t i, std::size_t j) const
{
  return m_data[i * m_nb_cols + j];
}

output operator 


std::ostream& operator<<(std::ostream& out, const matrix& m);
              

std::ostream& operator<<(std::ostream& out, const matrix& m)
{
  for(std::size_t i = 0; i < m.nb_rows(); ++i)
  {
    for(std::size_t j = 0; j < m.nb_cols(); ++j)
    {
      out << m(i, j) << ", ";
    }
    out << std::endl;
  }
  return out;
}

Computed assignment 


class matrix
{
  public:

  // ...

  matrix& operator+=(const matrix& rhs);
  matrix& operator-=(const matrix& rhs);
  matrix& operator*=(const matrix& rhs);
  matrix& operator/=(const matrix& rhs);
};

Computed assignment 


matrix& matrix::operator+=(const matrix& rhs)
{
  for(std::size_t i = 0; i < m_nb_rows; ++i)
  {
    for(std::size_t j = 0; j < m_nb_cols; ++j)
    {
      m_data[i * m_nb_cols + j] += rhs.m_data[i * m_nb_cols + j];
    }
  }
  return *this;
}
              

matrix& matrix::operator+=(const matrix& rhs)
{
  std::transform(m_data.begin(), m_data.end(), rhs.m_data.begin(),
  m_data.begin(), std::plus<double>());
  return *this;
}

Computed assignment 


class matrix
{
  public:

    matrix& operator+=(double rhs);
    matrix& operator-=(double rhs);
    matrix& operator*=(double rhs);
    matrix& operator/=(double rhs);
};
              

matrix& matrix::operator+=(double rhs)
{
  std::transform(m_data.begin(), m_data.end(), m_data.begin(),
  [rhs](double arg) { return arg + rhs; });
  return *this;
}

Arithmetic operators

Solution 1 (bad)


class matrix
{
  public:

    matrix operator+(const matrix& rhs) const;
    matrix operator+(double rhs) const;
};

matrix res = m1 + m2; // OK - equivalent to res = m1.operator+(m2);
matrix res = m1 + 2.  // OK - equivalent to res = m1.operator+(2.);
matrix res = 2. + m1  // Error, no overload found for operator+(double, matrix)

Solution 2 (good)


class matrix
{
  // ...
};

matrix operator+(const matrix& lhs, const matrix& rhs);
matrix operator+(const matrix& lhs, double rhs);
matrix operator+(double lhs, const matrix& rhs);

Arithmetic operators 


matrix operator+(const matrix& lhs, const matrix& rhs)
{
  matrix tmp(lhs);
  tmp += rhs;
  return tmp;
}

matrix operator+(const matrix& lhs, double rhs)
{
  matrix tmp(lhs);
  tmp += rhs;
  return tmp;
}

matrix operator+(double lhs, const matrix& rhs)
{
  return rhs + lhs;
}

Conversion operator

We want to convert a single-row matrix to a std::vector


class matrix
{
  public:

    // ...

    // No return type
    operator std::vector<double>() const { return m_data; }
};

Conversion

  • Use a conversion constructor when you convert to a type you manage
  • Use a conversion operator when you convert to a type you don't manage

Struct 


class test
{
  double m_value; // private by default
};

struct test
{
  double m_value; // public by default
};

Plain Old Data (POD): structure with only data members, no methods


struct test
{
  double m_value;
  std::string m_name;
  int m_id;
};

Friend 


class connection
{
  private:

    int m_id;
};

void print_debug(const connection& c)
{
  // Cannot access c.m_id because it is private
  std::cout << c.m_id << std::endl;
}
              

class connection
{
  private:

    int m_id;

    friend void print_debug(const connection&);
};

Friend 


class connection
{
  private;

    int m_id;

    friend class peer;
};

All methods defined in peer have access to connection::m_id

Friend 


class peer
{
  private:

    int m_id;
};

class connection
{
  public:

    void print_peer(const peer& p)
    {
      // Illegal: peer::m_id is private
      std::cout << p.m_id << std::end;
    }

  private:

    int m_id;
    friend class peer;
};

Friendship is not reciprocal

Friend 


class connection
{
  private:
    int m_id;
    friend class peer;
};

class peer
{
  private:
    friend class socket;
};

class socket
{
  public:
    void print_connection_id(const connection& c)
    {
      // Illegal: connection::m_id is private
      std::cout << c.m_id << std::endl;
    }
};

Friendship is not transitive

Dijkstra's algorithm

The goal of this TP is to implement a graph structure and the Dijkstra's algorithm (to find the shortest path from a node to another one)

Graph

Write a node class with:

  • an id data member (should be set upon construction)
  • a list of neighboors data member (a neighboor is a pair id - distance)
  • a method to add a neighboor with a weight
  • a method to read the list of neighboors

Graph 


#include <vector>
#include <utility>

namespace hpc
{
  class node
  {
    public:

      using neighboor = std::pair<size_t, double>;
      using neighboor_list = std::vector<neightboor>;

      explicit node(size_t id);

      void add_neighboor(size_t id, double distance);
      void add_neighboor(const neighboor& n);

      const neightboor_list& get_neighboors() const;

    private:

      size_t m_id;
      neighboor_list m_neighboor_list;
  };
}

Graph

Write a graph class that holds a list of nodes. Provide a convenient API to add nodes and read them

Graph 


namespace hpc
{
  class graph
  {
    public:

      using node_list = std::vector<node>;

      void add_node(const node& n);
      const node_list& get_nodes() const;

    private:

      node_list m_node_list;
  };
}

Dijkstra's algorithm

The idea is to incrementally build a subgraph in which nodes are ordered by distance from the origin.

  • Initially, all distances are set to infinite (except for the initial node), the subgraph is empty
  • At each step, we choose a node out of the subgraph with the smallest distance to the origin and we add it to the subgraph
  • We update the distances of the neighbors of the last added node

Djikstra's example (1/9)

Djikstra's example (2/9)

Djikstra's example (3/9)

Djikstra's example (4/9)

Djikstra's example (5/9)

Djikstra's example (6/9)

Djikstra's example (7/9)

Djikstra's example (8/9)

Djikstra's example (9/9)

Dijkstra's pseudocode 


Input: G = (N, E)
  P = {}
  d[n] = +int for n in N
  d[ninit] = 0
  while there is a node out of P:
    Choose n out of P such that d[n] is the smallest distance
    Put n in P
    For each b neighboor of n out of P:
      if d[b] > d[n] + distance(b, n):
        d[b] = d[n] + distance(b, n)
        previous[b] = n

Dijkstra's pseudocode 


Input: G = (N, E)
  Q = N
  d[n] = +int for n in N
  d[ninit] = 0
  while Q not empty:
    Choose n in Q such that d[n] is the smallest distance
    remove n from Q
    For each b neighboor of n in Q:
      if d[b] > d[n] + distance(b, n):
        d[b] = d[n] + distance(b, n)
        previous[b] = n

Dijkstra's algorithm

Implement the Dijkstra'a algorithm. The function should have the following signature:


void dijkstra(const graph& g, size_t start, size_t end, std::list<size_t>& path);