實習課第十次作業

tags: NTOU CSE C++ Programming

教學文件和作業說明文件： https://hackmd.io/@kogiokka/ntou-cse-cpp-nav

本次主題是運算子多載（operator overloading）。

實習目標 ：

1. class 基本語法
2. operator new 和 operator delete
3. operator overloading (<< = += ++)

需求

• 承第九次實習作業，擴增 BigInt 讓它可以存放負數，並且實作相關的加法運算。
• 不可用 malloc 和 free 函式。必須用到operator new 和 operator delete。
• 完成下列的 BigInt 運算子多載：operator=、operator+=、operator++ 和 operator<<。其中 operator+= 和 operator++ 必須是 BigInt 的成員函式。

提示

多了負整數的加法運算需要考慮的東西比較多，兩整數相加變成有下列 4 種可能：

• 正整數.Add(正整數)
• 正整數.Add(負整數)
• 負整數.Add(正整數)
• 負整數.Add(負整數)

依照這 4 種可能可以再歸納出 2 種情形：

• 同號相加
• 異號相加

如果是異號相加，必須考慮其中一方是否有足夠的高位數可以消去，有和沒有會影響到如何處理每一個位數。由此我們可以推論異號相加時，程式至少要走過每個位數 2 次。先比大小再相加，或是先對位數相加再處理進位問題。

範例程式

• 第十次範例程式：MyInt、BigInt_operators（Google Drive）
• BigInt_operators 是接續第九次實習作業的 BigInt 程式碼。取消註解測試案例後執行會報錯，請修正 BigInt 建構子的 bug。
• 如果你不是用 CMake 設定專案，請將測試檔（Test1.txt）存成檔案後跟可執行檔放在相同的資料夾。
• 使用 CMake 搭配 Visual Studio 的話可執行檔和測試檔會自動放在 install/ 資料夾之下，不用額外做設定。其他環境下可能要設定安裝路徑的變數： CMAKE_INSTALL_PREFIX。如果不是使用 Visual Studio，可能需要自行定義 CMAKE_INSTALL_PREFIX 變數，並做其他設定。詳情請見CMake專案建置的「CMake安裝指令的相關設定」一節。
• 專案的資料夾路徑不能有中文字元，否則用 Visual Studio 編譯 CMake 專案會出錯。

MyInt

編譯和執行

不是使用 Visual Studio 嗎？請見 CMake專案建置。

在 Visual Studio 選擇開啟本機資料夾或檔案 → 開啟 → 資料夾，並選擇MyInt/的資料夾。Visual Studio 會自動開始設定 CMake 專案，可能會花一點時間。

等待輸出欄位的訊息跑完之後，在上方工具列的選取啟動項目選 myint.exe 就可以自動編譯執行了。

專案目錄結構

MyInt
├── MyInt.cpp
└── CMakeLists.txt

原始碼

CMakeLists.txt

cmake_minimum_required(VERSION 3.12)
project("My Integer")
add_executable(myint)
target_sources(myint PRIVATE "MyInt.cpp")

MyInt.cpp

