Specifying RAM

A verbose structure

Here, let us use the type num and the related display tool in order to display what happens to the memory.

The keyword struct (as well as class which is very similar) allows for defining how to use a fixed size bunch of memory.

Here, let us define lists of nums, where elements can be append on the left (+) or on the right (-). As the number of elements cannot be known at compiling time, the elements have to live in the heap.

We do not use the std::list type defined in the STL, we re-implement a simplified version of it. The point is an efficient the implementation of the use of memory.

The code used in this section are exemple-*.cpp files in the archive struct.tar.gz. To test code, unzip and dive into the directory first

mylogin@mymachine:~$ tar zxvf struct.tar.gz
mylogin@mymachine:~$ rm struct.tar.gz
mylogin@mymachine:~$ cd struct
mylogin@mymachine:~$ more README.txt

The type interface `serie.hpp`

// This is the serie.hpp file.

#pragma once
#include <num.hpp>

// Forward declaration.
struct elem;
struct serie;
// The type serie (and elem) definition is pending (to be done later),
// but the compiler knows it exists. We can use serie&, serie* since
// this do not require to know sizeof(serie), which is not defined
// yet.
//
// Moreover, we can use the type serie in function headers, as soon
// has no function call has to be compiled.

// The following should return a "const serie" type in order to forbid
// the writing of (a+b) = c. Nevertheless, returning const type
// prevents the application of optimization with expiring.
//
// a + b + c <=> (a + b) + c, so temporary results are often on the
// left.
serie operator+(const serie&  a, const serie&  b);
serie operator+(      serie&& a, const serie&  b);
serie operator+(const serie&  a,       serie&& b);
serie operator+(      serie&& a,       serie&& b);
serie operator-(const serie&  a, const serie&  b);
serie operator-(      serie&& a, const serie&  b);
serie operator-(const serie&  a,       serie&& b);
serie operator-(      serie&& a,       serie&& b);

bool operator==(const serie&, const serie&);
bool operator!=(const serie&, const serie&);

// Serialization
std::ostream& operator<<(std::ostream&, const serie&);
std::istream& operator>>(std::istream&,       serie&);

struct serie {
  elem* front;
  elem* back;
  std::size_t size;

  // The constructors and affectations that should be implemented
  // since default ones my be used if there definition is missing
  // here.
  serie();
  serie(const serie&);
  serie(serie&&);
  serie& operator=(const serie& );
  serie& operator=(      serie&&);

  // Constructors and affectation from an external type.
  serie(int);

  // Destructor
  ~serie();

  // Conversion to bool (false <=> empty)
  operator bool() const;                  // if(s) {...};
  serie& operator+=(const serie& );       // a += b // prepend
  serie& operator+=(      serie&&);       // a += b // prepend
  serie& operator-=(const serie& );       // a -= b // append
  serie& operator-=(      serie&&);       // a -= b // append
  
  // Other features
  void clear();
  static serie empty();                   // serie::empty()
  static serie range(int start, int end); // serie::range(3, 8);
};

The code implementation `serie.cpp`

// This is the serie.cpp file.

#include "serie.hpp"
#include <string>

#ifdef serieDEBUG_MOVE_CALLS
#include <sstream>
#endif

// Elem is not needed by the serie users. So it can be defined in the
// .cpp file. It is somehow "private" to the serie definition.
struct elem {
  num content;
  elem* next;

  // Here, we define the contructors inline.
  elem(int             val) : content(std::string("e") + std::to_string(val), val), next(nullptr) {}
  elem(const num&  content) : content(content),                                     next(nullptr) {}
  elem(      num&& content) : content(std::move(content)),                          next(nullptr) {
#ifdef serieDEBUG_MOVE_CALLS
    std::ostringstream ostr;
    ostr << "elem::elem(num&&  " << content << ")";
    scope(ostr.str());
#endif
  }
};

serie::serie()
  : front(nullptr), back(nullptr), size(0) {
}

serie::serie(const serie& copy)
  : front(nullptr), back(nullptr), size(0) {
  *this = copy; // affectation by copy defined later.
}

