【序列容器 Sequence Containers】

Presentation on theme: "【序列容器 Sequence Containers】"— Presentation transcript:

1 【序列容器 Sequence Containers】
序列容器是一種各元素之間有順序關係的線性表，是一種線性結構的可序群集。序列容器中的每個元素均有固定的位置，除非用刪除或插入的操作改變這個位置。這個位置和元素本身無關，而和操作的時間和地點有關，序列容器不會根據元素的特點排序而是直接保存了元素操作時的邏輯順序。比如我們一次性對一個序列容器追加三個元素，這三個元素在容器中的相對位置和追加時的邏輯次序是一致的。 常見的序列容器有以下三種： vector：向量，從後面快速的插入與刪除，直接訪問任何元素。 list：雙向鏈結串列，從任何地方快速插入與刪除。 deque：雙向佇列，從前面或後面快速插入刪除、直接訪問任何元素。

2 【向量 vector】 每種容器都定義了一對命名為begin和end的函式，用於傳回迭代器。如果容器中有元素的話，由begin傳回的迭代器指向第一個元素。 　　vector<int>::iterator iter = v.begin(); 上述敘述把iter初始化為由名為v的vector進行begin操作傳回的值。假設vector不為空，初始化後，iter即指該元素v[0]。 由end操作傳回的迭代器指向vector的“末端元素的下一個”。通常稱為超出末端迭代器(off-the-end iterator)，表明它指向了一個不存在的元素。如果vector為空，begin傳回的迭代器與end傳回的迭代器相同。 由end操作傳回的迭代器並不指向vector中任何實際的元素，相反，它只是起一個崗哨（sentinel）的作用，表示我們已處理完vector中所有元素。

3 【向量 vector】 vector是一個線性順序結構。相當於陣列，但其大小可以不預先指定，並且自動擴展。它可以像陣列一樣被操作，由於它的特性我們完全可以將vector當作動態陣列。 在宣告一個vector後，它會自動在記憶體中分配一塊連續的記憶體空間進行資料儲存，初始的空間大小可以預先指定，也可以由vector內定，這個大小即capacity()函式的傳回值。當儲存的資料超過分配的空間時vector會重新分配一塊記憶體塊，但這樣的分配是很耗時的，在重新分配空間時它會做這樣的動作： 首先，vector會申請一塊更大的記憶體塊，然後，將原來的資料拷貝到新的記憶體塊中，其次，刪除原記憶體塊中的物件（呼叫物件的解構函式），最後，將原來的記憶體空間釋放掉。 如果vector保存的資料量很大時，這樣的操作一定會導致效能降低（這也是vector被設計成比較容易拷貝的類型的原因）。所以說vector不是在什麼情況下性能都好，只有在預先知道它大小的情況下vector的性能才是最佳的。

4 【vector 定義與宣告】 vector是一種動態陣列，是基本陣列的類別。相關之操作與成員函式定義在標題檔<vector>中：
#include <vector> vector的基本宣告語法：vector<資料型態> vector名稱; vector宣告方法如下： vector<int> v1; //宣告整數型態的向量v1 vector<int> v2(init_size,0); //宣告整數型態的向量v2，其元素初值為0。 vector<int> v3(v2); //宣告向量v3，並將v2的值指定給它。 vector<int> v4(first,last) //宣告向量v4，其元素初值由[first,last)指定

5 【vector 的成員函式一】 成員函式 功能說明 v.assign(beg,end) v.assign(n,elem)
將n個elem指定給v。 v.at(i) 傳回索引i所指的資料，如果i越界，拋出out_of_range。 v.back() 傳回最後一筆資料，不檢查這個資料是否存在。 v.begin() 傳回迭代器中的第一筆資料。 v.capacity() 傳回容器中資料個數。 v.clear() 移除容器中所有資料。 v.empty() 判斷容器是否為空。 v.end() 指向迭代器中的最後一筆資料位址。 v.erase(pos) 刪除pos位置的資料，傳回下一筆資料的位置。 v.erase(beg,end) 刪除[beg,end)區間的資料，傳回下一筆資料的位置。 v.front() 傳回第一筆資料。 v.insert(pos,elem) 在pos位置插入一個elem拷貝，傳回新資料位置。 v.insert(pos,n,elem) 在pos位置插入n個elem資料。無傳回值。 v.insert(pos,beg,end) 在pos位置插入在[beg,end)區間的資料。無傳回值。