/**
   指派運算子（Assignment operators）
   ---------------------------------

   以下列出一些常見指派運算子的函式原型（prototype）。

   類別成員的運算子多載：

      class T
      {

          // 簡單指派運算子（Simple assignment operator）
          T& operator=(const T2& b);

          // 複合指派運算子（Compound assignment operators）
          T& operator+=(const T2& b); // Addition assignment
          T& operator-=(const T2& b); // Subtraction assignment
          T& operator*=(const T2& b); // Multiplication assignment
          T& operator/=(const T2& b); // Division assignment

          // and more...
      };

   非類別成員的運算子多載：

      // 簡單指派運算子（Simple assignment operator）
      // operator= 不允許為非類別成員。

      // 複合指派運算子（Compound assignment operators）
      T& operator+=(T& a, const T2& b); // Addition assignment
      T& operator-=(T& a, const T2& b);  // Subtraction assignment
      T& operator*=(T& a, const T2& b);  // Multiplication assignment
      T& operator/=(T& a, const T2& b);  // Division assignment

      // and more...


   T2 可以是包括 T 在內的任何型別。

   C++ 中所有內建的指派運算子函式都是回傳 *this。大多數使用者自定義的運算子多載
   函式也是回傳 *this，這樣運算子的使用方式才會和內建的一致。雖然如此， C++ 仍
   允許自定義的運算子回傳任何型別，包括 void。


   遞增/遞減運算子（Increment/decrement operators）
   -----------------------------------------------

   以下列出遞增/遞減運算子的函式原型（prototype）。

   類別成員的運算子多載：

      // 前綴遞增/遞減
      T& T::operator++();   // pre-increment
      T& T::operator--();   // pre-decrement

      // 後綴遞增/遞減
      T T::operator++(int); // post-increment
      T T::operator--(int); // post-decrement


   非類別成員的運算子多載：

      // 前綴遞增/遞減
      T& operator++(T& a);
      T& operator--(T& a);

      // 後綴遞增/遞減
      T operator++(T& a, int);
      T operator--(T& a, int);


   C++ 中所有內建的前綴版本都是回傳參照（references），而後綴版本都是回傳值（
   values）。使用者自定義的運算子多載通常也是遵守這個規則 。然而 C++ 允許自定義
   的運算子回傳任何型別，包括 void。

   後綴版本的 int 參數為虛設參數，是為了在 C++ 中區分前綴和後綴函式而加的，並無
   實際作用。函式多載時，若兩函式參數型別和數量一樣就會產生歧義，因為 C++ 無法
   以不同回傳值型別區分函式。


   參考資料
   --------

    * https://en.cppreference.com/w/cpp/language/operator_assignment
    * https://en.cppreference.com/w/cpp/language/operator_incdec

*/

// Declarations (MyInt.h)
// ==============================================================================

#include <ostream>

class MyInt
{
    int* m_value;

    friend MyInt& operator+=(MyInt&, int);
    friend MyInt& operator-=(MyInt&, int);
    friend std::ostream& operator<<(std::ostream&, const MyInt&);

public:
    MyInt();
    explicit MyInt(int value);

    /**
       複製建構子（Copy constructor）
     */
    MyInt(const MyInt& other);
    ~MyInt();

    /**
       複製指派運算子（Copy assignment operator）。只能接受一個參數，參數型別可
       以是 MyInt、MyInt& 或 const MyInt& 。
     */
    MyInt& operator=(const MyInt& other);

    MyInt& operator=(int value);
    MyInt& operator+=(const MyInt& other);
    MyInt& operator-=(const MyInt& other);
    MyInt& operator++();
    MyInt operator++(int);
};

// Definitions (MyInt.cpp)
// =============================================================================

// Member functions
// -----------------------------------------------------------------------------
#include <cassert>
#include <cstring>
#include <iostream>

using std::cout;
using std::endl;
using std::ostream;

MyInt::MyInt()
    : m_value(new int[1])
{
    *m_value = 0;
    cout << "[info] [MyInt][member] Default constructor" << endl;
}

MyInt::MyInt(int value)
    : m_value(new int[1])
{
    *m_value = value;
    cout << "[info] [MyInt][member] Constructor" << endl;
}

MyInt::MyInt(const MyInt& other)
    : m_value(new int[1])
{
    *m_value = *other.m_value;
    cout << "[info] [MyInt][member] Copy constructor" << endl;
}

MyInt::~MyInt()
{
    assert(m_value != nullptr);
    delete[] m_value;
    cout << "[info] [MyInt][member] Destructor" << endl;
}

MyInt& MyInt::operator=(const MyInt& other)
{
    *m_value = *other.m_value;
    cout << "[info] [MyInt][member] Copy assignment operator" << endl;
    return *this;
}

MyInt& MyInt::operator=(int value)
{
    *m_value = value;
    cout << "[info] [MyInt][member] Assignment operator" << endl;
    return *this;
}

MyInt& MyInt::operator+=(const MyInt& other)
{
    *m_value += *other.m_value;
    cout << "[info] [MyInt][member] Addition assignment operator" << endl;
    return *this;
}

MyInt& MyInt::operator-=(const MyInt& other)
{
    *m_value -= *other.m_value;
    cout << "[info] [MyInt][member] Subtraction assignment operator" << endl;
    return *this;
}