serie::serie(serie&& copy)
  : front(nullptr), back(nullptr), size(0) {
  
#ifdef serieDEBUG_MOVE_CALLS
  std::ostringstream ostr;
  ostr << "serie::serie(serie&& " << copy << ")";
  scope(ostr.str());
#endif
  
  *this = std::move(copy); // affectation by move defined later.
}

// Try to draw the memory chunks here...
serie& serie::operator=(const serie& arg) {
  // We try to reuse the memory we already have.
  elem*  src_iter = arg.front;
  back            = front;
  
  elem** dst_iter = &front;
  // The content of dst_iter is where next element address should be
  // stored. In other words, dst_iter stores the address of the place
  // where the address of the next element is stored. So *dst_iter is
  // the address of the next element.

  while(src_iter != nullptr) {
    if(*dst_iter == nullptr) // we have no existing element at "this", we create it.
      *dst_iter = new elem(src_iter->content);
    else
      (*dst_iter)->content = src_iter->content;
    back     = *dst_iter;
    src_iter = src_iter->next;
    dst_iter = &((*dst_iter)->next);
  }

  if(back->next != nullptr) {// this was longer than arg
    elem* it = back->next;
    while(it != nullptr) {
      elem* next = it->next;
      delete it;
      it = next;
    }
    back->next = nullptr;
  }
  return *this;
}

serie& serie::operator=(serie&& arg) {
#ifdef serieDEBUG_MOVE_CALLS
  std::ostringstream ostr;
  ostr << "serie& serie::operator=(serie&& " << arg << ")";
  scope(ostr.str());
#endif
  
  clear();
  front = arg.front;
  back  = arg.back;
  size  = arg.size;

  // Do not arg.clear() here ! It would be a bug.
  arg.front = nullptr;
  arg.back  = nullptr;
  arg.size  = 0;
  return *this;
}

serie::serie(int value)
  : front(new elem(value)), back(nullptr), size(1) {
  back = front;
}

serie::~serie() {
  clear();
}

serie::operator bool() const {
  return front != nullptr;
}
     
serie& serie::operator+=(const serie& arg) {
  if(arg) {
    elem* src_iter   = arg.front; // not nullptr here.
    elem* new_elems  = new elem(src_iter->content);
    elem* current    = new_elems;
    for(src_iter = src_iter->next; src_iter != nullptr; src_iter = src_iter->next, current = current->next)
      current->next = new elem(src_iter->content);
    current->next  = front;
    front          = new_elems;
    size          += arg.size;
  }
  return *this;
}

serie& serie::operator+=(serie&& arg) {
#ifdef serieDEBUG_MOVE_CALLS
  std::ostringstream ostr;
  ostr << "serie& serie::operator+=(serie&& " << arg << ")";
  scope(ostr.str());
#endif
  
  if(arg) {
    arg.back->next  = front;
    front            = arg.front;
    size            += arg.size;
    // Do not arg.clear() here ! It would be a bug.
    arg.front = nullptr;
    arg.back  = nullptr;
    arg.size  = 0;
  }
  return *this;
}

serie& serie::operator-=(const serie& arg) {
  if(arg) {
    elem* src_iter   = arg.front; // not nullptr here.
    elem* new_elems  = new elem(src_iter->content);
    elem* current    = new_elems;
    for(src_iter = src_iter->next; src_iter != nullptr; src_iter = src_iter->next, current = current->next)
      current->next = new elem(src_iter->content);
    if(*this) {
      back->next  = new_elems;
      size       += arg.size;
    }
    else {
      front = new_elems;
      size  = arg.size;
    }
    back = current;
  }
  return *this;
}

serie& serie::operator-=(serie&& arg) {
#ifdef serieDEBUG_MOVE_CALLS
  std::ostringstream ostr;
  ostr << "serie& serie::operator-=(serie&& " << arg << ")";
  scope(ostr.str());
#endif
  
  if(arg) {
    if(*this) 
      back->next = arg.front;
    else 
      front = arg.front;
    size += arg.size;
    back  = arg.back;
    
    // Do not arg.clear() here ! It would be a bug.
    arg.front = nullptr;
    arg.back  = nullptr;
    arg.size  = 0;
  }
  return *this;
}

