Re: [問題] vector 問題 (2d,比較運算子)

[bleed1979 (十三)]

L大是對的，請翻開9.3.4，有詳述。

基本上是這樣：

容器元素數量相等，元素相等 --> 等於

            不相等 ----------> 不等於


不等於的情況：(分成容量小和容量大)

容量小者的所有元素都存在於容量大者 --> 容量小 < 容量大

兩者都不是對方的子序列  --> 取決於第一個不相等的元素看誰大


用法：(我也沒有很會用，只舉簡單的例子)

例子：2D的整數型態陣列但是每一個維度長度都不一樣。

題目：某塊土地上有10000個城市，兩個城市之間有路可以通行，

路徑的方向是單向的有權重，共有10000條路徑的資料，

請求出所有城市彼此間的最短路徑。

解：並不是要解題，而是這題資料結構的配置上要怎麼下。

當你讀入一堆像是(起點 終點 權重)即(A B W)這類的資料時，

總是要記錄起來，但是在有記憶體限制的情況下，

int W[10001][10001];

應該就爆表了。

但如果使用2D的vector，應該就可以在容許範圍內。

vector<int> vec1D;

vector< vector<int> > vec2D(10001, vec1D);

這時，

vec2D[0]
vec2D[1]
...
...
vec2D[10000]

這每一個都是vec1D，因為我放了10001個1D的進入vec2D，

要知道有幾個城市連通城市1，就存取vec2D[1].size()。

當你vec2D[1].push_back(某整數);時，

就放到了vec2D[1][0]的位置，vec2D[1].size()等於1。


如果你想用resize()來達到int W[10001][10001]的效果。

for(int i = 0; i < 10001; ++i) {
  wec2D[i].resize(10001);
}

此時每個元素都是預設初值(因為沒設定值是多少)。



如果原本就已經確定是要int W[10001][10001]了。

vector<int> vec1D(10001);

vector< vector<int> > vec2D(10001, vec1D);

就達到目的了。


當然解這題就是不想開那麼大的空間，

你可能需要自定義struct，把城市編號和權重一併放入。

struct City {
  City() {}
  City(int i1, int i2) : no(i1), w(i2) {}

  int no;    // city to
  int w;     // weight of route
};

那vector就可以這樣用：

vector<City> vec1D;

vector< vector<City> > vec2D(10001, vec1D);

然後你讀入資料10 1 1979，

City new_city(1, 1979);

vec2D[10].push_back(new_city);

這樣你就知道城市10通往城市1的weight是1979。

要存取通往那個城市是vec[10][0].no，存取1979就是vec[10][0].w。

(因為這個new_city是第一個從back來push進去的，所以index是0)

大致上就這樣用吧。

額外的課題像是size()和capacity()的分別，

sort時自定義vector元素形態時，重載運算子的寫法這些的，

我想書上，網路上資料很多，你一定能自行應用，就不多講了。


Bleed

※ 引述《tropical72 (藍影)》之銘言：
: 補充說明(Supplement)：
: 之前全都用 new, malloc, vector 只有用 1dim,
: 回來翻 primer 4e, 發現有幾個問題想問
: (1) 3.3.2 節-表3.5，vector 竟然有提供
:    ==, !=, <, <=, >, >= 運算子
:    比較時是怎麼判斷??
: (2) 實做 2D vector 時有點卡住
: #define X 2
: #define Y 3
:         vector<int>::size_type x, y;
:         // 2 dim - 1
:         vector <int> *a2 = new vector<int>[X];
:         for(x=0; x<X; x++) a2[x].reserve(Y);
:         // 2 dim - 2
:         vector <vector<int>> a3(X, vector<int>(Y));
: 爬過文後，目前我只會配到這裡而已，
: 只是在這裡，二維以上我完全感受不到使用 vector 的好處
: 這種方式和 new, malloc 似乎沒什麼二樣，也是事先配置好空間
: 到時重新配置空間還先 free 掉 -> 麻煩。
: 調用方法都用下標方式調用，
: 這樣 push_back, resize 該怎麼動手？
: 謝謝各位不吝指教。

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 114.43.124.23
推 tropical72:先感謝您的細心說明!!另您的例子而言,似乎第一維的數
→ tropical72:字無法做更動,能更動的只有第二維的數字?
→ bleed1979:vec2D.resize(20);  從10001down到剩20個vec1D
→ tropical72:那其餘的 (1001-20) 會自動釋放嗎？
→ tropical72:還是 (1001-20)*1000 全都卡在那？
→ bleed1979:以上兩者應該都是。會釋放，但是值沒有被蓋掉，卡在那。
→ bleed1979:另外要小心，如果resize比原本的大，多的部分size是0。
→ tropical72:嗯,這部份我再研究,非常感謝您的細心解說與指導.
→ tropical72:感激不盡!!
→ loveme00835:resize: 如果比當前size還要小, 多餘物件會被解構, 比
→ loveme00835:當前size還要大, 新增的物件會用copy ctor一個個建構
→ loveme00835:引數是一個用該型別default ctor建構的物件, 配置記
→ loveme00835:憶體 vs 建構物件是兩個不同階段的事情, 可參考std::
→ loveme00835:allocator
→ loveme00835:至於比較的問題, 你可以查bits/stl_vector.h, 沒有什
→ loveme00835:麼效率考量而需要特化時, 一般都是選用algorithms來
→ loveme00835:實作, std::equal、std::lexicographical_compare
→ tropical72:感謝 love 補充說明 ^^