MyInt& MyInt::operator++()
{
    *m_value += 1;
    return *this;
}

MyInt MyInt::operator++(int)
{
    MyInt temp(*this);
    *m_value += 1;
    return temp;
}

// Non-member functions
// -----------------------------------------------------------------------------

MyInt& operator+=(MyInt& n1, int n2)
{
    *n1.m_value += n2;
    cout << "[info] [MyInt][friend] Addition assignment operator" << endl;
    return n1;
}

MyInt& operator-=(MyInt& n1, int n2)
{
    *n1.m_value -= n2;
    cout << "[info] [MyInt][friend] Subtraction assignment operator" << endl;
    return n1;
}

ostream& operator<<(ostream& out, const MyInt& number)
{
    out << *number.m_value;
    return out;
}

// main.cpp
// ==============================================================================

int main()
{
    char divider[81];
    memset(divider, '=', 80);
    divider[80] = '\0';

    {
        MyInt a(15);
        a += 16;
        cout << "a: " << a << endl;
    }

    cout << divider << endl;

    {
        MyInt a1(100);
        MyInt a2;
        a2 = a1;
        MyInt a3 = a1 = 10;
        MyInt a4(a1);

        cout << "a1: " << a1 << endl;
        cout << "a2: " << a2 << endl;
        cout << "a3: " << a3 << endl;
        cout << "a4: " << a4 << endl;
    }

    cout << divider << endl;

    {
        MyInt a(100);
        MyInt b(50);
        MyInt c(10);

        a += b += c += 99;
        cout << "a: " << a << endl;

        a -= b -= c -= 99;
        cout << "a: " << a << endl;
    }

    cout << divider << endl;

    {
        MyInt a(100);
        MyInt b(50);
        MyInt c(10);

        a.operator+=(b).operator+=(c) += 99;
        cout << "a: " << a << endl;

        a.operator-=(b).operator-=(c) -= 99;
        cout << "a: " << a << endl;
    }

    cout << divider << endl;

    {
        int x = 99;
        cout << ++x << endl; // 100
        cout << x++ << endl; // 100
        cout << x << endl;   // 101

        MyInt y(99);
        cout << ++y << endl; // 100
        cout << y++ << endl; // 100
        cout << y << endl;   // 101
    }

    return 0;
}

BigInt_operators

專案目錄結構

BigInt_operators
├── BigInt.cpp
├── BigInt.hpp
├── CMakeLists.txt
├── main.cpp
└── Test1.txt

編譯和執行

不是使用 Visual Studio 嗎？請見 CMake專案建置。

在 Visual Studio 選擇開啟本機資料夾或檔案 → 開啟 → 資料夾，並選擇 BigInt_operators/的資料夾。Visual Studio 會自動開始設定 CMake 專案，可能會花一點時間。

等待輸出欄位的訊息跑完之後，在上方工具列的選取啟動項目選 bigint.exe (安裝) 就可以自動編譯執行了。

原始碼

CMakeLists.txt

cmake_minimum_required(VERSION 3.12)

project("Big Integer")

add_executable(bigint)

target_sources(bigint
PRIVATE
    "main.cpp"
    "BigInt.cpp"
)

install(TARGETS bigint DESTINATION .)
install(FILES
    "${CMAKE_SOURCE_DIR}/Test1.txt"
    DESTINATION .)

BigInt.hpp

#ifndef BIGINT_H
#define BIGINT_H

#include <ostream>

/**
 * @class BigInt
 *
 * Arbitrary-precision integers. BigInt provides addition operations.
 */
class BigInt
{
    friend std::ostream& operator<<(std::ostream&, const BigInt&);

public:
    /**
       Default constructor. Create a BigInt with default value 0 and default
       capacity 10.
     */
    BigInt();

    /**
       Destructor. Destroy the instance and release the memory.
     */
    ~BigInt();

    /**
       Constructor. Create a BigInt with an integer.
     */
    explicit BigInt(const int value, const int size = 10);

    /**
       Constructor. Create a BigInt with a string.
     */
    explicit BigInt(const char* const value, const int size = 10);