void serie::clear() {
  elem* iter = front;
  while(iter != nullptr) {
    elem* next = iter->next;
    delete iter;
    iter = next;
  }
  size  = 0;
  front = nullptr;
  back  = nullptr;
}

serie serie::empty() {
  return {};
}

serie serie::range(int start, int end) {
  serie res;
  for(int i = start; i != end; ++i)
    res -= i;
  return res;
}

serie operator+(const serie& a, const serie& b) {
  serie res = a;
  res += b;
  return res;
}

serie operator+(serie&& a, const serie& b) {
#ifdef serieDEBUG_MOVE_CALLS
  std::ostringstream ostr;
  ostr << "const serie serie::operator+(serie&& " << a
       << ", const serie& " << b << ")";
  scope(ostr.str());
#endif
  
  serie res = std::move(a);
  res += b;
  return res;
}

serie operator+(const serie& a, serie&& b) {
#ifdef serieDEBUG_MOVE_CALLS
  std::ostringstream ostr;
  ostr << "const serie serie::operator+(const serie& " << a
       << ", serie&& " << b << ")";
  scope(ostr.str());
#endif
  
  serie res = std::move(b);
  res += a;
  return res;
}

serie operator+(serie&& a, serie&& b) {
#ifdef serieDEBUG_MOVE_CALLS
  std::ostringstream ostr;
  ostr << "const serie serie::operator+(serie&& " << a
       << ", serie&& " << b << ")";
  scope(ostr.str());
#endif
  
  serie res = std::move(a);
  res += std::move(b);
  return res;
}

serie operator-(const serie& a, const serie& b) {
  serie res = a;
  res -= b;
  return res;
}

serie operator-(serie&& a, const serie& b) {
#ifdef serieDEBUG_MOVE_CALLS
  std::ostringstream ostr;
  ostr << "const serie serie::operator-(serie&& " << a
       << ", const serie& " << b << ")";
  scope(ostr.str());
#endif
  
  serie res = std::move(a);
  res -= b;
  return res;
}

serie operator-(const serie& a, serie&& b) {
#ifdef serieDEBUG_MOVE_CALLS
  std::ostringstream ostr;
  ostr << "const serie serie::operator-(const serie& " << a
       << ", serie&& " << b << ")";
  scope(ostr.str());
#endif
  
  serie res = std::move(b);
  res -= a;
  return res;
}

serie operator-(serie&& a, serie&& b) {
#ifdef serieDEBUG_MOVE_CALLS
  std::ostringstream ostr;
  ostr << "const serie serie::operator-(serie&& " << a
       << ", serie&& " << b << ")";
  scope(ostr.str());
#endif
  
  serie res = std::move(a);
  res -= std::move(b);
  return res;
}

bool operator==(const serie& a, const serie& b) {
  if(a.size != b.size) return false;
  if(a.size == 0)      return true;
  elem* a_iter = a.front;
  elem* b_iter = b.front;
  for(; a_iter != nullptr; a_iter = a_iter->next, b_iter = b_iter->next)
    if(a_iter->content != b_iter->content) return false;
  return true;
}

bool operator!=(const serie& a, const serie& b) {
  return !(a == b);
}

std::ostream& operator<<(std::ostream& os, const serie& s) {
  os << '[';
  if(s) {
    elem* it = s.front;
    os << it->content;
    for(it = it->next; it != nullptr; it = it->next)
      os << ", " << it->content;
  }
  os << ']';
  return os;
}

std::istream& operator>>(std::istream& is, serie& s) {
  s.clear();
  // We could be more efficient here, and reuse the memory in s. You
  // can try to improve this function.
  
  char c;
  int value;
  is >> c; // eats white spaces and then c <- '['
  while(c != ']') {
    is >> c;
    if(c != ']') {
      is.putback(c);
      is >> value >> c;
      s -= value;
    }
  }
  return is;
}

Try the examples…

Take the time to try and understand what all the examples do.

