4
\$\begingroup\$

Story

I was trying to solve a hard problem from Project Euler earlier today (continued from yesterday) and I wanted to graph some things up and play a little bit with fractions. To work with fractions, I decided to implement a little OOP-ish fraction class. I was hoping to brush up whatever little knowledge of C++ I have into trying and implementing a full blown templated project (as I don't practice software design very often and am relatively on the newer side of programming (1.8-ish years)). After fixing what seems like a million template errors (we all can agree on how terrible compilers are with reporting template errors), the following code is what I've arrived at in one day's work.

Code

/**
    Lost Arrow (Aryan V S)
    Monday 2020-10-19
**/

#ifndef FRACTION_H_INCLUDED
#define FRACTION_H_INCLUDED

#include <algorithm>
#include <stdexcept>
#include <type_traits>
#include <utility>

/**
 * The fraction class is meant to represent and allow usage of fractions from math.
 * It is represented by a numerator and a denominator (private context).
 * The interface provides you with simple operations:
 *      - Construction/Assignment
 *      - Comparison (equality/inequality, less/greater than, lesser/greater equal to, three-way (C++20 spaceship operator))
 *      - Arithmetic (addition/subtraction, multiplication/division)
 *      - Conversion (bool, decimal)
 *      - I/O Utility
 *      - Access/Modification
 */

template <typename T>
class fraction {
    /**
     * fraction <T> is implemented to work only with T = [integer types]
     * using floating point or any other types in fractions doesn't make sense.
     */
    static_assert(std::is_integral <T>::value, "fraction requires integral types");

  public:

    /**
     * Constructors
     */
    fraction ();
    fraction (const T&, const T&);
    fraction (T&&, T&&);
    fraction (const fraction&);
    fraction (fraction&&);
    fraction (const std::pair <T, T>&);
    fraction (std::pair <T, T>&&);

    /**
     * Assignment
     */
    fraction <T>& operator = (const fraction&);
    fraction <T>& operator = (fraction&&);

    /**
     * Access/Modification
     */
    T  nr () const;
    T  dr () const;
    T& nr ();
    T& dr ();
    std::pair <T, T>   value () const;
    std::pair <T&, T&> value ();

    /**
     * Utility
     */
    void print (std::ostream& = std::cout) const;
    void read  (std::istream& = std::cin);

    template <typename S>
    S decimal_value () const;
    std::pair <T, T>   operator () () const;
    std::pair <T&, T&> operator () ();
    operator bool() const;

    /**
     * Comparison
     */
    int8_t spaceship_operator (const fraction <T>&) const;
    template <typename S>
    friend bool operator == (const fraction <S>&, const fraction <S>&);
    template <typename S>
    friend bool operator != (const fraction <S>&, const fraction <S>&);
    template <typename S>
    friend bool operator <= (const fraction <S>&, const fraction <S>&);
    template <typename S>
    friend bool operator >= (const fraction <S>&, const fraction <S>&);
    template <typename S>
    friend bool operator <  (const fraction <S>&, const fraction <S>&);
    template <typename S>
    friend bool operator >  (const fraction <S>&, const fraction <S>&);

    /**
     * Arithmetic
     */
    fraction <T>& operator += (const fraction <T>&);
    fraction <T>& operator -= (const fraction <T>&);
    fraction <T>& operator *= (const fraction <T>&);
    fraction <T>& operator /= (const fraction <T>&);

  private:
    mutable T m_nr, m_dr;

    /**
     * Utility
     */
    void normalize () const;
};

/** ::normalize
 * The normalize utility function converts a fraction into its mathematically equivalent
 * "simplest" form.
 * The functions throws a domain error if the denominator is ever set to 0.
 */
template <typename T>
inline void fraction <T>::normalize () const {
    if (m_dr == 0)
        throw std::domain_error("denominator must not be zero");
    T gcd = std::gcd(nr(), dr());
    m_nr /= gcd;
    m_dr /= gcd;
}

/** ::spaceship_operator
 * The spaceship operator provides similar functionality as the <=> operator introduced in C++20.
 * If self  < other : return value is -1
 * If self == other : return value is  0
 * If self  > other : return value is  1
 */
template <typename T>
inline int8_t fraction <T>::spaceship_operator (const fraction <T>& other) const {
    normalize();
    other.normalize();

    if ((*this)() == other())
        return 0;

    if (nr() * other.dr() < other.nr() * dr())
        return -1;

    return 1;
}

/**
 * Constructors
 */
template <typename T>
fraction <T>::fraction ()
    : m_nr (0)
    , m_dr (1)
{ }

template <typename T>
fraction <T>::fraction (const T& nr, const T& dr)
    : m_nr (nr)
    , m_dr (dr)
{ normalize(); }

template <typename T>
fraction <T>::fraction (T&& nr, T&& dr)
    : m_nr (std::move(nr))
    , m_dr (std::move(dr))
{ normalize(); }

template <typename T>
fraction <T>::fraction (const fraction <T>& other)
    : fraction (other.nr(), other.dr())
{ }

template <typename T>
fraction <T>::fraction (fraction <T>&& other)
    : fraction (std::move(other.nr()), std::move(other.dr()))
{ }

template <typename T>
fraction <T>::fraction (const std::pair <T, T>& other)
    : fraction (other.first, other.second)
{ }

template <typename T>
fraction <T>::fraction (std::pair <T, T>&& other)
    : fraction (std::move(other.first), std::move(other.second))
{ }

/**
 * Assignment
 */
template <typename T>
fraction <T>& fraction <T>::operator = (const fraction <T>& other) {
    if (this != &other) {
        nr() = other.nr();
        dr() = other.dr();
    }
    return *this;
}

template <typename T>
fraction <T>& fraction <T>::operator = (fraction <T>&& other) {
    if (this != &other) {
        nr() = std::move(other.nr());
        dr() = std::move(other.dr());
    }
    return *this;
}

/** ::nr
 * An accessor function that returns a copy of the numerator value to the caller.
 */
template <typename T>
inline T fraction <T>::nr () const {
    return m_nr;
}

/** ::dr
 * An accessor function that returns a copy of the denominator value to the caller.
 */
template <typename T>
inline T fraction <T>::dr () const {
    return m_dr;
}

/** ::nr
 * An modification function that returns a reference of the numerator value to the caller.
 */
template <typename T>
inline T& fraction <T>::nr () {
    return m_nr;
}

/** ::dr
 * An modification function that returns a reference of the denominator value to the caller.
 */
template <typename T>
inline T& fraction <T>::dr () {
    return m_dr;
}

/** ::print
 * An utility function that prints to the standard output stream parameter in the form: nr/dr
 */
template <typename T>
inline void fraction <T>::print (std::ostream& stream) const {
    normalize();
    stream << nr() << "/" << dr();
}

/** ::read
 * An utility function that reads from the standard input stream in the form: nr dr
 */
template <typename T>
inline void fraction <T>::read (std::istream& stream) {
    stream >> nr() >> dr();
    normalize();
}

/** ::decimal_value
 * An utility function that converts a fraction to its mathematically equivalent floating point representation
 * This function requires its template type as a floating point type.
 */
template <typename T>
template <typename S>
inline S fraction <T>::decimal_value () const {
    static_assert(std::is_floating_point <S>::value, "decimal notation requires floating point type");
    normalize();
    return static_cast <S> (nr()) / static_cast <S> (dr());
}

/** ::value
 * An utility function that returns a standard pair with the copy of the numerator and denominator to the caller.
 */
template <typename T>
inline std::pair <T, T> fraction <T>::value () const {
    return std::pair <T, T> (nr(), dr());
}

/** ::value
 * An utility function that returns a standard pair with a refernce to the numerator and denominator to the caller.
 */
template <typename T>
inline std::pair <T&, T&> fraction <T>::value () {
    return std::pair <T&, T&> (nr(), dr());
}

/** ::operator ()
 * Provides same functionality as ::value with copy.
 */
template <typename T>
inline std::pair <T, T> fraction <T>::operator () () const {
    return value();
}

/** ::operator ()
 * Provides same functionality as ::value with reference.
 */
template <typename T>
inline std::pair <T&, T&> fraction <T>::operator () () {
    return std::pair <T&, T&> (nr(), dr());
}

/** ::bool()
 * Converts a fraction to a boolean value which is false if the numerator is 0.
 */
template <typename T>
inline fraction <T>::operator bool() const {
    return bool(nr());
}

/**
 * Comparison (implemented with the spaceship_operator
 */
template <typename S>
inline bool operator == (const fraction <S>& left, const fraction <S>& right) {
    return left.spaceship_operator(right) == 0;
}

template <typename S>
inline bool operator != (const fraction <S>& left, const fraction <S>& right) {
    return left.spaceship_operator(right) != 0;
}

template <typename S>
inline bool operator <= (const fraction <S>& left, const fraction <S>& right) {
    return left.spaceship_operator(right) <= 0;
}

template <typename S>
inline bool operator >= (const fraction <S>& left, const fraction <S>& right) {
    return left.spaceship_operator(right) >= 0;
}

template <typename S>
inline bool operator < (const fraction <S>& left, const fraction <S>& right) {
    return left.spaceship_operator(right) == -1;
}

template <typename S>
inline bool operator > (const fraction <S>& left, const fraction <S>& right) {
    return left.spaceship_operator(right) == 1;
}

/**
 * Arithmetic
 */
template <typename T>
fraction <T>& fraction <T>::operator += (const fraction <T>& other) {
    normalize();
    other.normalize();
    T lcm = std::lcm(dr(), other.dr());
    nr() = nr() * (lcm / dr()) + other.nr() * (lcm / other.dr());
    dr() = lcm;
    normalize();
    return *this;
}

template <typename T>
fraction <T>& fraction <T>::operator -= (const fraction <T>& other) {
    return *this += fraction <T> (-other.nr(), other.dr());
}

template <typename T>
fraction <T>& fraction <T>::operator *= (const fraction <T>& other) {
    normalize();
    other.normalize();
    nr() *= other.nr();
    dr() *= other.dr();
    normalize();
    return *this;
}

template <typename T>
fraction <T>& fraction <T>::operator /= (const fraction <T>& other) {
    return *this *= fraction <T> (other.dr(), other.nr());
}

template <typename T>
fraction <T> operator + (fraction <T>& left, fraction <T>& right) {
    fraction <T> result (left);
    return result += right;
}

template <typename T>
fraction <T> operator - (fraction <T>& left, fraction <T>& right) {
    fraction <T> result (left);
    return result -= right;
}

template <typename T>
fraction <T> operator * (fraction <T>& left, fraction <T>& right) {
    fraction <T> result (left);
    return result *= right;
}

template <typename T>
fraction <T> operator / (fraction <T>& left, fraction <T>& right) {
    fraction <T> result (left);
    return result /= right;
}

#endif // FRACTION_H_INCLUDED

Questions and other stuff

According to modern programming standards in C++, how well is my code written? According to software engineering standards, what are the areas I need to improve in? Is my code efficient and well written? Are there any ways I could speed up some computations for efficiency? What improvements to the interface are possible? What could I clean up or refactor in my code? Other relevant insights and tips/discussion/reviews will be appreciated.

To make my implementation more efficient, I'm thinking that I have normalize() at a lot of places which runs in O(log(a.b)) and I could add another private variable which checks if a fraction has been normalized or not. This could get rid of redundant runs on normalize. Any other suggestions will be warmly welcomed.

Please don't mind the terrible documentation. I would really do that part much better if my goal was to write a fraction implementation for the sake of writing a fraction implementation and not for solving some problem, and if I were to not have to finish it in one days work. Also, any comments on a good procedure to document stuff are welcome (I know this is subjective and different people have different answers to this but something like a short 101 will likely provide helpful info for future projects).

Thanks SE Community!

\$\endgroup\$
2
  • \$\begingroup\$ Seems like I forgot implementing assignment completely... It's 03:30 AM where I live and this is the best thing I've got to do. Programming makes you do weird things. \$\endgroup\$
    – Arrow
    Oct 19, 2020 at 22:02
  • \$\begingroup\$ Another question: If I have a big integer arithmetic implementation and would like to use it as a template parameter in the above code, is there a possibility that I could do an integer type check on the big integer class with features from C++20? Something involving concepts maybe? \$\endgroup\$
    – Arrow
    Oct 19, 2020 at 22:10

1 Answer 1

4
\$\begingroup\$

Overview

Prety good. Big points.

  • Move Semantics should be noexcept
  • Overuse of normalize() is going to make the class ineffecient.
    I would only normalize for printing personally.
  • Don't use nr() when m_nr is just as valid.
    You are already tightly bound in all other member functions.
  • read() should not change the state of the object if it fails.

Things You should probably do:

  • I would add a swap()
  • Put one liners into the class definition.
  • Put forward declarations of the arithmatic operations next to the class.
    I should not need to read all the code to find them.
  • print/read should be symetric

Code Review

Best practice would to put this in a namespace.


This works:

    /**
     * fraction <T> is implemented to work only with T = [integer types]
     * using floating point or any other types in fractions doesn't make sense.
     */
    static_assert(std::is_integral <T>::value, "fraction requires integral types");

But since you specified C++20 should you not be using concepts (require rather than static_assert). Not very familiar with the exact definitions yet so don't know how to do it myself.


The move opertator should be noexcept:

fraction (fraction&&)                  noexcept;
fraction <T>& operator = (fraction&&)  noexcept;

When your object is used in a standard container this helps. Becuase the standard gurantees the "Strong Excetpion Gurantee" on some operations it must use the copy semantics when resizing; unless you guranted (with noexcept) that you can not throw an exception then it can use move semantics and speed up these operations.


You have the normal assignment operators.

    fraction (const T&, const T&);
    fraction (T&&, T&&);

    fraction <T>& operator = (const fraction&);
    fraction <T>& operator = (fraction&&);

But since this type is supposed to represent integers. It should be able to support just assigning integers to directly. I would allow the construction/assignment with a single integer (and use a 1 as bottom of the fraction).

    fraction (const T& n, const T& d = 1);
    fraction (T&& n, T&& d = 1);

    fraction <T>& operator = (const fraction&);
    fraction <T>& operator = (fraction&&);

    // I would provide these explicitly
    // Otherwise the compiler will generate a conversion with a single
    // parameter constructor and then use the assignment above. This
    // may be slightly sub optimal.
    fraction <T>& operator = (const T&);
    fraction <T>& operator = (T&&);

Return these by const reference.

    T  nr () const;
    T  dr () const;

You mention that T may be some "Big Integer" implementation not just a standard POD int. So you want to avoid a copy if you don't actually need it.

    T const& nr () const;
    T const& dr () const;
               ^  not a fan of this space.

You give accesses to the internal state.

    T& nr ();
    T& dr ();

This makes redundant your use of normalize() in the constructor. You no longer gurantee that the fraction is normalized.


Not sure I like this.

    std::pair <T&, T&> value ();

Not going to argue against it. But it seems like you are giving accesses to the internals without good reason.


Like this:

    void print (std::ostream& = std::cout) const;
    void read  (std::istream& = std::cin);

Don't see the friend functions to help printing:

    friend std::ostream& operator<<(std::ostream& st, fraction const& d)
    {
        d.print(str);
        return str;
    }
    friend std::istream& operator>>(std::istream& st, fraction& d)
    {
        d.read(str);
        return str;
    }

I would always make the bool operator explicit. This will prevent an accidental conversion to bool in contexts that you don't want it happening.

    operator bool() const;

The reason to make these free standing functions (FSF) rather than members is to allow symetric auto conversion. i.e. If they are members only the rhs could be auto converted to a fraction. If these are non member then both the lhs or the rhs can by auto converted to fractions.

    friend bool operator == (const fraction <S>&, const fraction <S>&);
    ... etc

Notrmally not a fan of auto conversion. But this use case it is a good idea. Unfortunately you don't provide the appropriate constructions to allow auto conversion from an integer type to a fraction (you need a single argument constructor).


If you create these:

    fraction<T>& operator += (const fraction <T>&);
    ... etc

Then why don't you implement:

    fraction<T> operator + (fraction<T> const& lhs, fraction<T> const& rhs);
    ... etc

these are FSF for the same reason as these:

friend bool operator == (const fraction <S>&, const fraction <S>&);

This is not a good use of mutable.

    mutable T m_nr, m_dr;

Mutable should be used on members that don't represent the state of the object. i.e. you are caching some printable value. i.e. It has a state that is expensive to compute so you keep it around but it could be easily re-computed from the members that actually represent the state of the obejct.


No need to call nr() inside the class simply use m_nr.

    T gcd = std::gcd(nr(), dr());

Is normalize() a rather expensive operation?

inline int8_t fraction <T>::spaceship_operator (const fraction <T>& other) const {

Thus calling it as part of a comparison seems overkill.

    normalize();
    other.normalize();

Why not calcualte the value and do a comparison?

    double lhsTest = 1.0 * m_nr/m_dr;
    double rhsTest = 1.0 * other.m_nr/other.m_dr;

In comparison to normalization this is relatively cheap? I think?


I would not bother to normalize during construction.

fraction <T>::fraction (const T& nr, const T& dr)
    : m_nr (nr)
    , m_dr (dr)
{ normalize(); }

You don't gurantee that the object will remain normalized (As you give access to the internal members. So why do this expensive operation each time. I would simply save normalization for printing.


I prefer the standard Copy and Swap Idiom here.

template <typename T>
fraction <T>& fraction <T>::operator = (const fraction <T>& other) {
    if (this != &other) {
        nr() = other.nr();
        dr() = other.dr();
    }
    return *this;
}

The check for assignment to self is a test for something that basically never happens and is thus a pessimization in real code (obviously it still needs to work with assignment to self). But the copy and swap gets away from this by always doing the copy (which may seem like a pesimization but in real life is not as you don't get the branch prediction reset).


Prefer the swap implementation of this:

template <typename T>
fraction <T>& fraction <T>::operator = (fraction <T>&& other) {
    if (this != &other) {
        nr() = std::move(other.nr());
        dr() = std::move(other.dr());
    }
    return *this;
}

Again. no need for a self assignment test.


I would also add a swap() method and swap() friend function:

  void fraction<T>::swap(fraction<T>& other) noexpcept
  {
      using std::swap;
      swap(m_nr, other.m_nr);
      swap(m_dr, ither.m_dr);
  }
  friend void swap(fraction<T>& lhs, fraction<T>& rhs)
  {
      lhs.swap(rhs);
  }

I don't like the external definition of functions that are this simple.

template <typename T>
inline T fraction <T>::nr () const {
    return m_nr;
}

One liner functions should be part of the class declaration.


inline void fraction <T>::print (std::ostream& stream) const {
    normalize();
    stream << nr() << "/" << dr();
              ^^^^ You are inside the class.
                   You are already tightly coupled to the implementation.
                   You should simply use m_nr.
}

Here is "about" the only time I would normalize fraction. Printing is already relatively slow operation, so normalizing is not going to add a great cost relatively speaking.

I would implement this function like this:

void fraction <T>::print (std::ostream& stream) const
{
    fraction<T>   temp(*this);
    temp.normalize(); // Now normalize can happen on a non cost object.

    stream << temp.m_nr << "/" << temp.m_dr;
}

I would want the read operation to be symetric with the print() function. Thus I would expect it to read and discard the / operator.

Also the read operation should only mutate the current object if the read succedes. So I would change it slightly.

void fraction<T>::read(std::istream& stream)
{
    fraction<T>    temp
    char           div;
    if ((stream >> temp.m_nr >> div >> temp.m_dr) && div == '/') {
        // read worked and we have correct seporator.
        // so we can update the state of the object.
        temp.swap(*this);
    }
    else {
        // some failure. Make sure the stream is marked bad.
        stream.setstate(std::ios::badbit);
    }
}

That seems like a non optimal comparison.

inline bool operator == (const fraction <S>& left, const fraction <S>& right) 
{
    return left.spaceship_operator(right) == 0;
}

Quite expensive if it is not eual.


You don't need to call normalize three times!! Call it once at the end of the operation (if you must). I would not bother (unless there is some overflow issue).

PS. You missed the inline here.

template <typename T>
fraction <T>& fraction <T>::operator += (const fraction <T>& other) {
    normalize();
    other.normalize();
    T lcm = std::lcm(dr(), other.dr());
    nr() = nr() * (lcm / dr()) + other.nr() * (lcm / other.dr());
    dr() = lcm;
    normalize();
    return *this;
}

This can be simplified to:

fraction<T>& fraction<T>::operator+=(fraction <T> const& other)
{
    if (m_dr == other.m_dr) {
        m_nr += other.m_nr;
    }
    else {
        m_nr = (other.m_nr * m_dr) + (m_nr * other.m_dr);
        m_dr = m_dr * other.m_dr;
        if (m_dr > SOME_BOUNDRY_CONDITION) {
            normalize();
        }
    }
    return *this;
}
// Notice the lhs is passed by value to get a copy.
// So we don't need to do an explicit copy in the function;
fraction<T> operator+(fraction<T> lhs, fraction<T> const& rhs) {return lhs += rhs;}
\$\endgroup\$
7
  • 1
    \$\begingroup\$ Short review review: I think there's a note about = defaulting the move and copy constructors as well as operator= missing. \$\endgroup\$
    – Zeta
    Oct 20, 2020 at 10:09
  • \$\begingroup\$ I'm amazed at the level of detail you've provided Martin. Huge thanks for the effort and time you've taken! There are a lot of things you've mentioned. I'm going to be replying to some of them in these comments. Just to make sure that I don't end up commenting too much, I'll try to comment about things I'm not familiar with and the new things I'm seeing. \$\endgroup\$
    – Arrow
    Oct 20, 2020 at 10:16
  • \$\begingroup\$ (1) Yes, I should be using concepts but because I don't have a g++ version which supports C++20 features, this is how it's gonna have to be for now. (2) I believe I've missed a lot of things as this was a one day build to get stuff done. It was a nice point of defaulting denominators to 1 in the constructors to represent integers. (3) I still have no idea how I could use Big Integer type a parameter as the static assertion prevents me from doing so. Maybe when I can use C++20, it'd be easier to intuitively understand what to do to make it work. \$\endgroup\$
    – Arrow
    Oct 20, 2020 at 10:26
  • \$\begingroup\$ (4) I figured as much about the redundant calls to normalize(). Again, I was trying to solve a problem which is why I implemented this. I didn't want to deal with any sort of stupid overflow that might occur. However, in the worst cases, the calls don't really do anything. I'll work on fixing that. (5) The reason why I have std::pair <T&, T&> value (); is because I thought it might look cool to do stuff like f.value() = some_pair. I'm immature I guess. (6) I haven't add the friend functions for i/ostream into the header because the end user could want to print/read data in their own way. \$\endgroup\$
    – Arrow
    Oct 20, 2020 at 10:31
  • 1
    \$\begingroup\$ I'll edit my question with revised code.: Don't do that. Ask a new question with the new code. If you look at my submissions here I can go through 4/5 revisions in 4/5 different questions. \$\endgroup\$ Oct 20, 2020 at 16:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.