Programming

Deque 不同於 stack 與 queues， deques 兩個端點都支援擴展。 基於 doubly linked list，deques 有幾項額外的特徵： 支援隨機存取 插入元素時間 \(O(1)\) 函式 1. push_front() 2. push_back() 3. front() 4. back() 5. begin() 6. end() 7. insert() 8. erase() 9. pop_front() 10. pop_back() 11. empty() 12. clear() 13. random_access() 內部運作原理 上述所有函數和操作都在雙鏈表中以O（1）時間執行，但這些清單不能隨機訪問任何元素。C++中的deque也是如此。這個 O（1） 在 deque 中可以使用圓形陣列來實現。使用循環陣列，可以在O（1）時間內實現從陣列的正面和背面插入和刪除等操作以及元素的隨機訪問。但這帶來了一個問題。當 deque 增長到超出容量時，使用者將需要將數位大小加倍，並將所有數據複製到陣列中。此外，如果數據是某個使用者定義的對象，那麼加倍和複製數據的成本就會變得非常昂貴。 這是一個基本的解決方案。Deque使用一些棘手的實現，當它說O（1）來push_back（）和push_front（）時，它實際上是調用的複製構造函數數量的常數時間。因此，如果數據物件是具有多個成員的某個類物件，則最小化複製構造函數調用的數量將節省時間。此外，複製構造函數調用的次數是恆定的。現在讓我們看看如何實現這一點。 這可以通過使用指向一些固定大小的塊的指標數位來實現，這些塊包含deque數據。下面是一個說明性示例。 這些 Deque 數據被劃分為固定大小的塊。在這裡，我們考慮了將數據劃分為大小為5的固定塊。 塊的填充從指標的兩個 deque 陣列的中間開始，並使用push_front和push_back操作向前和向後擴展。中間塊通常是滿的，當它被填滿時，數據被移動到上部或下部塊。 在上部塊中，元素以相反的順序推送，因為在這種情況下，填充數據的第一個位置將是4，然後是3，2，1，0。但是在中間和下部塊中，數據按正向順序填充，如0，1，2，3，4等。 當上面的塊被填滿時，指標將創建一個新塊並開始指向一個新的數位塊。這為更多數據創造了空間。在這種情況下，也可以填充指標塊。這會導致一個問題。 這是加倍來救援的時候。在加倍時，指標陣列的大小加倍。這不會複製整個數據，而只會複製指標。這是許多人在討論恆定時間時提出的一般論點。時間在調用的複製構造函數數方面保持不變。 如果數據集非常大，則指標塊幾乎不會執行加倍，因為單個指標可以指向大量數據塊。因此，指標陣列被填充並加倍的可能性非常小。

C++ Custom Comparator sort(iter, iter, comp) Lambda function int main(){ auto comp = [](int a, int b){ return a < b; } vector<int> = {3,6,7,2,1,9,5,4,8}; sort(vec.begin(), vec.end(), comp); // 1,2,3,4,5,6,7,8,9 } Usual boolean function bool comp(const int& a, const int& b){ return a < b; } int main(){ vector<int> = {3,6,7,2,1,9,5,4,8}; sort(vec.begin(), vec.end(), comp); // 1,2,3,4,5,6,7,8,9 } Old solution using struct/class with () operator struct cmp { bool operator() (int a, int b) const { return a < b; } }; int main(){ vector<int> = {3,6,7,2,1,9,5,4,8}; sort(vec....

pair 函式庫 #include <utility> 宣告 pair<data_type1, data_type2> Pair_name; 初始化 pair<int, int> p1; // 宣告但不初始化 pair<int, char> p2(1, 'a'); // 不同資料型態的初始化 pair<int, int> p3(1, 10); // 同資料型態的初始化 pair<int, int> p4(p3); // 利用其它 pair 來初始化 pair<int, int> p5 = {1, 2} // 用 assign 的方式初始化 p2 = make_pair(1, 'a'); // 利用 make_pair 函式 成員 .first .second 函式 1. make_pair(v1, v2); 2. pair1.swap(pair2); 3. tie(a,b) 示例 #include <iostream> #include <utility> using namespace std; int main(){ // initialize pair<int,int> p1; pair<int,int> p2(2,4); pair<int,char> p3(3,'c'); pair<int,int> p4(p2); pair<int,int> p5 = {5,10}; // member cout << p2....

HDLBits HDLBits 是一系列小型電路設計的練習，用於使用 Verilog 硬體描述語言(HDL)進行數位硬體設計。 由教學的題型由淺入深，逐步建立起電路設計的技能。 每個問題都會要求讀者使用 Verilog 設計一個小電路。HDLBits 會對提交的程式碼作判讀。透過一組測試碼來進行向量模擬，並與解答比較，檢查正確性。 Catalog 1. Getting Started 2. Verilog Language 3. Circuits 4. Verification: Reading Simulations 5. Verification: Writing Testbenches 6. CS450 1 Getting Started \(\text{assign one}\) Build a circuit with no inputs and one output. The output should always drive 1 (or logic high). module top_module( output one); assign one = 1'b1; endmodule \(\text{assign zero}\) Build a circuit with no inputs and one output that outputs a constant 0....

1. Getting Started 2. Verilog Language 3. Circuits 4. Verification: Reading Simulations 5. Verification: Writing Testbenches 6. CS450 2 Verilog Language 2.1 Basics wire Create a module with one input and ont output that behaves like a wire module top_module( input in, output out); assign out = in; endmodule multi-in-out Create a module with 3 inputs and 4 outputs that behaves like wires that makes these connections: module top_module( input a,b,c, output w,x,y,z ); assign w = a; assign x = b; assign y = b; assign z = c; endmodule not gate Create a module that implements a NOT gate....