Open Pin-Jiun opened 1 year ago
Using Range Constructor
#include <iostream>
#include <vector>
int main()
{
// input array
int src[] = { 1, 2, 3, 4, 5 };
int n = sizeof(src) / sizeof(src[0]);
std::vector<int> dest(src, src + n);
for (int i: dest) {
std::cout << i << " ";
}
return 0;
}
C++11後有引進新的function, begin()
和 end()
#include <iostream>
#include <vector>
int main()
{
// input array
int src[] = { 1, 2, 3, 4, 5 };
std::vector<int> dest(std::begin(src), std::end(src));
for (int i: dest) {
std::cout << i << " ";
}
return 0;
}
Naive Solution
#include <iostream>
#include <vector>
int main()
{
// input array
int src[] = { 1, 2, 3, 4, 5 };
// create an empty vector and push all elements
std::vector<int> dest;
for (int i: src) {
dest.push_back(i);
}
for (int i: dest) {
std::cout << i << " ";
}
return 0;
}
assign function
#include <iostream>
#include <vector>
int main()
{
// input array
int src[] = { 1, 2, 3, 4, 5 };
std::vector<int> dest;
dest.assign(std::begin(src), std::end(src));
for (int i: dest) {
std::cout << i << " ";
}
return 0;
}
參考資料 https://www.techiedelight.com/convert-array-vector-cpp/
前言
vector<int> ivec(10); // 宣告1個vector,裡面有10個int空間。
vector<int> ivec[10]; // 宣告10個vector,每一個都可以存int。
vector<vector<int>> array_2D; // 宣告1個vector,每一個都可以存vector<int>。
vector<int> row;
row.assign(n,0); //配置一個 row 的大小為n, 值為0
vector<vector<int>> array_2D; // 宣告1個vector,每一個都可以存vector<int>。
array_2D.assign(n,row);//配置2維
int n = 3;
int m = 4;
/*
We create a 2D vector containing "n"
elements each having the value "vector<int> (m, 0)".
"vector<int> (m, 0)" means a vector having "m"
elements each of value "0".
Here these elements are vectors.
*/
vector<vector<int>> vec( n , vector<int> (m, 0));
A 2D vector is a vector of the vector. Like 2D arrays, we can declare and assign values to a 2D vector!
Assuming you are familiar with a normal vector in C++, with the help of an example we demonstrate how a 2D vector differs from a normal vector below:
/* Vectors belong to a C++ library
called STL so we need to import
it first! */
#include <vector>
using namespace std;
int main()
{
/*
In the case of a normal vector we initialize it as:
1. vector<datatype> variable_name
Now in the case of a 2D vector all we do is create
a vector of datatype vector.
We simply replace "datatype" with "vector<int>":
1. vector<vector<int>> variable_name
That's literally it! We just created a 2D vector!
On line 23 below we declare an actual 2D vector
named "vect".
*/
vector<vector<int>> vect;
return 0;
}
In a 2D vector, every element is a vector.
Time Complexity: O(1)
Auxiliary Space: O(1)
/* C++ code to demonstrate a 2D vector
with elements(vectors) inside it. */
#include <iostream>
#include <vector>
using namespace std;
int main()
{
/*
Below we initialize a 2D vector
named "vect" on line 12 and then
we declare the values on
line 14, 15 and 16 respectively.
*/
vector<vector<int>> vect
{
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
/*
Now we print the values that
we just declared on lines
14, 15 and 16 using a simple
nested for loop.
*/
for (int i = 0; i < vect.size(); i++)
{
for (int j = 0; j < vect[i].size(); j++)
{
cout << vect[i][j] << " ";
}
cout << endl;
}
return 0;
}
output
1 2 3
4 5 6
7 8 9
Time Complexity: O(N*N)
Auxiliary Space: O(N*N)
/* C++ code to demonstrate a 2D vector
with elements(vectors) inside it. */
#include <iostream>
#include <vector>
using namespace std;
int main()
{
/*
Below we initialize a 2D vector
named "vect" on line 12 and then
we declare the values on
line 14, 15 and 16 respectively.
*/
vector<vector<int>> vect
{
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
/*
Now we print the values that
we just declared on lines
14, 15 and 16 using a simple
nested for loop with the help of iterator.
*/
/*
vector<vector<int>> vect
We can divide this declaration to two parts, which will
help us to understand the below concepts.
1. vect is a 2D vector consisting multiple elements of type vector<int>.
2. vector<int> is a 1D vector consisting of multiple int data.
So we can use iterator provided by STL instead of
i,j variable used in for loop. It can reduce the error which can
happen wrt to i, j operations(i++, j++)
In the below code we are using iterator to access the vector elements.
1. We are getting vect1D vectors of type vector<int> from the 2D vector vect.
2. We are getting int elements to x from the vector<int> vect 1D vector.
*/
for (vector<int> vect1D : vect)
{
for (int x : vect1D)
{
cout << x << " ";
}
cout << endl;
}
return 0;
}
參考網址
https://www.geeksforgeeks.org/2d-vector-in-cpp-with-user-defined-size/
Vector
可視為會自動擴展容量的陣列 以模板(泛型)方式實現,可以儲存任意類型的變數,包括使用者自定義的資料型態 以循序 (Sequential) 的方式維護變數集合-支援隨機存取 使用前預先
#include <vector>
即可 尾端增刪元素很快 : O(1) 中間增刪元素比較費時 : O(n)優先使用 vectors 和 iterators 取代低階的 array 和 pointer
最基礎的一般陣列,有特別強調說,他是在靜態時期編譯起來你就必須給他直接長度的,不能透過輸入賦予長度,雖然在某些 compiler 會過,但其實這件事情是不被大家所允許的。
pointers 和 arrays 對於某些低階任務可能有存在的必要,但我們應該盡量避免使用它們,因為他們容易出錯又很難除錯。一般而言應該優先使用程式庫提供的抽象事物而非語言內建的 array 和 pointer,這一忠告在「多用strings,少用C-Style 字串(亦即以null結尾之字元array)」這件事上尤其合適。
vector 就是動態的配置陣列大小給陣列,不用去操心記憶體,或是程式出錯,完全會自動配置大小,是非常好用的一個工具。 https://hackmd.io/@ndhu-programming-2021/Sy8Oqd5TF
vector 是 array 的進階版,所以他還是一種 array,仍舊是連續配置記憶體,當容量不夠的時候會重新申請空間,並把原本的資料複製或搬到新的記憶體去。 但這樣有點不好,如果今天我們一直往 vector 裡面丟東西,一旦容量不夠,他可能會一直搬來搬去,其實有點沒有效率,因為他會一直釋放資源,添加資源,所以應該減少他配置新空間的次數。
上面這句話簡單的說就是,針對需求,可以配置比需求多一倍的空間,會是比較適當的。
成員函式簡介Method
以容器模式為基準設計的,也就是說,基本上它有
begin()
,end()
,size()
,max_size()
,empty()
,swap()
等用法1. 存取元素的用法
vec[i]
- 存取索引值為 i 的元素值。vec.at(i)
- 存取索引值為 i 的元素的值,vec.front()
- 回傳 vector 第一個元素的值。vec.back()
- 回傳 vector 最尾元素的值。用
operator[]
可能會 Segmentation Fault。以at()
存取會做陣列邊界檢查,如果存取越界將會拋出一個例外,這是與operator[]的唯一差異。撰寫較嚴肅、安全性較高的程式時使用at()
。2. 新增或移除元素的用法
vec.push_back()
- 新增元素至 vector 的尾端,必要時會進行記憶體配置。vec.pop_back()
- 刪除 vector 最尾端的元素。vec.insert()
- 插入一個或多個元素至 vector 內的任意位置。vec.erase()
- 刪除 vector 中一個或多個元素。vec.clear()
- 清空所有元素。 size將會=0少依賴
push_back()
的自動記憶體配置,不是不要用push_back
,是不要讓push_back
自己判定記憶體需求,能自己要記憶體的就自己要,善用reserve()
、resize()
或constructor
引數。迭代器範圍刪除是前閉後開 [a,b) 這個是 STL 迭代器相關函式的設計原則,區間範圍以前閉後開範圍表示 例如,用
erase(
) 刪除全部元素vec.erase( vec.begin(), vec.end() )
,vec.begin()
是在第一個元素,vec.end()
是最後一個元素的下一個元素3. 取得長度/容量的用法
vec.empty()
- 如果 vector 內部為空,則傳回 true 值。vec.size()
- 取得 vector 目前持有的元素個數。vec.max_size()
- 取得 vector 最多可放的元素個數。vec.resize()
- 改變 vector 目前持有的元素個數。vec.capacity()
- 取得 vector 目前可容納的最大元素個數。這個方法與記憶體的配置有關,它通常只會增加,不會因為元素被刪減而隨之減少。 重新配置/重設長度vec.reserve()
- 如有必要,可改變 vector 的容量大小(配置更多的記憶體)。在眾多的 STL 實做,容量只能增加,不可以減少。empty()
和size()==0
不建議使用 size()==0 判斷容器是否為空,用 empty() 判斷較恰當。因為並不是所有容器的 size() 都是 O(1),例如是 linked list 結構,其 size() 是 O(n)。
容量 (capacity) 和長度 (size)
容量 (capacity) : 是這個 vector 擁有的空間。 長度 (size) : 是實際儲存了元素的空間大小。capacity 永遠不小於 size。![image](https://user-images.githubusercontent.com/34474924/191460753-63902cf7-36c8-497a-981e-b2df22bae8b9.png)
reserve()
的目的是擴大容量。做完時,vector 的長度不變,capacity 只會長大不會縮小,資料所在位置可能會移動 (因為會重配空間)。因為 vector 一開始是空的,立刻預留顯然比填了資料後才預留省了拷貝資料的時間。resize()
的目的是改變 vector 的長度。做完時,vector 的長度會改變為指定的大小,capacity 則視需要調整,確保不小於 size,資料所在位置可能會移動。如果變小就擦掉尾巴的資料,如果變大就補零。補零如果會超過容量,會做重配空間的動作。shrink_to_fit()
4. 疊代 (Iterator)
vec.begin()
- 回傳一個 iterator,它指向 vector 第一個元素。vec.end()
- 回傳一個 iterator,它指向 vector 最尾端元素的下一個位置(請注意:它不是最末元素)。vec.rbegin()
- Return reverse iterator to reverse beginningvec.rend()
- Return reverse iterator to reverse end。vec.cbegin()
vec.cend
-回傳的 iterator將為constant, 無法進行修改crbegin()
crend()
5.Other Method
assign()
Assign vector contentswap()
Exchanges the content of the container by the content of x, which is another vector object of the same type. Sizes may differ.output
常用的 vector 程式寫法
1. 尋訪
或是直接用for尋訪
2. Construction and Assignment
3.用 C++ 的 Vector 產生動態二維陣列
4.使用者自定義的資料型態
vector 的優缺點
Advantages
宣告時不用確定大小,由後續的開發配置長度 節省空間,更提供 shrink_to_fit() 函式供開發者省去空間 支持 random access,也就是可以依靠 [i] 去取得資料 插入比較方便 若要針對一搬的陣列做插入,要整個搬移。
Disadvantages
插入與刪除比較複雜,且效率比較低落-你可能要搞懂疊代器(iterator) 只能再末端 push 跟 pop,但正常來說開頭端也可以更好,像 queue 一樣。
參考資料https://mropengate.blogspot.com/2015/07/cc-vector-stl.html https://cplusplus.com/reference/vector/vector/