實習課第十一次作業

tags: `NTOU CSE C++ Programming`

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

實習目標：

operators new and delete
static class members
Operator Functions:
- Class Members
- friend Functions
class inheritance
C++容器 vector

需求

實作 class MyString，模擬 C++ 函式庫中的std::string。
使用類別繼承語法實作 class MyString_Derived，MyString_Derived 繼承 MyString。
使用 new 和 delete（不可用 malloc 和 free）
完成的 MyString 和 MyString_Derived 類別須通過範例程式提供的測試案例。

範例程式

實習第十一次範例程式：MyString、vector（Google Drive）
專案的資料夾路徑不能有中文字元，否則用 Visual Studio 編譯 CMake 專案會出錯。

MyString

編譯和執行

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

在 Visual Studio 選擇開啟本機資料夾或檔案 → 開啟 → 資料夾，並選擇MyString/的資料夾。Visual Studio 會自動開始設定 CMake 專案，可能會花一點時間。等待輸出欄位的訊息跑完之後，在上方工具列的選取啟動項目選mystring.exe 就可以自動編譯執行了。

專案目錄結構

MyString
├── CMakeLists.txt
├── Inheritance.cpp
├── Inheritance.hpp
├── main.cpp
├── MyString.cpp
└── MyString.hpp

原始碼

CMakeLists.txt












cmake_minimum_required(VERSION 3.12)

project("My String")

add_executable(mystring)

target_sources(mystring
PRIVATE
    "main.cpp"
    "MyString.cpp"
    "Inheritance.cpp"
)

main.cpp

















































































































































#include <iostream>
#include <string>

#include "Inheritance.hpp"
#include "MyString.hpp"

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

void testInheritance();
void testStdString();
// void testMyString();
// void testMyStringDerived()

int main()
{
    testInheritance();
    testStdString();

    // testMyString();
    // testMyStringDerived();
    return 0;
}

// Test cases
/**
void testMyString()
{
    {
        MyString str1("String"), str2("Test String 2"), str3(str1);
        cout << "str1 is " << str1 << endl;
        cout << "str1 is: " << str1 << endl;
        cout << "str2 is: " << str2 << endl;
        cout << "str3 is: " << str3 << endl;
        cout << "The number of MyString instances is: " << MyString::GetCount() << endl;

        /////////////////////////////////////////////////////////

        cout << "Give one word " << endl;
        cin >> str1; // from stdin "this is a test line"
        cout << "str1 is: " << str1 << endl;

        /////////////////////////////////////////////////////////

        str2 = str1;
        cout << "str2 is: " << str2 << endl;

        /////////////////////////////////////////////////////////

        str3 += str1;
        cout << "str3 is: " << str3 << endl;

        /////////////////////////////////////////////////////////

        cout << "str3 is: ";
        for (unsigned i = 0; i < str3.length(); i++)
            cout << str3[i];
        cout << endl;

        for (unsigned i = 0; i < str3.length(); i++)
            str3[i] = 'a' + i;
        cout << "str3 is: " << str3 << endl;

        /////////////////////////////////////////////////////////

        cout << "str1 is: " << str1 << endl;
        cout << "str2 is: " << str2 << endl;
        cout << "str3 is: " << str3 << endl;
        cout << "Compare str1 == str2 is: " << (str1 == str2) << endl;
        cout << "Compare str1 == str3 is: " << (str1 == str3) << endl;
        cout << "Compare str1 != str2 is: " << (str1 != str2) << endl;
        cout << "Compare str1 != str3 is: " << (str1 != str3) << endl;
    }
}

void testMyStringDerived()
{
    MyString_Derived str1("NTOU");
    cout << (MyString)str1 << endl;
    cout << static_cast<MyString>(str1) << endl;
    cout << *(dynamic_cast<MyString*>(&str1)) << endl;
}
 */

void testInheritance()
{
    A a(1);
    cout << a << endl;

    B b(2, 3);
    cout << b << endl;

    b.setXY(4, 5);
    cout << b << endl;
}