The `Complex` class

This is a real class (with private section, not detailed so far). The comments are in French. Use this class as a reminder for syntax, since there is a complex class in the STL.

The intended usage

#include <iostream>
#include <string>
#include "Complex.hpp"

int main(int argc, char* argv[]) {
  
  try {
    Complex a         = Complex(2,3) + Complex::i();
    Complex b         = Complex(2,3).conj() + 1;
    std::string a_str = (std::string)a;
    std::cout << a << std::endl
	      << b << std::endl
	      << a_str << std::endl;
    b /= 0;
    std::cout << "Done." << std::endl;
  }
  catch(const std::exception& e) {
    std::cerr << "Exception caught : " << e.what() << std::endl;
  }

  return 0;
}

The type interface `Complex.hpp`

// Fichier Complex.hpp

#pragma once

#include <iostream>
#include <string>

/////////////////////////
//                     //
// Opérateurs externes //
//                     //
/////////////////////////

class Complex;
// Le type complex est incomplet (déclaré plus tard, i.e. "forward
// declaration").  On peut maintenant parler de Complex& et Complex*
// même si la classe Complex n'est définie qu'après. De même, tant
// qu'une fonction n'est pas appelée et tant que son corps de fonction
// n'est pas défini, on peut parler d'un type incomplet pour ses
// arguments ou sa valeur de retour.


// Opérateurs de sérialisation.
std::ostream& operator<<(std::ostream& os, const Complex& c);
std::istream& operator>>(std::istream& is, Complex& c);

// L'opérateur renvoie un const Complex afin d'éviter que l'expression
// suivante soit licite :
// (a+b) = c;
const Complex operator+(const Complex&  a, const Complex&  b);

/////////////////////////
//                     //
// La classe elle-même //
//                     //
/////////////////////////

class Complex {
private:
    
  double  re; 
  double  im;


  // Ceci comptera le nombre d'instance de la classe complexe qui sont
  // "vivantes" en mémoire. C'est un exemple d'utilisation d'un
  // attribut statique.
  static unsigned int nb;

  // Les fonctions externes sont déclarées comme "amies" de la
  // classe. Leur code pourra utiliser des noms privés (re, im, reim,
  // nb, ...).
  
  friend std::ostream& operator<<(std::ostream& os, const Complex& c);
  friend std::istream& operator>>(std::istream& is, Complex& c);

  friend const Complex operator+(const Complex&  a, const Complex&  b);

public:

  Complex();                            // Recommandé
  Complex(const Complex& c);            // Recommandé
  Complex& operator=(const Complex& c); // Recommandé
  // Complex(Complex&& c);              // Inutile, pas d'allocation dans le tas.
  // Complex& operator=(Complex&& c);   // Inutile, pas d'allocation dans le tas.
  ~Complex();                          

  Complex(double re,double im=0);

  operator std::string() const; // Cast to string.

  Complex  conj()  const; // Const signifie que l'appel ne modifie pas l'objet. 
  double   norm()  const; // C'est bien sûr invalide pour les méthodes statiques.
  double   norm2() const;

  bool     operator==(const Complex& c) const; 
  Complex& operator+=(const Complex& c);
  Complex& operator/=(double d);

  static Complex zero();
  static Complex one();
  static Complex i();
  static unsigned int nb_instances();

};

The code implementation `Complex.cpp`

// Fichier Complex.cpp

#include "Complex.hpp"
#include <stdexcept>
#include <cmath>
#include <sstream>

// création et initialisation de l'attribut statique (variable globale
// dans le segment "data").
unsigned int Complex::nb = 0;

std::ostream& operator<<(std::ostream& os, const Complex& c) {
  os << c.re << ' ' << c.im;
  return os;
}

std::istream& operator>>(std::istream& is, Complex& c) {
  is >> c.re >> c.im;
  return is;
}

const Complex operator+(const Complex& a, const Complex& b) {
  return {a.re + b.re, a.im + b.im};
}

Complex::Complex() 
  : re(0), im(0) {
  ++nb;
}
               
