顯示具有 程式 標籤的文章。 顯示所有文章
顯示具有 程式 標籤的文章。 顯示所有文章

2022年10月10日 星期一

MD5 筆記

MD5 Intro

MD5 訊息摘要演算法(英語:MD5 Message-Digest Algorithm),一種被廣泛使用的密碼雜湊函式,可以產生出一個128位元(16個字元(BYTES))的雜湊值(hash value),用於確保資訊傳輸完整一致。(節自wiki)

簡易 MD5 工具 : md5sum

基本上 Unix, Linux 的作業系統都有預設 md5sum
  • md5sum 用法
        # pipe
        $ echo "123" | md5sum
        ba1f2511fc30423bdbb183fe33f3dd0f  -
    
        # 讀檔
        $ md5sum .gitignore
        247bc32fd24d78844194917cb32d556a  .gitignore
    
        # check
        $ md5sum .gitignore > tmp.md5
        $ md5sum -c tmp.md5
        .gitignore: OK
    
        # pipe check
        $ echo "247bc32fd24d78844194917cb32d556a .gitignore" | md5sum -c
        .gitignore: OK
    

openssl/evp.h

The EVP digest routines are a high level interface to message digests (節自 Linux man page)。這裡註記一下 EVP 大概是代表 Envelope。雖然現在已經被改掉,但以前的 openssl/evp.h 的 #ifndef 是 HEADER_ENVELOPE_H。
  • evp 大概的流程
        #include <stdio.h>
        #include <string.h>
        #include <openssl/evp.h>
    
        int main(int argc, char *argv[])
        {
            EVP_MD_CTX *mdctx;
            const EVP_MD *md;
            char mess1[] = "Test Message\n";
            char mess2[] = "Hello World\n";
            unsigned char md_value[EVP_MAX_MD_SIZE];
            unsigned int md_len, i;
    
            if (argv[1] == NULL) {
                printf("Usage: mdtest digestname\n");
                exit(1);
            }
    
            OpenSSL_add_all_algorithms(); // 有可能有些 algo 沒有 load, ex. RSA-SHA1
            md = EVP_get_digestbyname(argv[1]);
            if (md == NULL) {
                printf("Unknown message digest %s\n", argv[1]);
                exit(1);
            }
    
            mdctx = EVP_MD_CTX_new();
            EVP_DigestInit_ex(mdctx, md, NULL); // _ex() 較有效率, 以前的 code 可能是 EVP_DigestInit()
            EVP_DigestUpdate(mdctx, mess1, strlen(mess1));
            EVP_DigestUpdate(mdctx, mess2, strlen(mess2));
            EVP_DigestFinal_ex(mdctx, md_value, &md_len);
            EVP_MD_CTX_free(mdctx);
    
            printf("Digest is: ");
            for (i = 0; i < md_len; i++)
                printf("%02x", md_value[i]);
            printf("\n");
    
            exit(0);
        }
    
參考資料 :
1.MD5 wiki
2.MD5SUM wiki
3.linux man page
4.stackoverflow

2022年10月9日 星期日

讀取 Linux file info (stat)

讀取 Linux 的檔案資訊

Linux 的檔案有很多資訊,即使只用到檔案大小也是很方便。

stat

  • struct stat
    stat 的資料結構
        #include <sys/stat.h>
    
        struct stat {
            dev_t     st_dev;         /* ID of device containing file */
            ino_t     st_ino;         /* Inode number */
            mode_t    st_mode;        /* File type and mode */
            nlink_t   st_nlink;       /* Number of hard links */
            uid_t     st_uid;         /* User ID of owner */
            gid_t     st_gid;         /* Group ID of owner */
            dev_t     st_rdev;        /* Device ID (if special file) */
            off_t     st_size;        /* Total size, in bytes */
            blksize_t st_blksize;     /* Block size for filesystem I/O */
            blkcnt_t  st_blocks;      /* Number of 512B blocks allocated */
    
            /* Since Linux 2.6, the kernel supports nanosecond
                precision for the following timestamp fields.
                For the details before Linux 2.6, see NOTES. */
    
            struct timespec st_atim;  /* Time of last access */
            struct timespec st_mtim;  /* Time of last modification */
            struct timespec st_ctim;  /* Time of last status change */
    
            #define st_atime st_atim.tv_sec      /* Backward compatibility */
            #define st_mtime st_mtim.tv_sec
            #define st_ctime st_ctim.tv_sec
        };
    
  • struct stat
    讀取檔案 (這裡讀 .gitignore)
        #include <stdio.h>    // for printf
        #include <time.h>     // for ctime
        #include <sys/stat.h>
    
        int main()
        {
            struct stat st;
            // 0 success, -1 failed
            // error code: errno
            if(stat(".gitignore", &st) == -1){
                return -1;
            }
            printf("I-node number:             %ld\n", (long) st.st_ino);
            printf("Mode:                      %lo (octal)\n", (unsigned long) st.st_mode);
            printf("Link count:                %ld\n", (long) st.st_nlink);
            printf("Ownership:                 UID=%ld   GID=%ld\n", (long) st.st_uid, (long) st.st_gid);
            printf("device containing file id: %ld\n", (long) st.st_dev);
            printf("device id:                 %ld\n", (long) st.st_rdev);
            printf("File size:                 %lld bytes\n", (long long) st.st_size);
            printf("Preferred I/O block size:  %ld bytes\n", (long) st.st_blksize);
            printf("Blocks allocated:          %lld\n", (long long) st.st_blocks);
            printf("Last status change:        %s", ctime(&st.st_ctime));
            printf("Last file access:          %s", ctime(&st.st_atime));
            printf("Last file modification:    %s", ctime(&st.st_mtime));
            return 0;
        }
    
        I-node number:             20057552
        Mode:                      100664 (octal)
        Link count:                1
        Ownership:                 UID=1000   GID=1000
        device containing file id: 66306
        device id:                 0
        File size:                 16 bytes
        Preferred I/O block size:  4096 bytes
        Blocks allocated:          8
        Last status change:        Tue Mar 29 14:03:01 2022
        Last file access:          Sun Oct  9 19:02:52 2022
        Last file modification:    Thu Jun 17 10:20:57 2021
    