void testStdString()
{
    {
        std::string str1("String"), str2("Test String 2"), str3(str1);
        cout << "str1 is " << str1 << endl;
        cout << "str1 is: " << str1 << endl;
        cout << "str2 is: " << str2 << endl;
        cout << "str3 is: " << str3 << endl;

        /////////////////////////////////////////////////////////

        cout << "Give one word " << endl;
        cin >> str1; // from stdin "this is a test line"
        cout << "str1 is: " << str1 << endl;

        /////////////////////////////////////////////////////////

        str2 = str1;
        cout << "str2 is: " << str2 << endl;

        /////////////////////////////////////////////////////////

        str3 += str1;
        cout << "str3 is: " << str3 << endl;

        /////////////////////////////////////////////////////////

        cout << "str3 is: ";
        for (unsigned i = 0; i < str3.length(); i++)
            cout << str3[i];
        cout << endl;

        for (unsigned i = 0; i < str3.length(); i++)
            str3[i] = 'a' + i;
        cout << "str3 is: " << str3 << endl;

        /////////////////////////////////////////////////////////

        cout << "str1 is: " << str1 << endl;
        cout << "str2 is: " << str2 << endl;
        cout << "str3 is: " << str3 << endl;
        cout << "Compare str1 == str2 is: " << (str1 == str2) << endl;
        cout << "Compare str1 == str3 is: " << (str1 == str3) << endl;
        cout << "Compare str1 != str2 is: " << (str1 != str2) << endl;
        cout << "Compare str1 != str3 is: " << (str1 != str3) << endl;
    }
}

MyString.hpp

















#ifndef MYSTRING_H
#define MYSTRING_H

class MyString
{
public:
    MyString();
    explicit MyString(const char* str);
    ~MyString();
};

class MyString_Derived;

void testStdString();
void testMyString();

#endif // MYSTRING_H

MyString.cpp
















#include "MyString.hpp"

MyString::MyString()
{
    // TODO
}

MyString::MyString(const char* str)
{
    // TODO
}

MyString::~MyString()
{
    // TODO
}

Inheritance.hpp




































#ifndef INHERITANCE_H
#define INHERITANCE_H

#include <iostream>

class A
{
    friend std::ostream& operator<<(std::ostream&, const A&);

private:
    int x;

protected:
    void setX(int i);

public:
    A(int i = 0);
    int getX() const;
};

class B : public A
{
    friend std::ostream& operator<<(std::ostream&, const B&);

private:
    int y;

public:
    B(int i = 0, int j = 0);
    void setXY(int i, int j);
};

std::ostream& operator<<(std::ostream& out, const A& a);
std::ostream& operator<<(std::ostream& out, const B& b);

#endif // INHERITANCE_H

Inheritance.cpp














































#include "Inheritance.hpp"

using std::ostream;

A::A(int i)
    : x(i)
{
}

void A::setX(int i)
{
    x = i;
}

int A::getX() const
{
    return x;
}

B::B(int i, int j)
    : A(i)
    , y(j)
{
}

void B::setXY(int i, int j)
{
    A::setX(i);
    y = j;
}

ostream& operator<<(ostream& out, const A& a)
{
    out << a.x;
    return out;
}

ostream& operator<<(ostream& out, const B& b)
{
    out << b.getX() << ' ' << b.y;

    out << (A)b << ' ' << b.y;
    out << static_cast<A>(b) << ' ' << b.y;
    out << *(dynamic_cast<const A*>(&b)) << ' ' << b.y;
    return out;
}

vector

編譯和執行

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

在 Visual Studio 選擇開啟本機資料夾或檔案 → 開啟 → 資料夾，並選擇vector/的資料夾。Visual Studio 會自動開始設定 CMake 專案，可能會花一點時間。等待輸出欄位的訊息跑完之後，在上方工具列的選取啟動項目選 vector.exe 就可以自動編譯執行了。

專案目錄結構

vector
├── CMakeLists.txt
└── main.cpp

原始碼

CMakeLists.txt










cmake_minimum_required(VERSION 3.12)

project("Vector Example")

add_executable(vector)