Complex::Complex(const Complex& c) 
  : re(c.re), im(c.im) {
  ++nb;
}
        
Complex& Complex::operator=(const Complex& c) {
  if(this != &c) {
    re = c.re;
    im = c.im;
  }
  return *this;
}
   
Complex::~Complex() {
  --nb;
}

Complex::Complex(double re,double im)
  : re(re), im(im) {
  ++nb;
}

Complex::operator std::string() const {
  std::ostringstream ostr;
  ostr << re << " + " << im << "*i";
  return ostr.str();
}

Complex  Complex::conj() const {
  return Complex(re,-im);
}

double Complex::norm() const {
  return std::sqrt(norm2());
}

double Complex::norm2() const {
  return re*re + im*im;
}

bool Complex::operator==(const Complex& c) const {
  return re == c.re && im == c.im;
}
 
Complex& Complex::operator+=(const Complex& c) {
  re      += c.re;
  im      += c.im;
  return *this;
}

Complex& Complex::operator/=(double d) {
  if(d == 0)
    throw std::invalid_argument("Complex /= 0");
  
  re      /= d;
  im      /= d;
  return *this;
}

Complex Complex::zero() {
  return Complex();
}

Complex Complex::one() {
  return Complex(1, 0);
}

Complex Complex::i() {
  return Complex(0, 1);
}

unsigned int Complex::nb_instances() {
  return nb;
}

Inlined methods

As usual functions, mehtods can be inlined. No need for the inline keyword in this case, you just have to write the code directly in the class definition (and no more in the .cpp assorted file). As for functions, inlining a method implies writing the code in the .hpp file, i.e. any user can see how the method is programmed.

// File Point.hpp, no Point.cpp since everything is inlined.
#include <cmath>
struct Point {
  double x,y;
    
  Point()                        : x(0), y(0)   {}
  Point(double xx, double yy)    : x(xx), y(yy) {}
  Point(const Point&)            = default;
  Point& operator=(const Point&) = default;

  Point& operator= (double val)           {x  = val; y  = val; return *this;}
  Point& operator+=(const Point& p)       {x += p.x; y += p.y; return *this;}
  Point& operator-=(const Point& p)       {x -= p.x; y -= p.y; return *this;}
  Point& operator*=(double a)             {x *= a  ; y *= a  ; return *this;}
  Point& operator/=(double a)             {(*this)*=(1/a)    ; return *this;}
  bool   operator==(const Point& p) const {return x == p.x && y == p.y;     }
  bool   operator!=(const Point& p) const {return x != p.x || y != p.y;     }
  Point  operator+ (const Point& p) const {return {x + p.x, y + p.y};       }
  Point  operator- ()               const {return {-x, -y};                 }
  Point  operator+ ()               const {return {x, y};                   }
  Point  operator- (const Point& p) const {return {x - p.x, y - p.y};       }
  double angle     ()               const {return std::atan2(y, x);         }
  double operator* (const Point& p) const {return x * p.x + y * p.y;        }
  double operator^ (const Point& p) const {return x * p.y - y * p.x;        }
  Point  operator* ()               const {return (*this) / norm();         }
  Point  operator* (double a)       const {return {x * a, y * a};           }
  Point  operator/ (double a)       const {return (*this) * (1 / a);        }
  double norm2     ()               const {return (*this) * (*this);        }
  double norm      ()               const {return std::sqrt(norm2());       }

  static Point unitary(double angle) {return {std::cos(angle), std::sin(angle)};}
};

inline Point operator*(double a, const Point p) {return p * a;}

inline std::ostream& operator<<(std::ostream& os, const Point& p) {
  os << '(' << p.x << ", " << p.y << ')';
  return os;
}

inline std::istream& operator>>(std::istream& is, Point& p) {
  char c;
  is >> c >> p.x >> c >> p.y >> c;
  return is;
}

inline double d2(const Point& A, const Point& B) {
  Point tmp = B-A;
  return tmp*tmp;
}

Hervé Frezza-Buet,

Specifying RAM

A verbose structure

The type interface serie.hpp

The code implementation serie.cpp