    /**
       Copy Constructor. Create a BigInt with another BigInt.
     */
    BigInt(const BigInt& value);

    /**
       Addition operation. Add another BigInt.
     */
    void Add(const BigInt& value);

    /**
       Addition operation. Add a value from an integer.
     */
    void Add(const int value);

    /**
       Addition operation. Add a value from a string.
     */
    void Add(const char* const value);

    /**
       Reset the integer to zero.
     */
    void SetZero();

    /**
       Write the integer to the standard output.
     */
    void PrintValue() const;

    /**
       Assignment Operators
     */
    // BigInt& operator=(int value);
    // BigInt& operator=(const BigInt& other);
    // BigInt& operator+=(int value);
    // BigInt& operator+=(const BigInt& other);

    /**
       Increment/Decrement Operators
     */
    // BigInt& operator++();
    // BigInt operator++(int);

private:
    /// An dynamic array storing the digits.
    int* m_digits;

    /// Size of the dynamic array.
    int m_capacity;

    /// Number of digits in the integer
    int m_numDigits;

    /// sign of the integer
    int m_sign;
};

#endif

BigInt.cpp

#include "BigInt.hpp"

#include <cassert>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <sstream>

using std::cout;
using std::endl;
using std::ostream;
using std::ostringstream;
// using std::realloc;

BigInt::BigInt()
{
    m_capacity = 100;
    m_digits = new int[m_capacity];
    SetZero();
}

BigInt::~BigInt()
{
    assert(m_digits != nullptr);

    delete[] m_digits;
}

/// BUG
BigInt::BigInt(const char* const value, const int size)
    // Member initialization list.
    // Set initial values of the member variables.
    : m_digits(nullptr)
    , m_capacity(size)
    , m_numDigits(0)
{
    int numDigits = strlen(value);

    if (numDigits > size)
        return;

    m_digits = new int[m_capacity];
    m_numDigits = numDigits;
    SetZero();

    for (int i = 0; i < m_numDigits; i++) {
        if (value[i] < '0' || value[i] > '9') {
            break;
        }
        m_digits[i] = value[m_numDigits - i - 1] - 48;
    }
}

BigInt::BigInt(const int value, const int size)
    : m_digits(nullptr)
    , m_capacity(size)
    , m_numDigits(0)
{
    // TODO
}

BigInt::BigInt(const BigInt& other)
    : m_digits(nullptr)
    , m_capacity(other.m_capacity)
    , m_numDigits(other.m_numDigits)
{
    // TODO
}

void BigInt::PrintValue() const
{
    ostringstream oss;

    if (m_numDigits == 0) {
        oss << '0';
    } else {
        for (int i = m_numDigits - 1; i >= 0; i--) {
            oss << m_digits[i];
        }
    }

    cout << oss.str() << endl;
}

void BigInt::SetZero()
{
    for (int i = 0; i < m_capacity; i++) {
        m_digits[i] = 0;
    }

    m_numDigits = 0;
}

void BigInt::Add(const BigInt& value)
{
    // TODO
}

void BigInt::Add(const int value)
{
    // TODO
}

void BigInt::Add(const char* const value)
{
    // TODO
}

main.cpp

#include "BigInt.hpp"

#include <fstream>
#include <iostream>
#include <string>

using std::cerr;
using std::cout;
using std::endl;

// void testBigInt();
// void testBigInt2(BigInt sum, const std::string& filename);