target_sources(vector
PRIVATE
    "main.cpp"
)

main.cpp

















































































































































































































/**
   std::vector 範例
   ~~~~~~~~~~~~~~~~

   std::vector 是 C++ 標準程式庫中的一個容器類別模板（container class template）
   是 C++ 標準程式庫中的眾多容器（container）之一。可視為會自動擴展容量的陣列，可
   以用來取代一般的動態陣列（new[]）。要使用必須包含 <vector> 標頭檔：

      #include <vector>


   常見操作的時間複雜度：

    * 隨機存取 - O(1)
    * 末端插入或刪除元素 - O(1)
    * 中間插入或刪除元素 - O(n)

   std::vector 記憶體的配置通常只會增加，不會因為元素被刪減而隨之減少。



   動態增長容器的比較
   ------------------

   std::vector
   ^^^^^^^^^^^

   跟動態陣列一樣在主記憶體（RAM）中擁有一段連續的儲存空間。其讀寫隨機位置的元素
   非常有效率，末端的刪除或增加元素效率也很快。但如果是刪除或增加容器中間元素時，
   vector 會需要借由複製來挪動儲存的元素，使效率不佳。另外，當儲存空間不夠時，需
   要重新申請一塊足夠大的記憶體並把每個元素拷貝過去，影響 vector 的效率。


   std::list
   ^^^^^^^^^

   雙向鏈結（doubly-linked list）。隨機存取元素很沒效率，但適合應用在需要在任意地
   方插入或刪除元素的情境。


   std::deque
   ^^^^^^^^^^

   雙向佇列（double-ended queue）。從前後插入及刪除元素都很快，但在中間插入或刪除
   元素效率不好。


   std::set
   ^^^^^^^^

   紅黑樹（red-black tree）。std::set 是一種關聯式容器，其中存放的物件是唯一的。
   std::set 會透過比較函式判斷兩個物件是否相等（例："hi" == "hi"）。如果是自定義
   的類別，就必須自己定義相關的比較函式。


   std::map
   ^^^^^^^^

   紅黑樹（red-black tree）。std::map 是一種關聯式容器，存放的是鍵-值對（
   Key-Value Pair）。每個鍵（Key）的物件在容器中會是唯一的，而且者會對應到一個值
   （Value）。std::map 透過比較函式判斷兩個鍵是否相等。如果是自定義的類別，就必
   須自己定義相關的比較函式。

   std::map 跟 std::set 的區別在於 std::set 只存放唯一的 "Key" 型別物件，而
   std::map 除了存放唯一的 "Key" 物件，還儲存與 "Key" 對應的 "Value" 物件。


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

   教學文章
   <<<<<<<<

    * C/C++ - Vector (STL) 用法與心得完全攻略：http://mropengate.blogspot.tw/2015/07/cc-vector-stl.html
    * C++ std::vector 用法與範例：https://shengyu7697.github.io/std-vector/
    * C++ std::list 用法與範例：https://shengyu7697.github.io/std-list/
    * C++ std::deque 用法與範例：https://shengyu7697.github.io/std-deque/
    * C++ std::set 用法與範例：https://shengyu7697.github.io/std-set/
    * C++ std::map 用法與範例：https://shengyu7697.github.io/std-map/

    cppreference
    <<<<<<<<<<<<

    * std::vector： https://en.cppreference.com/w/cpp/container/vector
    * std::list： https://en.cppreference.com/w/cpp/container/list
    * std::deque： https://en.cppreference.com/w/cpp/container/deque
    * std::set： https://en.cppreference.com/w/cpp/container/set
    * std::map： https://en.cppreference.com/w/cpp/container/map
*/

#include <cstdlib> // std::size_t
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::size_t;