參考資料 :
1.Linux manual page
2.程式人生

2022年9月25日 星期日

vscode 刪除空格 (Remove trailing spaces)

使用 vscode 自動刪除空格的原因

當你上 code 時,有 reviewer 看你的程式碼時,通常會用 meld 等軟體 review。當你的程式碼加了多餘的空格時,都會被這些程式碼 highlight,使得 reviewer 在查看你的程式碼時有一定的不便。

vscode 刪除空格

  • 手動刪除空格 (Remove trailing spaces manually)
    ctrl + alt + p,輸入 trail 你應該就可以看到相關快捷鍵。
  • 自動刪除空格 (Remove trailing spaces automatically)
    setting > 右上角的 open setting (JSON) > 加入以下這行。
        "files.trimTrailingWhitespace": true
    
參考資料 :
1.remove-trailing-spaces-automatically-or-with-a-shortcut

2022年1月3日 星期一

Topological Ordering 介紹

Directed Acyclic Graph (DAG) 介紹

不同於 Tree 的無方向、無環,DAG 則是有方向無環。DAG 特性是不斷地前進,有時分流、有時合流,日常常見的 DAG 為族譜、水流以及課程擋修規則

實作

  • Topological Ordering
    拿課程擋修規則為例,有必須先修的課程及後修的課程,將其完整排列出來視為 Topological Ordering。
        // 課程 1 須先修 : None
        // 課程 2 須先修 : 課程 1
        // 課程 3 須先修 : 課程 1, 課程 2
        // 課程 4 須先修 : None
        // 
        // Gragh:
        // 課程 1 -> 課程 2
        //        ↘   ↓
        // 課程 4    課程 3
        //
        // Topological Ordering:
        //  1) 1 2 3 4
        //  2) 4 1 2 3
        //  3) 1 4 2 3
        //  4) 1 2 4 3
        // 兩個都行,只要順序符合規則就好 (按這個例子,課程 4 的排序位置無關緊要)
    
  • Topological Sort ( Kahn's Algorithm  )
    排序時,首先要找到第一個點 (課程 1 或課程 4)。第一個點有一個特別之處,就是沒有人指向他。找出來該第一點後,把其指向的連接也跟著去掉。使下一次課程 2 變為第一個點。以此排序。
        // Gragh:
        //         課程 2
        //           ↓
        // 課程 4   課程 3
    
  • Code
    題目之範例解答
        bool canFinish (int numCourses, vector<vector<int>>& prerequisites) {
    
            // Kahn's Algorithm
            // http://web.ntnu.edu.tw/~algo/DirectedAcyclicGraph.html
    
            // adj 紀錄 node 連出去的所有 nodes
            // ref 紀錄 node 被連的次數
            vector<vector<int>> adj(numCourses, vector<int>());
            vector<int> ref(numCourses, 0);
    
            // init
            for (auto&v : prerequisites) {
                ++ref[v[0]];
                adj[v[1]].push_back(v[0]);
            }
    
            // Every loop 都可以找到一個 first node, 需要找出 numCourses 個
            for (int i = 0; i < numCourses; ++i) {
    
                // 一定有 node 的被連的次數為 0, 是為 first node
                // 若所有 node 被連次數都 > 0, 代表有 cycle
                int head = 0;
                while (head < numCourses && ref[head] != 0) ++head;
                if (head == numCourses) return false;
    
                // 找過的 first node 要刪除, 設為 -1
                // 把這次的 first node 所連出去 nodes 的 被連次數(ref) 減一
                ref[head] = -1;
                for (auto & n : adj[head]) --ref[n];
            }
    
            return true;
        }
    
參考資料 :
1.leetcode-problem-course-schedule
2.http://web.ntnu.edu.tw/~algo/DirectedAcyclicGraph.html

2021年10月1日 星期五

Distance 筆記

最近一直寫 Leetcode,部落格也就荒廢許久,想說突破 200 題來分享一下心得。

Distance question

Leetcode 上有很多問題是關於距離,這裡紀錄下一些有用的數學概念。
  • 平均值 (mean)
    平均值的歐幾里得距離最短 (4*4 + 4*4 < 1*1 + 7*7)
    但相乘值最大 (4*4 > 1*7)
  • 中位數 (median)
    中位數的絕對偏差值最低 (跟其物件的距離之總和最短)
  • 眾數 (mode)
    mode minimizes distance for indicator function (理解不能)
    這個我沒寫過類似的,寫過後我再更新。
參考資料 :
1.leetcode/discuss

2021年6月18日 星期五

Segment Tree 筆記

Segment-Tree 介紹

主要用來找區間最大值區間總和。由於我是為了這題所以以區間總和做介紹。下面陣列是應對區間總和,每個 node 紀錄的有起始點, 結束點及區間總和,EXAMPLE: [0,4] 代表 index 0 ~ 4 的總和,其總和為 10,[0,0] 代表 index 0~0 也就是 nums[0] 的本身值。至於樹為什麼長這樣跟 Build tree 有關。
    // nums:[-1, 4, 2, 0, 5]
    //
    // Segment Tree for the Above Array:
    //
    //         10                      [0,4]
    //        /  \
    //      5      5           [0,2]          [3,4]
    //     / \    / \
    //    3   2  0   5      [0,1]  [2,2]   [3,3]  [4,4]
    //   / \   
    // -1  4            [0,0]  [1,1]

Segment-Tree 實作

  • Build Tree
    這邊我用 c++ 概略作介紹。基本上是 top-down 的 build 法,時間複雜度為 O(n)。
        // Node 資料結構
        class segTreeNode {
        public:
            int begin, end, sum;
            segTreeNode * left = NULL;
            segTreeNode * right = NULL;
            segTreeNode(int s, int e, int m):begin(s), end(e), sum(m) {}
        };
    
        // Build
        segTreeNode* buildSegTree(int begin, int end, vector& nums) {
            // 若 begin = end,代表是 leaf。
            if (begin == end) {
                auto node = new segTreeNode(begin, begin, nums[begin]);
                return node;
            }  
            
            // 分割
            int mid = (begin + end) / 2;
            auto left  = buildSegTree(begin, mid, nums);
            auto right = buildSegTree(mid+1, end, nums);
            auto node = new segTreeNode(begin, end, left->sum + right->sum);
            node->left = left;
            node->right = right;
            return node;
        }
    
  • Update tree
    時間複雜度為 O(log n)。
        // Update
        void updateSegTree(segTreeNode* node, int index, int val) {
            
            // 若是該 index 的 leaf。則更新其 sum
            if (node->begin == index && node->end == index) {
                node->sum = val;
                return;
            }
            
            // 若是中間 node 則分割往下繼續找
            int mid = (node->begin + node->end) / 2;
            if (index > mid)
                updateSegTree(node->right, index, val);
            else
                updateSegTree(node->left, index, val);
                
            // 最後更新 node's sum
            node->sum = node->left->sum + node->right->sum;
        }
    
  • Sum
    時間複雜度為 O(log n + k)。
        // Sum
        int sumSegTree(segTreeNode* node, int left, int right) {
            // 若完美覆蓋區間,直接回傳。
            if (node->begin == left && node->end == right)
                return node->sum;
            
            int mid = (node->begin + node->end) / 2;
            
            // 要求區間完全在左邊
            if (right <= mid)
                return sumSegTree(node->left, left, right);
            // 要求區間完全在右邊
            else if (left > mid)
                return sumSegTree(node->right, left, right);
            // 兩邊都有
            else
                return sumSegTree(node->left, left, mid) + 
                       sumSegTree(node->right, mid+1, right);
        }
    
參考資料 :
1.leetcode/hg3994 answer
2.youtube 中文講解

2021年6月11日 星期五

讀書心得 - C++ Primer (5th Edition) - Chapter 5 (3) - 常用詞彙

常用詞彙

  • block
    Sequence of zero or more statements enclosed in curly braces. A block is a statement, so it can appear anywhere a statement is expected.
  • case label
    Constant expression that follows the keyword case inC++ Primer, Fifth Edition a switch statement. No two case labels in the same switch statement may have the same value.
  • catch clause
    The catch keyword, an exception declaration in parentheses, and a block of statements. The code inside a catch clause does whatever is necessary to handle an exception of the type defined in its exception declaration.
  • compound statement
    Synonym for block.
  • null statement
    An empty statement. Indicated by a single semicolon.
  • raise
    Often used as a synonym for throw. C++ programmers speak of “throwing” or “raising” an exception interchangeably.

讀書心得 - C++ Primer (5th Edition) - Chapter 5 (2) - Exception

Exceptions

Exceptions 是程式在 run-time 遇到的異常,比如與資料庫的連結斷開或遇到其他程式異想不到的 input。Exception handling 基本上就是當程式無法解決問題或者無法繼續執行時發出警告,或者更進一步根據情況處理 exception。
Exception handling 由 detecting, handling parts of a program 所組成
  • throw expressions
    當 detecting part 表示遭遇無法處理的情況
  • try blocks
    handling part 用來處理 exception。程式碼一開始會有一個 try block 隨後跟著一個或以上的 catch clauses。
  • exception classes
    用來傳遞 information about what happened between a throw and an associated catch.

A throw Expression

通常會在 detecting part 發生 exception 時 throw Expression,這麼做原因是有時你不能保證你的程式一定是跟 User 互動的那一個,throw Expression 效果就比你回傳一個錯誤值好用得多。
    // Normal version
    int throwTest(int num1, int num2) {
        if (num1 == num2) {
            cout << "Same." << endl;
            return 0;
        } else {
            cerr << "Not the same." << endl;
            return -1;
        }
    }

    // throw Expression
    void throwTest(int num1, int num2) {
        if (num1 != num2)
            throw runtime_error("Not the same.");
        cout << "Same." << endl;
    }

The try Block

基於 C 風格的錯誤處理,在回傳值代表發生錯誤時予以處理。相比之下 throw 就相對靈活,但也會有終止程式的代價。try catch 的 block 就適合在此情況使用。讓程式有 exception handler。
    try {
        program-statements
    } catch (exception-declaration) {
        handler-statements
    } catch (exception-declaration) {
        handler-statements
    } // . . .

Standard Exceptions

正如上面的 try block 示億程式碼所示,程式必須先宣告 exception 的種類才能近一步去做 handle,這裡紀錄 C++ standard library \ 裡的 exception table。 
    exception         // The most general kind of problem.

    // Runtime errors
    runtime_error     // Problem that can be detected at the run-time.
    range_error       // Result generated outside the range of value that are meaningful.
    overflow_error    // Computation that overflow.
    underflow_error   // Computation that underflow.

    // Logic errors
    logic_error       // Error in the logic of the program.
    domain_error      // Argument for which no result exists.
    invalid_argument  // Inappropriate argument.
    length_error      // Attempt to create an object larger than the maximum size for that type.
    out_of_range      // Use a value outside the valid range.

讀書心得 - C++ Primer (5th Edition) - Chapter 5 (1) - Statement

Statement

  • Simple Statements
    expression 加上 ; 作為結尾視為 statement。
        a + 5  // expression
        a + 5; // statement
        ;      // null statement
    
  • Compound Statements (Blocks)
    在 { } 中間一連串的 statements 或 declarations (也允許是空的),且不用 ; 作為中止符。
        while (val <= 10) {
            sum += val;  // assigns sum + val to sum
            ++val;       // add 1 to val
        }
    
  • Statement Scope
    我們可以在 if else for 等等的 statements 裡宣告參數,但該參數也只有在 statements 裡能存取。
        while (int i = get_num()) // i is created and initialized on each iteration
            cout << i << endl;
        i = 0;  // error: i is not accessible outside the loop
    
  • Conditional Statements
    有 if statement, if else statement 和 switch statement。以下面的 switch code 為示範,"switch (ch)" 的 ch 為 expression,"case 'a':", "case 'e':" ... 為 case label,當 expression match case label,execution 就會從此開始直到 switch 的中止符或 break,所以是有可能橫跨 case labels。合法 case label 為 integral constant expressions,也就是 integral type 的 constant expression
        int vowelCnt = 0
        // any occurrence of a, e, i, o, or u increments vowelCnt
        while (cin >> ch) {
            switch (ch) {
                case 'a':
                case 'e':
                case 'i':
                case 'o':
                case 'u':
                    ++vowelCnt;
                    break;
            }
        }
    
  • Why can't variables be declared in a switch statement?
    首先這是 stackoverflow 裡的一個問題,問題題目應該改成 Why can't variables be initialized in a switch statement?,因為如果只有 declared 是合法的,頂多有 warning。基本上 case 就是 label 的一種,一種常見於有 goto 的程式碼。若你做 variable definition 在 switch statement,等於在這 switch statement scope 裡會有機會因為做了 goto label 的關係而忽略掉該 definition,進而導致程式碼出錯。若要在 switch statement 做 variable definition,你就必須很明確地告訴 compiler 即使有 goto label 忽略該 variable definition 也沒差,因為我只會在那 case 裡使用,也就是加 {} 更近一步明確地縮小 variable definition 的 scope 而非整個 switch statement scope。(Declaration跟Definition間的差異)
        // Ok, 程式碼寫得漂亮,compiler 發現沒有任何 label 會忽略掉 init 的 definition
        switch (num) {
            case 1:
                int init = 0;
                cout << declare << endl;
        }
    
        // Error, case 2 這個 label 會忽略 init 的 definition
        // main.cpp:17:10: error: jump to case label
        // 17 |     case 2:
        //    |          ^
        switch (num) {
            case 1:
                int init = 0;
                cout << init << endl;
            case 2:
                cout << 9999 << endl;
        }
    
        // 加 {},縮小該 variable definition 的 scope
        switch (num) {
            case 1:
                {
                    int init = 0;
                    cout << init << endl;
                }
            case 2:
                cout << 9999 << endl;
        }
    
        // 只是 declaration 不會有事
        // 甚至因為是同 scope 所以 case 2 可以呼叫到
        // declare = 5; 若拿掉會出錯
        // 因為 compiler 發現 declare 從沒被賦予值過
        int num = 2;
        switch (num) {
            case 1:
                int declare;
                declare = 5;
            case 2:
                cout << declare << endl;
        }
        // Output: 21911
    
  • Iterative Statements
    有 while statement, for statement 跟 do while Statement。C++ 的 for statement 除了傳統的還有 range for statement。其中 expression 必須要是 braced initializer list, array, vector 或 string 其中一種。
        for (declaration : expression)
            statement
    
  • Jump Statements
    有 break statement, continue statement 和 goto Statement。
參考資料 :
1.why-cant-variables-be-declared-in-a-switch-statement

2021年5月20日 星期四

讀書心得 - C++ Primer (5th Edition) - Chapter 4 (3) - 常用詞彙

常用詞彙

  • arithmetic conversion
    A conversion from one arithmetic type to another. In the context of the binary arithmetic operators, arithmetic conversions usually attempt to preserve precision by converting a smaller type to a larger type (e.g., integral types are converted to floating point).
  • associativity
    Determines how operators with the same precedence are grouped. Operators can be either right associative (operators are grouped from right to left) or left associative (operators are grouped from left to right).
  • cast
    An explicit conversion.
  • compound expression
    An expression involving more than one operator.
  • expression
    The lowest level of computation in a C++ program. Expressions generally apply an operator to one or more operands. Each expression yields a result. Expressions can be used as operands, so we can write compound expressions requiring the evaluation of multiple operators.

讀書心得 - C++ Primer (5th Edition) - Chapter 4 (2) - Type Conversions

Type Conversions

  • Implicit Conversions
    型別轉換,大部分轉換都是看是否能轉換成 int,例如 char, bool, 和 short。
        bool      flag;   char           cval;
        short     sval;   unsigned short usval;
        int       ival;   unsigned int   uival;
        long      lval;   unsigned long  ulval;
        float     fval;   double         dval;
        3.14159L + 'a'; //  'a' promoted to int, then that int converted to long double
        dval + ival;    //  ival converted to double
        dval + fval;    //  fval converted to double
        ival = dval;    //  dval converted (by truncation) to int
        flag = dval;    //  if dval is 0, then flag is false, otherwise true
        cval + fval;    //  cval promoted to int, then that int converted to float
        sval + cval;    //  sval and cval promoted to int
        cval + lval;    //  cval converted to long
        ival + ulval;   //  ival converted to unsigned long
        usval + ival;   //  promotion depends on the size of unsigned short and int
        uival + lval;   //  conversion depends on the size of unsigned int and long
    
  • Explicit Conversions
    用於我們想明確地強制將 object 轉換為其他類型。cast-name\(expression)。(const相關文章1, const相關文章2)
        // static_cast 最常用的 cast-name
        // cast used to force floating-point division
        double slope = static_cast<double>(j) / i;
    
        // const_cast 用來改變 low-level const (point to const)
        const char *pc;
        char *p = const_cast<char*>(pc); // ok: but writing through p is undefinedc
    
        // reinterpret_cast 對其 operand 進行 low-level bit 的重新解釋
        // 要很理解其型別的 bit 組成才會使用
        int *ip;
        char *pc = reinterpret_cast<char*>(ip);
    
cast 基本上就是擾亂型別,建議能不使用就不使用。

讀書心得 - C++ Primer (5th Edition) - Chapter 4 (1) - Expression & Operator

Expression

運算式 (expression) 由運算元 (operand) 與運算子 (operator) 所組成,最終計算產生一個結果 (result)。
  • Order of Evaluation
    想要計算 expression 的話,就必須知道運算子運作及其先後順序。這裡的 * 號就不是 pointer 而是相乘,然後再來是基本的先乘除後加減。
        cout << 5 + 10 * 20 / 2 << endl;        // 105
        cout << 6 + 3 * 4 / 2 + 2 << endl;      // 14
        cout << (6 + 3) *  (4 / 2 + 2) << endl; // 36
        cout << ((6 + 3) *  4) / 2 + 2 << endl; // 20
        cout << 6 + 3 * 4  / (2 + 2) << endl;   // 9
    
  • Lvalues and Rvalues
    有寫過一篇 Lvalues and Rvalues 也可以參考。這裡紀錄此書寫大概的定義,當我們將一個 object 視為 rvalue 使用,使用的是此 object 的值 (contents)。當我們將一個 object 視為 lvalue 使用,使用的是此 object 的「存在」(記憶體位置)。還有一點也很重要,lvalue 可以代替 rvalue,但反之 rvalue 卻不能代替 lvalue。
        int a = 1;     // a = lvalue, 1 = rvalue
        int b = a + 1; // a = lvalue, a = rvalue (lvalue 代替 rvalue)
        int 1 = a;     // Error, 1 != lvalue (rvalue 不能代替 lvalue)
    

Operators

  • Logical and Relational Operators
    Logical Operators 和 Relational Operators 回傳 bool。Logical Operators AND 跟 OR 永遠都會先計算左側再來計算右側。這裡想特別紀錄的是 && 跟 ||,&& 代表只有左側計算出來是 True 才會計算右側,|| 則是只有左側計算出來是 False 才會計算右側。這可以寫出一些流程控制而不是使用典型的 if else。Relational Operators 則是 >, <, >=, <=, ! 這些。
        // 以下這兩個 val 都會被轉換成 bool
        if (val)  { /*  ...  */ } // true if val is any nonzero value
        if (!val) { /*  ...  */ } // true if val is zero
    
        // 有了上面兩個例子,我們看似可以將其改寫成以下寫法
        if (val == true) { /*  ...  */ }
    
        // 這個會產生問題,只要 val 的型別不是 bool
        // 假設 val 是 int,true 會被轉換成 int 也就是 1 跟原先的任何 nonzero value 相去甚遠
        if (val == 1) { /*  ...  */ } // true if val is 1
    
  • Assignment Operators
    最常見就是等號 (=)。Assignment 是 Right Associative,以下有程式碼示範。另外 Assignment Operators 執行順序較低通常會用括弧輔助。
        int ival, jval;
        ival = jval = 0; // ok: each assigned 0
        // 對於右邊的 assignment,jval = 0
        // 對於左邊的 assignment,ival = (jval = 0)
        // jval assigned 0 後,回傳 jval (ival = jval),ival = 0
    
        // 原先邏輯
        int i = get_value();
        while (i != 42) {
            // do something ...
            i = get_value();
        }
        // 改寫,用括弧輔助
        int i;
        while ((i = get_value()) != 42) {
            // do something ...
        }
    
  • Increment and Decrement Operators
    ++ -- 用來做 Increment 和 Decrement,兩個都有 prefix 跟 postfix 的寫法,效果如下程式碼示範。要注意的是要盡量用 prefix 來做運算,因為你通常不會需要做增減前的 value,而 postfix 會 copy 一份增減前的 value 來做回傳。 
        int i = 0, j;
        j = ++i; // j = 1, i = 1: prefix yields the incremented value
        j = i++; // j = 1, i = 2: postfix yields the unincremented value
    
        // 需要 postfix 的場合
        auto pbeg = v.begin();
        // print elements up to the first negative value
        while (pbeg != v.end() && *beg >= 0)
            cout << *pbeg++ << endl; // print the current value and advance pbeg
    
    Operand 運算順序不是固定的,通常不會造成問題,但如果兩邊有用到同一 variable 且用了 Increment 或 Decrement Operators 問題就會浮現。
        // 原先邏輯是把 s 裡的 char 都改成大寫
        // the behavior of the following loop is undefined!
        auto it = s.begin()
        while (it != s.end() && !isspace(*it))
            *it = toupper(*it++);   // error: this assignment is undefined
    
        // 會有兩種結果
        // 第一種輸出 ABCDEFG
        *beg = toupper(*beg);        // 先執行左邊的 Operand,Output: ABCDEFG
        *(beg + 1) = toupper(*beg);  // 先執行左邊的 Operand,Output: aAAAAAA
    
  • Shift Operators (aka IO Operators) Are Left Associative
        cout << "hi" << " there" << endl;
        ( (cout << "hi") << " there" ) << endl;
    
        cout << 42 + 10;   // ok: + has higher precedence, so the sum is printed
        cout << (10 < 42); // ok: parentheses force intended grouping; prints 1
        cout << 10 < 42;   // error: attempt to compare cout to 42!
    

2021年5月13日 星期四

C++ Primer (5th Edition)

讀書心得 - C++ Primer (5th Edition) - Chapter 3 (4) - 常用詞彙

常用詞彙

  • buffer overflow
    Serious programming bug that results when we use an index that is out-of-range for a container, such as a string, vector, or an array.
  • container
    A type whose objects hold a collection of objects of a given type. vector is a container type.
  • index
    Value used in the subscript operator to denote the element to retrieve from a string, vector, or array.
  • iterator
    A type used to access and navigate among the elements of a container.
  • off-the-end iterator
    The iterator returned by end that refers to a nonexistent element one past the end of a container.

讀書心得 - C++ Primer (5th Edition) - Chapter 3 (3) - Array

Array

Array 為資料結構且跟 Vector 很像,都是裝同一 Type object 的 container。但 Array 為固定大小,所以不能增加 element,但也因為如此有時能提供較好的 run-time performance。
  • Initialize
    在 C++ 裡 Array 的 Size 要為 constant expression,也就是 expression 能在 compile time 就算出來。但因為 C 支援在 Array Size 塞變數,所以 G++ 將此寫法視為一個 extension,只要你不在 compile 時強調要遵循 C++ 的 Rule (-pedantic)。
        unsigned cnt = 42;            // not a constant expression
        constexpr unsigned sz = 42;   // constant expression
    
        int arr[10];                  // array of ten ints
        int *parr[sz];                // array of 42 pointers to int
        string bad[cnt];              // error: cnt is not a constant expression
        string strs[get_size()];      // ok if get_size is constexpr, error otherwise
        int a1[3] = {0, 1, 2};        // [0, 1, 2]
        int a2[]  = {0, 1, 2};        // [0, 1, 2]
        int a3[5] = {0, 1, 2};        // [0, 1, 2, 0, 0]
        string a4[3] = {"hi", "bye"}; // ["hi", "bye", ""]
    
    賦予初始值可用 string 來直接 Initialize。
        char a1[] = {'C', '+', '+'};       // list initialization, no null
        char a2[] = {'C', '+', '+', '\0'}; // list initialization, explicit null
        char a3[] = "C++";                 // null terminator added automatically
        const char a4[6] = "Daniel";       // error: no space for the null!
    
    加入 pointer 和 reference 的宣告
        int *ptrs[10];            // ptrs is an array of ten pointers to int
        int &refs[10] = /* ? */;  // error: no arrays of references
        int (*Parray)[10] = &arr; // Parray points to an array of ten ints
        int (&arrRef)[10] = arr;  // arrRef refers to an array of ten ints
        int *(&arry)[10] = ptrs;  // arry is a reference to an array of ten pointers
    
  • Iterate
    這裡紀錄像 Iterator 的方法。arr[10] 是一個不存在的 index 所以只能取 address,所以當 pointer 指到它時就代表此 Array 已結束,類似 begin 跟 end 的方法。但這是較危險的寫法
        int arr[] = {0,1,2,3,4,5,6,7,8,9};
        int *e = &arr[10];
        for (int *b = arr; b != e; ++b)
            cout << *b << endl; // print the elements in arr
    
    有 function 可以直接用。
        int arr[] = {0,1,2,3,4,5,6,7,8,9}; 
        int *pbeg = begin(arr); // pbeg points to the first
        int *pend = end(arr);   // pend points just past the last element in arr
        for (int* p = pbeg; p != pend; ++p)
            cout << (*p) << endl;
    
  • Using an Array to Initialize a vector
        int int_arr[] = {0, 1, 2, 3, 4, 5};
        // ivec has six elements; each is a copy of the corresponding element in int_arr
        vector<int> ivec(begin(int_arr), end(int_arr));
        // copies three elements: int_arr[1], int_arr[2], int_arr[3]
        vector<int> subVec(int_arr + 1, int_arr + 4);
    
  • Initializing the Elements of a Multidimensional Array
        int ia[3][4] = {    // three elements; each element is an array of size 4
            {0, 1, 2, 3},   // initializers for the row indexed by 0
            {4, 5, 6, 7},   // initializers for the row indexed by 1
            {8, 9, 10, 11}  // initializers for the row indexed by 2
        };
        // equivalent initialization without the optional nested braces for each row
        int ia[3][4] = {0,1,2,3,4,5,6,7,8,9,10,11};
        // explicitly initialize only element 0 in each row
        int ia[3][4] = {{ 0 }, { 4 }, { 8 }};
        // explicitly initialize row 0; the remaining elements are value initialized
        int ix[3][4] = {0, 3, 6, 9};
    
參考資料 :
1.Initializing array with variable vs real number

2021年5月11日 星期二

讀書心得 - C++ Primer (5th Edition) - Chapter 3 (2) - Vector

Library - vector

  • Intro
    vector 是物件的集合,集合裡的物件都是同一 type,且每個物件都有 index 可以用找到該物件。vector 也是 container 和 class template 的一種。
        vector<int> ivec;             // ivec holds objects of type int
        vector<Sales_item> Sales_vec; // holds Sales_items
        vector<vector<string>> file;  // vector whose elements are vectors
    
  • Initialize
        vector<int> ivec;               // initially empty
        // give ivec some values
        vector<int> ivec2(ivec);        // copy elements of ivec into ivec2   
        vector<int> ivec3 = ivec;       // copy elements of ivec into ivec3   
        vector<string> svec(ivec2);     // error: svec holds strings, not ints
        vector<int> ivec(10, -1);       // ten int elements, each initialized to -1
        vector<string> svec(10, "hi!"); // ten strings; each element is "hi!"
    
  • Add
    push_back 會在 run time 的時候執行,會加 object 到 container 的最後端
        vector<int> v2;        // empty vector
        for (int i = 0; i != 100; ++i)
            v2.push_back(i);    // append sequential integers to v2
        // at end of loop v2 has 100 elements, values 0 . . . 99
    
  • Operations
        v.empty()       // Return true if v is empty; otherwise return false.
        v.size()        // Return the number of elements in v.
        v.push_back(t)  // And an element with value t to end of v.
        v[n]            // Return a reference to the element at position n in v
        v1 = v2         // Replaces the elements in v1 with a copy of the elements in v2
        v1 = {a,b,c...} // Replaces the elements in v1 with a copy of the elements in the comma-separated list
        v1 == v2        // v1 and v2 are equal if they have same number of elements and each
        v1 != v2        // element in v1 is equal to the corresponding element in v2
    

Library - iterators

  • Intro
    雖然使用者可以用 [n] (subscripts) 來取得 string 或 vector 的 element。但有一個更通用的用法也就是 iterator。
  • Using
    不像 pointer 不是用 address-of operator 來獲取 iterator,有些型別本身就有成員回傳 iterator。典型就是行別有成員 begin 和 end。begin 指向第一個 element,而 end 指向的是 container 的"結束",也就是說當 container 的 element 數量為 0 時,begin == end。
        // the compiler determines the type of b and e;
        // b denotes the first element and e denotes one past the last element in v
        auto b = v.begin(), e = v.end(); // b and e have the same type
    
  • Operation
        *iter       // Return a reference to the element denoted by the iterator iter
        iter->mem   // Dereferences iter and fetches the member named mem from the
                    // underlying element. Equivalent to the (*iter).mem
        ++iter      // Refers to the next element in the container
        --iter      // Refers to the previous element in the container
    
    利用 begin() != end() 來確認不是空字串
        string s("some string");
        if (s.begin() != s.end()) { // make sure s is not empty
            auto it = s.begin();    // it denotes the first character in s
            *it = toupper(*it);     // make that character uppercase
        }
    
  • Iterates through the elements in container
    這裡用 string 示範,比較要注意的是常用的迴圈終止條件用的是 != end(),而非用往常的 < 。並不是所有 Iterator 都可以支援 < operator,剛好 vector 還有 string 支援而已。
        // process characters in s until we run out of characters or we hit a whitespace
        for (auto it = s.begin(); it != s.end() && !isspace(*it); ++it)
            *it = toupper(*it); // capitalize the current character
    
  • Type
    如果想要精準宣告 Iterator 的 Type 的話。
        vector<int>::iterator it;        // it can read and write vector<int> elements
        string::iterator it2;            // it2 can read and write characters in a string
        vector<int>::const_iterator it3; // it3 can read but not write elements
        string::const_iterator it4;      // it4 can read but not write characters
    
  • Operations Supported by vector and string Iterators
    上面有提到 vector 跟 string 的 iterator 有支援較多的 operator。
        // The iterators must denote element in, or one past the end of, the same container
    
        iter + n      // Adding (subtracting) an integral value n to (from) an iterator yields an
        iter - n      // iterator that many elements forward (backward) within the container.
    
        iter1 += n    // Compound-assignment for iterator addition. 
        iter1 -= n    // Compound-assignment for iterator subtraction.
    
        iter1 - iter2 // Subtracting two iterators yields the number that when added to the
                      // right-hand iterator yields the left-hand iterator.
    
        >, <=, <, <=  // Relational operators on iterators. One iterator is less than another if it
                      // refers to an element that appears in the container before the referred to 
                      // by the other iterator.
    
    取中間的 iterator
        // compute an iterator to the element closest to the midpoint of vi
        auto mid = vi.begin() + vi.size() / 2;
    
    binary search
        // text must be sorted
        // beg and end will denote the range we're searching
        auto beg = text.begin(), end = text.end();
        auto mid = text.begin() + (end - beg)/2; // original midpoint
        // while there are still elements to look at and we haven't yet found sought
        while (mid != end && *mid != sought) {
            if (sought < *mid)     // is the element we want in the first half?
                end = mid;         // if so, adjust the range to ignore the second half
            else                   // the element we want is in the second half
                beg = mid + 1;     // start looking with the element just after mid
            mid = beg + (end - beg)/2;  // new midpoint
        }
    

2021年5月6日 星期四

讀書心得 - C++ Primer (5th Edition) - Chapter 3 (1) - Namespace

Namespace - using declaration

為了讀取 stdin,程式碼會是 std::cin。 :: 的左邊是告訴 compiler 去哪個 scope 找右邊的 operand。這有時會造成程式碼過於冗長,所以有了 using declaration 讓你更簡單的呼叫 namespace 底下的成員。
    #include <iostream>
    using std::cin;
    int main()
    {
        int i;
        cin >> i;       // ok: cin is a synonym for std::cin
        cout << i;      // error: no using declaration; we must use the full name
        std::cout << i; // ok: explicitly use cout from namepsace std
        return 0;
    }
using declaration 通常不會出現在 header 裡,因為 header 會被複製到各個程式中,會導致所有 include 該 header 的程式用相同的 using declaration 容易造成命名衝突。

Library - string

  • Initialize
        #include <string>
        using std::string;
        string s1;            // default initialization; s1 is the empty string
        string s2 = s1;       // s2 is a copy of  s1
        string s3 = "hiya";   // s3 is a copy of the string literal
        string s4(10, 'c');   // s4 is cccccccccc
    
  • std::cin interaction
    cin 會因為 space 而被分開,以下程式碼若輸入 "Hello World!",則 s1 = "Hello", s2 = "World!"
        string s1, s2;
        cin >> s1 >> s2; // read first input into s1, second into s2
        cout << s1 << s2 << endl; // write both strings
    
    可以用 getline 來讀完整的 "Hello World!"
        string line;
        // read input a line at a time until end-of-file
        while (getline(cin, line))
            cout << line << endl;
        return 0;
    
  • Comparing & Adding Two string
    string 可以使用 ==, != 做比較,也可以用 + 來做字串串接
        string s1 = "hello, ", s2 = "world\n";
        string s3 = s1 + s2;   // s3 is hello, world\n
        s1 += s2;   // equivalent to s1 = s1 + s2
    
  • Iterates through the chars in a string
    可以用 for(auto c : str),也可以用 for(auto &c : str)。&c 是 reference 所以可以改變 str 裡的 char。 
        string str("some string");
        // print the characters in str one character to a line
        for (auto c : str)      // for every char in str
            cout << c << endl;  // print the current character followed by a newline
    

2021年4月27日 星期二

Git - 刪除 submodule

Git - delete submodule

因為上網 Google 這問題你會發現這個Stackoverflow這個Github的答案。很久以前查的時候 stackoverflow 置頂的答案是以前最多 upvote 的答案,也就是 githb 的答案。但 git 在版本更新後那個 7 步刪除 submodule 的已經過時了。雖然還是可以用但現在三步就可完成。
    # 用 git submodule deinit 清除 git config 的紀錄
    git submodule deinit -f path/to/submodule

    # 手動刪除 git 不再 track 的 submodule file
    rm -rf .git/modules/path/to/submodule

    # 用 git 清除 .gitmodules 的紀錄
    git rm -f path/to/submodule
參考資料 :
1.stackoverflow

Popular Posts