int main()
{
    cout << R"(
              _                     _  _
            /' `\                  ' /' `         /'
          /'     )                 /'         --/'--               .-~)
        /' (___,/'O  ____        /' ,____     /'                  ;_.~
      /'     )  /' /'    )     /'  /'    )  /'               __--~|
    /'      /'/' /'    /'    /'  /'    /' /'               ,~     |__
(,/' (___,/' (__(___,/(__(,/(_,/'    /(__(__               `.__--~`.
                   /'
           /     /'
          (___,/'

                                                       /'
                                                   --/'--
     ____     ____     ____      ____     ____     /' ____     ____     ____
   /'    )--/'    )--/'    )   )'    )--/'    )  /' /'    )--)'    )--/'    )--
 /'    /' /'    /' /(___,/'  /'       /'    /' /' /'    /' /'        '---,
(___,/' /(___,/'  (________/'        (___,/(__(__(___,/' /'        (___,/
      /'
    /'
  /'

)";
    cout << "CMake project setup successfully." << endl;
    cout << "Uncomment the test cases to proceed." << endl;

    // testBigInt();
    // testBigInt2(BigInt(), "Test1.txt");

    return 0;
}

/**
// Test cases

void testBigInt()
{
    BigInt x, y("-1234"), z("+00000987654321");
    x.PrintValue();
    y.PrintValue();
    z.PrintValue();

    cout << x << ' ' << y << ' ' << z << endl;
    // Ans: +0 -1234 [phone]

    x = z = y;
    cout << x << ' ' << y << ' ' << z << endl;
    // Ans: -1234 -1234 -1234

    x = y = -123;
    z = 123;
    cout << x << ' ' << y << ' ' << z << endl;
    // Ans: -123 -123 +123

    x = 123;
    y = -123;
    z = -99;
    x += z;
    y += z;
    cout << x << ' ' << y << ' ' << z << endl;
    // Ans: +24 -222 -99

    x = 123;
    y = -123;
    z = 99;
    x += z;
    y += z;
    cout << x << ' ' << y << ' ' << z << endl;
    // Ans: +222 -24 +99

    x = 99;
    y = ++x;
    z = x++;
    cout << x << ' ' << y << ' ' << z << endl;
    // Ans: +101 +100 +100

    x = -100;
    y = ++x;
    z = x++;
    cout << x << ' ' << y << ' ' << z << endl;
    // Ans: -98 -99 -99
}

void testBigInt2(BigInt sum, const std::string& filename)
{
    std::ifstream file;
    file.open(filename);
    if (file.fail()) {
        cerr << "Cannot read the file: " << filename << endl;
        return;
    }

    std::string num;
    while (file >> num) {
        sum.Add(num.c_str());
        sum.PrintValue();
    }
    file.close();
}
*/

測試檔：Test1.txt

400964665703314527979359727778963866579483469756336732289380625240474297077199803425307972262806030610567501210954993735863224880451383004470538328521215944251611888945298850040589115412875069594507356891333
-95028625771685543131108255483614436379337582332251805552583208181992408407296353411797989426285029254704497786996333515399584296666977772059517583859528178787632017680035827459619620352851391493898243583245921
-137648733864466971164366752021498418277175869696382367841576999523574220716470237089158575032811478133986379351117203009362854063711959411019193310368710809004499062919974498657642831235585018605061378089680896
32760398659743139137119286981116623549967856987739003546295325886610664530519916427219740857809131795888758285565894316228359267163446339822568007867753172543070776974953930680518993834069234428004607985344053248
7796974881018867114634390301505756404892349963081882844018287561013338158263740109678298324158573367421524471964682847262349505584900228877771185872525255065250844920039035501963520532508477793865096700511884673024
-1855680021682490373282984891758370024364379291213488116876352439521174481666770146103435001149740461446322824327594517648439182329206254472909542237661010705529701090969290449467317886737017714939893014721828552179712
-441651845160432708841350404238492065798722271308810171816571880606039526636691294772617530273638229824224832189967495200328525394351088564552471052563320547916068859650691126973221657043410216155694537503795195418771456
105113139148182984704241396208761111660095900571496820892344107584237407339532528155882972205125898698165510061212263857678189043855559078363488110510070290404024388596864488219626754376331631445055299925903256509667606528
25016927117267550359609452297685144575102824336016243372377897605048502946808741701100147384819963890163391394568518798127408992437623060650510170301396729116157804486053748196271167541566928283923161382364975049300890353664

參考資料

• 16章 課本例題
• 18章 課本例題

cppreference

• operator overloading
• Assignment operators
• Increment/decrement operators

Learn C++

• Overloading the arithmetic operators using friend functions
• Overloading operators using normal functions
• Overloading the I/O operators
• Overloading operators using member functions

其他

• 運算子多載, docs.microsoft.com
• CppCoreGuidelines - c62-make-copy-assignment-safe-for-self-assignment, github.com