// std::vector<int> 範例
int main()
{
    //////////////////////////////////////////////////////////////
    // vector 範例1
    // vector: 宣告時有明確長度的陣列

    cout << "vector 範例1" << endl;

    //要建立vector型態的物件，可以提供元素型態與長度資訊
    //例如: 建立int元素的vector，並擁有5個元素：
    std::vector<int> ivector_5(5);

    // size(): 取得 vector 目前持有的元素個數
    for (size_t i = 0; i < ivector_5.size(); i++) {
        ivector_5[i] = i + 1; // 可以使用陣列中存取元素的方式 [] 來存取vector的元素
    }

    cout << "ivector_5 is:\t";
    for (size_t i = 0; i < ivector_5.size(); i++) {
        cout << ivector_5[i] << " "; // 可以使用陣列中存取元素的方式 [] 來存取vector的元素
    }
    cout << endl;

    // iterator指標：指標用來指向vector的元素
    // begin()：取得指標 指向vector 第一個元素
    // end()：取得指標 指向最尾端元素的下一個位置（請注意：它不是最末元素）
    // operator++：iterator指標指向元素的下一個位置
    cout << "iterator:: ivector_5 is:\t";
    for (std::vector<int>::iterator it = ivector_5.begin(); it != ivector_5.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    // auto(C++11)可用於宣告變數時 自動推斷該變量的類型
    cout << "auto iterator:: ivector_5 is:\t";
    for (auto it = ivector_5.begin(); it != ivector_5.end(); it++)
        cout << *it << " ";
    cout << endl;

    //////////////////////////////////////////////////////////////
    // vector 範例2
    // vector:: 自動擴展容量的陣列
    cout << "\nvector 範例2" << endl;
    std::vector<int> ivector;

    // push_back(): 新增元素至 vector 的尾端，必要時會自動進行記憶體配置
    for (int i = 1; i <= 5; i++) {
        ivector.push_back(i);
    }

    cout << "ivector is:\t";
    for (auto it = ivector.begin(); it != ivector.end(); it++)
        cout << *it << " ";
    cout << endl;

    // capacity(): 取得 vector 目前可容納的最大元素個數
    cout << "ivector capacity is " << ivector.capacity() << endl;
    // resize(newSize): 改變目前持有的元素個數
    ivector.resize(3);
    cout << "resize 3 ivector capacity is " << ivector.capacity() << "\t ivector is : \t";
    for (auto it = ivector.begin(); it != ivector.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    // pop_back(): 刪除 vector 最尾端的元素
    for (int i = 1; i <= 2; i++) {
        ivector.pop_back();
    }

    cout << "刪除最尾端2個元素(pop_back) ivector is:\t";
    for (auto it = ivector.begin(); it != ivector.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    // clear(): 清空所有元素。
    ivector.clear();
    cout << "清空所有元素(clear) ivector is:\t";
    for (auto it = ivector.begin(); it != ivector.end(); it++)
        cout << *it << " ";
    cout << endl;

    //////////////////////////////////////////////////////////////
    // vector 範例3: 2維vector
    cout << "\nvector 範例3: 2維vector" << endl;
    std::vector<std::vector<int>> ivector2;

    for (int i = 1; i <= 5; i++) {
        std::vector<int> ivectorI;
        for (int j = 1; j <= i; j++) {
            ivectorI.push_back(j);
        }
        ivector2.push_back(ivectorI);
    }

    cout << "ivector2 size " << ivector2.size() << "\tcapacity " << ivector2.capacity() << endl;
    int i = 0;
    for (auto it2 = ivector2.begin(); it2 != ivector2.end(); it2++, i++) {
        cout << "ivector2[" << i << "] size " << it2->size() << "\tcapacity " << it2->capacity() << "\tivector2[" << i
             << "] is:\t";
        for (auto it = it2->begin(); it != it2->end(); it++) {
            cout << *it << " ";
        }
        cout << endl;
    }
    cout << endl;

    return 0;
}

參考資料

見 vector 範例程式。

實習課第十一次作業

tags: NTOU CSE C++ Programming

需求

範例程式

MyString

編譯和執行

專案目錄結構

原始碼

vector

編譯和執行

專案目錄結構

原始碼

參考資料

Read more

CMake 專案建置

實習課第十三次作業

NTOU CSE C++ 程式設計實習

正課第五次作業

tags: `NTOU CSE C++ Programming`