6 【vector 的成員函式二】 成員函式 功能說明 v.max_size() 傳回容器中最大資料的數量。 v.pop_back()
刪除最後一筆資料。 v.push_back(elem) 在尾部加入一筆資料。 v.rbegin() 傳回vector的最後一個元素的逆向迭代器。 v.rend() 傳回vector的第一個元素的逆向迭代器。 v.resize(num) 重新指定大小。 v.reserve() 保留適當的容量。 v.size() 傳回容器中實際資料的個數。 v1.swap(v2) swap(v1,v2) 將v1和v2元素互換。

7 【 說明範例 】 // 04sc_01vector.cpp vector說明範例 #include <vector>
#include <iostream> #include <algorithm> #include <stdexcept> using namespace std; void print(int num) {cout<<num<<" ";} int main() { //1. 宣告及設定初值 vector<int> v; vector<int>::iterator iter; v.reserve(100);//設置vector大小 v.assign(10, 2);//將10個元素的值設定為2 cout << v.capacity() << endl; //返回vector所能容納的元素數量 cout << v.size() << endl; //返回vector實際含有的元素數量 //2. 添加 //注意：push_front()只適用於list和deque容器類型 for (int i = 0; i < 10; i++) v.push_back(i); for_each(v.begin(), v.end(), print);//需要#include <algorithm> cout << endl; cout << v.size() << endl; 

8 【 說明範例 】 //3. 插入及遍歷、逆遍歷 v.insert(v.begin() + 3, 99);
v.insert(v.end() - 3, 99); for_each(v.begin(), v.end(), print); cout << endl; for_each(v.rbegin(), v.rend(), print); //在逆序迭代器上做++運算   //一般遍歷寫法 for(iter = v.begin(); iter != v.end(); ++iter) cout<<*iter<<" "; cout << endl;  //4. 刪除 v.erase(v.begin() + 3); v.insert(v.begin() + 3, 99);//還原 v.erase(v.begin(), v.begin() + 3); //注意刪除了3個元素而不是4個 //注意：pop_front()只適用於list和deque容器類型 v.pop_back();

9 【 說明範例 】 //5. 查詢 cout << v.front() << endl;
cout << v.back() << endl; //危險的做法，但一般我們就像訪問陣列那樣操作就行 for (int i = 15; i < 25; i++) cout << "Element " << i << " is " << v[i] << endl; //安全的做法 int i; try { for (i = 15; i < 25; i++) cout << "Element " << i << " is " << v.at(i) << endl; } catch (out_of_range err)//#include <stdexcept> cout << "Out_of_range at " << i << endl; //6. 清空 v.clear(); cout << v.size() << endl;//0 for_each(v.begin(), v.end(), print); //已經clear，不會有任何結果。 cin.get(); return 0;

10 【vector解題範例 Uva10763 Foreign Exchange】
// 04sc_01vector_ex.cpp Uva10763 Foreign Exchange #include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std; int n,i,a,b,judge; vector<int> v[500005]; int main() { while (scanf("%d", &n) && n) judge = 0; memset(v, 0, sizeof(v)); for (i = 0; i < n; i ++) scanf("%d%d", &a, &b); if (find(v[b].begin(), v[b].end(), a) != v[b].end()) v[b].erase(find(v[b].begin(), v[b].end(), a)); judge --; } else v[a].push_back(b); judge ++; if (judge) printf("NO\n"); else printf("YES\n"); return 0;

11 To be Continue… 回目錄頁