29. Standard Template library(STL) - Vector
29 Sep 2019 | C++
Standard Template Library (STL)
- C++ 표준 라이브러리를 보면 꽤나 많은 종류의 라이브러리들이 있습니다.
- 대표적으로 입출력 라이브러리 (iostream 등등), 시간 관련 라이브러리 (chrono), 정규표현식 라이브러리 (regex) 등등 들이 있지요.
- 하지만 보통 C++ 템플릿 라이브러리(STL)를 일컫는다면 다음과 같은 세 개의 라이브러리들을 의미합니다
- 임의 타입의 객체를 보관할 수 있는 컨테이너 (container)
- 컨테이너에 보관된 원소에 접근할 수 있는 반복자 (iterator)
- 반복자들을 가지고 일련의 작업을 수행하는 알고리즘 (algorithm)
- EX
- 편지를 보관하는 각각의 편지함들은 ‘컨테이너’
- 편지를 보고 원하는 편지함을 찾는 일은 ‘반복자’
- 편지들을 편지함에 날짜 순서로 정렬하여 넣는 일은 ‘알고리즘’
- 임의 타입의 객체를 보관할 수 있는 컨테이너 (container)
- 우리가 다루려는 객체가 어떤 특성을 갖는지 무관하게 라이브러리를 자유롭게 사용할 수 있다는 것입니다 (because of Template).
- 만일 사용하려는 자료형이 int 나 string 과 같은 평범한 애들이 아니라, 우리가 만든 임의이 클래스의 객체들이여도 자유롭게 위 라이브러리의 기능들을 모두 활용할 수 있습니다.
- 반복자의 도입으로 알고리즘 라이브러리에 필요한 최소한의 코드만을 작성할 수 있게 되었습니다.
- 존의 경우 M 개 종류의 컨테이가 있고 N 종류의 알고리즘이 있다면 이 모든 것을 지원하려면 MN 개의 알고리즘 코드가 있어야만 했습니다.
- 반복자를 이용해서 컨테이너를 추상화 시켜서 접근할 수 있기 때문에 N 개의 알고리즘 코드 만으로 M 종류의 컨테이너들을 모두 지원할 수 있게됩니다.
STL 컨테이너 - Vector(STD::vector)
- C++ STL 에서 컨테이너는 크게 두 가지 종류가 있습니다.
- 먼저 배열 처럼 객체들을 순차적으로 보관하는 시퀀스 컨테이너 (sequence container)
- 키를 바탕으로 대응되는 값을 찾아주는 연관 컨테이너 (associative container) 가 있습니다.
- 시퀀스 컨테이너의 경우 vector, list, deque 이렇게 3 개가 정의되어 있습니다.
- (vector) 의 경우, 쉽게 생각하면 가변길이 배열이
- 벡터에는 원소들이 메모리 상에서 실제로 순차적으로 저장되어 있고, 따라서 임의의 위치에 있는 원소를 접근하는 것을 매우 빠르게 수행할 수 있습니다.
- vector 의 경우, 임의의 위치에 있는 원소에 접근을 O(1) 로 수행할 수 있습니다. 게다가 맨 뒤에 새로운 원소를 추가하거나 제거하는 것 역시 O(1) 에 수행합니다.
- vector 의 임의의 원소에 접근하는 것은 배열처럼 [] 를 이용하거나, at 함수를 이용하면 됩니다.
- 또한 맨 뒤에 원소를 추가하거나 제거하기 위해서는 push_back 혹은 pop_back 함수를 사용하면 됩니다. 아래 예를 보겠습니다
#include <iostream>
#include <vector>
int main() {
std::vector<int> vec;
vec.push_back(10); // 맨 뒤에 10 추가
vec.push_back(20); // 맨 뒤에 20 추가
vec.push_back(30); // 맨 뒤에 30 추가
vec.push_back(40); // 맨 뒤에 40 추가
for (std::vector<int>::size_type i = 0; i < vec.size(); i++) {
std::cout << "vec 의 " << i + 1 << " 번째 원소 :: " << vec[i] << std::endl;
}
}
- 벡터의 크기를 리턴하는 함수인 size 의 경우, 그리턴하는 값의 타입은 size_type 멤버 타입으로 정의되어 있습니다.
- 맨 뒤에 원소를 추가하는 작업은 엄밀히 말하자면 amortized O(1) 이라고 합니다. (amortized 의 뜻은 분할상환이란 뜻)
- 왜냐면 보통은 vector 의 경우 현재 가지고 있는 원소의 개수 보다 더 많은 공간을 할당해 놓고 있습니다.
- 예를 들어 현재 vector 에 있는 원소의 개수가 10 개라면 이미 20개를 저장할 수 있는 공간을 미리 할당해놓게됩니다.
- 따라서 만약에 뒤에 새로운 원소를 추가하게 된다면 새롭게 메모리를 할당할 필요가 없이, 그냥 이미 할당된 공간에 그 원소를 쓰기만 하면 됩니다.
- 따라서 대부분의 경우 O(1) 으로 vector 맨 뒤에 새로운 원소를 추가하거나 지울 수 있습니다.
- 문제가 되는 상황은 할당된 공간을 다 채웠을 때 입니다.
- 이 때는 어쩔 수 없이, 새로운 큰 공간을 다시 할당하고, 기존의 원소들을 복사하는 수 밖에 없습니다.
- 따라서 이 경우 n 개의 원소를 모두 복사해야 하기 때문에 O(n) 으로 수행됩니다.
- 하지만 이 O(n) 으로 수행되는 경우가 매우 드물기 때문에, 전체적으로 평균을 내보았을 때 O(1) 으로 수행됨을 알 수 있습니다.
- 이렇기에 amortized O(1)O(1) 이라고 부르게 됩니다.
- vector 기능은 맨 뒤에 원소를 추가하거나 제거하는 것은 빠르지만,임의의 위치에 원소를 추가하거나 제거하는 것은 O(n) 으로 느립니다.
- 왜냐하면 어떤 자리에 새로운 원소를 추가하거나 뺄 경우 그 뒤에 오는 원소들을 한 칸 씩 이동시켜 주어야만 하기 때문이지요. 따라서 이는 nn 번의 복사가 필요로 합니다.
- 따라서 만일 맨 뒤가 아닌 위치에 데이터를 추가하거나 제거하는 작업이 많은 일일 경우 vector 를 사용하면 안되겠지요.
- 결과적으로 vector 의 복잡도를 정리해보자면 아래와 같습니다.
- 임의의 위치 원소 접근 ([], at) : O(1)
- 맨 뒤에 원소 추가 및 제거 (push_back/pop_back) : amortized O(1)O(1); (평균적으로 O(1)O(1) 이지만 최악의 경우 O(n)O(n) )
- 임의의 위치 원소 추가 및 제거 (insert, erase) : O(n)O(n)
Example
#include <iostream>
#include <vector>
#include <string>
// vector is basically like a resizeable array
using namespace std;
int main() {
vector<string> strings;
//vector is template class
//vector<> <- inside of blanket is type of the variable we are going to create
//resizeable automatically memory value.
//if we use push_back we dont need to add strings()
strings.push_back("one");
strings.push_back("two");
strings.push_back("three");
// index one two in along way
// Push_back은 vector 의 끝에 요소를 추가할 때 사용 되는 함수이다.
// push_back is delete the element in list
cout << "For loop: " << endl;
for(int i=0; i<strings.size(); i++) {
cout << strings[i] << endl;
}
cout << endl;
// .end() <- after the element
// vector.end() <- end interator를 반환
// vector.begin() <- beginning iterator 반환
//
cout << "Iterator loop: " << endl;
//The auto keyword specifies that the type of the variable that is begin declared will automatically be deduced
//from its initializer and for functions if their return type is auto then that will be evaluated by return type expression at runtime.
// auto 키워드를 사용하면 초깃값의 형식에 맞춰 선언하는 인스턴스(뱐수)의 형식이 자동으로 결정된다.
for(auto it = strings.begin(); it != strings.end(); ++it) {
cout << *it << endl;
}
cout << endl;
cout << "Single item." << endl;
vector<string>::iterator it = strings.begin();
//strings.begin()<- this will actually give us a thing called an iterator(반복자)
//which points to the first element in the vector.
//vector<string>::iterator it <- it is that equal to return value of string stop again
it += 2;
// so we gonna call the first vector + 2 index value
cout << *it << endl;
return 0;
}
Result
Vector and Memory
- capacity is the size of the internal array that the vector is using and that size is going to increase as you add elements
- we’ve reserve we precisely rated 20 elements. so capacity is 20
- capacity 배열의 크기만 신경쓴다. 값은 신경안씀!
- expenantionaly increase number of elements
- proportional to the number of elements in the array if insert an element into a vector and it has to internally create a new array a bigger capacity and then copy the elements from the order rates.
- how big our arrays going to get based on its current size and it crease the capacity based on that
- capacity is completely different the size of capacity is the size of the internal rate it reserved the size the actual number of elements that are added to that vector
- numbers.resize(100) <- only resize size of valuable.
- reserve method, we want to reserve(적립하다.) memory and in turn on a rate increase size of capacity array.
- numbers.clear() <- remove all of the element in the vector
- doent change the capacity of the internal array
- Capacity가 꽉차서 원소를 추가하게 되면 배열의 수는 더블로 늘어난다
- Ex 사이즈 2에 원소가 하나 늘어나면 Capacity 가 4 가 되고 똑같이 원소가 또 추가 되면 8되고
```
#include
#include
using namespace std;
int main() {
vector<double> numbers(0);
//specifiy the argument (0)
cout << "Size: " << numbers.size() << endl;
int capacity = numbers.capacity();
//.capacity is the size of the internal array that the vector is using and that size is
//going to increase as you add elements
cout << "Capacity: " << capacity << endl;
//we've reserve we precisely rated 20 elements. so capacity is 20
//capacity 배열의 크기만 신경쓴다. 값은 신경안씀!
for(int i=0; i<10000; i++) {
if(numbers.capacity() != capacity) {
capacity = numbers.capacity();
cout << "Capacity: " << capacity << endl;
}
numbers.push_back(i);
}
// expenantionaly incresae number of elemenst
// propotiaonal to the number of elements in the array
// if insert an element into a vector and it has to internally create a new array
// a bigger capacity and then copy the elements from the order rates.
// how big our arrays going to get based on its current size
// and it crease the capacity based on that
// capacity is completely different the size of capacity is the size of the internal
// rate it reserved the size the actual number of elements that are added to that vector
numbers.reserve(100000);
//numbers.resize(100) <- only resize size of valuable.
//reserve method, we want to reserve(적립하다.) memory and in turn on a rate
//increase size of capacity array.
cout << numbers[2] << endl;
cout << "Size: " << numbers.size() << endl;
cout << "Capacity: " << numbers.capacity() << endl;
//numbers.clear() <- remove all of the element in the vector
//doent change the capacity of the internal array
return 0; }
> Result
<a href="https://postimg.cc/kVvY541T"><img src="https://i.postimg.cc/Dzt9B4q3/421321312.png" width="700px" title="source: imgur.com" /></a>
# Two Dimensional vectors
- Vector<> <- column
- Vector<vector<>> <- raw
- grid( 3<- 3 raw , vector<int>(4,7) <- some value put)
- 3 space of raw, 4 space of column all value is 7
#include
#include
using namespace std;
int main() {
vector< vector > grid(3, vector(4, 7));
//Vector<> <- column
//Vector<vector<>> <- raw
//grid( 3<- 3 raw , vector(4,7) <- some value put)
// 3 space of raw, 4 space of column
grid[1].push_back(8);
for(int row=0; row < grid.size(); row++) {
for(int col=0; col < grid[row].size(); col++) {
cout << grid[row][col] << flush;
//grid[row] is the vector
//and [col] is to access the elements in that particular row using
//this column
}
cout << endl;
}
return 0; } ``` > Result
Sorting Vectors Deque Friend
- Deque : 리스트의 양쪽 끝에서 삽입과 삭제를 모두 허용하는 자료의 구조. 이것은 스택과 큐의 자료 구조를 복합한 형태이다.
Deque
- 덱은 벡터와 비슷하게 O(1) 으로 임의의 위치의 원소에 접근할 수 있으며 맨 뒤에 원소를 추가/제거 하는 작업도 O(1) 으로 수행할 수 있습니다.
- 뿐만아니라 벡터와는 다르게 맨 앞에 원소를 추가/제거 하는 작업 까지도 O(1)O(1) 으로 수행 가능합니다.
- 임의의 위치에 있는 원소를 제거/추가 하는 작업은 벡터와 마찬가지로 O(n)O(n) 으로 수행 가능합니다
- 그렇다면 덱이 벡터에 비해 모든 면에서 비교 우위에 있는 걸까요?
- 안타깝게도 벡터와는 다르게 덱의 경우 원소들이 실제로 메모리 상에서 연속적으로 존재하지는 않습니다.
- 이 때문에 원소들이 어디에 저장되어 있는지에 대한 정보를 보관하기 위해 추가적인 메모리가 더 필요로 합니다.
- 실제 예로, 64 비트 libc++ 라이브러리의 경우 1 개의 원소를 보관하는 덱은 그 원소 크기에 비해 8 배나 더 많은 메모리를 필요로 합니다).
- 즉 덱은 실행 속도를 위해 메모리를 (많이) 희생하는 컨테이너라 보면 됩니다.
- 벡터와는 다르게 원소들이 메모리에 연속되어 존재하는 것이 아니라 일정 크기로 잘려서 각각의 블록 속에 존재합니다.
- 따라서 이 블록들이 메모리 상에 어느 곳에 위치하여 있는지 저장하기 위해서 각각의 블록들의 주소를 저장하는 벡터가 필요로 합니다.
- 존의 벡터와는 조금 다르게, 새로 할당 시에 앞쪽 및 뒤쪽 모두에 공간을 남겨놓게 됩니다. (벡터의 경우 뒤쪽에만 공간이 남았지요) 따라서 이를 통해 맨 앞과 맨 뒤에 O(1) 의 속도로 insert 및 erase 를 수행할 수 있는 것입니다.
- 그렇다면 왜 덱이 벡터 보다 원소를 삽입하는 작업이 더 빠른 것일까요?
- 위와 같은 상황에서 deq.push_back(10) 을 수행하였다고 생각해봅시다.
- 그렇다면 단순히 새로운 블록을 만들어서 뒤에 추가되는 원소를 넣어주면 됩니다
- 즉 기존의 원소들을 복사할 필요가 전혀 없다는 의미 입니다.
- 반면에 벡터의 경우
- 만약에 기존에 할당한 메모리가 꽉 차면 모든 원소들을 새로운 공간에 복사해야 합니다. 따라서 평균적으로 덱이 벡터보다 더 빠르게 작동합니다.
- 물론 덱의 경우 블록 주소를 보관하는 벡터가 꽉 차게 되면 새로운 공간에 모두 복사해야 합니다.
- 하지만 블록 주소의 개수는 전체 원소 개수 보다 적고 대체로 벡터에 저장되는객체들의 크기가 주소값의 크기보다 크기 때문에 복사 속도가 훨씬 빠릅니다.)
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
class Test
{
string name;
int id;
public:
Test(int id, string name) :
id(id), name(name)
{
}
bool operator<(const Test &other) const {
return name == other.name ? id < other.id : name < other.name;
//?: <- is the conditional operator
// condition ? result_if_true : result_if_false
/* int qempty()
{
if(f==r)
{
return 1;
}
else
{
return 0;
}
}*/ // example of conditional operator
}
// because of for function??
void print()
{
cout << id << ": " << name << endl;
}
friend bool comp(const Test &first, const Test &second);
// friend function은 protect data/function 에 접근이 가능하다.
};
bool comp(const Test &first, const Test &second)
{
return first.name < second.name;
}
// 알파뱃 순서로 정령한다.
int main(int argc, char const *argv[])
{
vector<Test> tests;
tests.push_back(Test(5, "Mike"));
tests.push_back(Test(10, "Sue"));
tests.push_back(Test(7, "Raj"));
tests.push_back(Test(3, "Vicky"));
sort(tests.begin(), tests.end(), comp);
//comp is the funtion pointer
for(int i = 0; i < tests.size(); i++)
{
tests[i].print();
}
return 0;
}
Result
REFERENCE
Standard Template Library (STL)
- C++ 표준 라이브러리를 보면 꽤나 많은 종류의 라이브러리들이 있습니다.
- 대표적으로 입출력 라이브러리 (iostream 등등), 시간 관련 라이브러리 (chrono), 정규표현식 라이브러리 (regex) 등등 들이 있지요.
- 하지만 보통 C++ 템플릿 라이브러리(STL)를 일컫는다면 다음과 같은 세 개의 라이브러리들을 의미합니다
- 임의 타입의 객체를 보관할 수 있는 컨테이너 (container)
- 컨테이너에 보관된 원소에 접근할 수 있는 반복자 (iterator)
- 반복자들을 가지고 일련의 작업을 수행하는 알고리즘 (algorithm)
- EX
- 편지를 보관하는 각각의 편지함들은 ‘컨테이너’
- 편지를 보고 원하는 편지함을 찾는 일은 ‘반복자’
- 편지들을 편지함에 날짜 순서로 정렬하여 넣는 일은 ‘알고리즘’
- 임의 타입의 객체를 보관할 수 있는 컨테이너 (container)
- 우리가 다루려는 객체가 어떤 특성을 갖는지 무관하게 라이브러리를 자유롭게 사용할 수 있다는 것입니다 (because of Template).
- 만일 사용하려는 자료형이 int 나 string 과 같은 평범한 애들이 아니라, 우리가 만든 임의이 클래스의 객체들이여도 자유롭게 위 라이브러리의 기능들을 모두 활용할 수 있습니다.
- 반복자의 도입으로 알고리즘 라이브러리에 필요한 최소한의 코드만을 작성할 수 있게 되었습니다.
- 존의 경우 M 개 종류의 컨테이가 있고 N 종류의 알고리즘이 있다면 이 모든 것을 지원하려면 MN 개의 알고리즘 코드가 있어야만 했습니다.
- 반복자를 이용해서 컨테이너를 추상화 시켜서 접근할 수 있기 때문에 N 개의 알고리즘 코드 만으로 M 종류의 컨테이너들을 모두 지원할 수 있게됩니다.
STL 컨테이너 - Vector(STD::vector)
- C++ STL 에서 컨테이너는 크게 두 가지 종류가 있습니다.
- 먼저 배열 처럼 객체들을 순차적으로 보관하는 시퀀스 컨테이너 (sequence container)
- 키를 바탕으로 대응되는 값을 찾아주는 연관 컨테이너 (associative container) 가 있습니다.
- 시퀀스 컨테이너의 경우 vector, list, deque 이렇게 3 개가 정의되어 있습니다.
- (vector) 의 경우, 쉽게 생각하면 가변길이 배열이
- 벡터에는 원소들이 메모리 상에서 실제로 순차적으로 저장되어 있고, 따라서 임의의 위치에 있는 원소를 접근하는 것을 매우 빠르게 수행할 수 있습니다.
- vector 의 경우, 임의의 위치에 있는 원소에 접근을 O(1) 로 수행할 수 있습니다. 게다가 맨 뒤에 새로운 원소를 추가하거나 제거하는 것 역시 O(1) 에 수행합니다.
- vector 의 임의의 원소에 접근하는 것은 배열처럼 [] 를 이용하거나, at 함수를 이용하면 됩니다.
- 또한 맨 뒤에 원소를 추가하거나 제거하기 위해서는 push_back 혹은 pop_back 함수를 사용하면 됩니다. 아래 예를 보겠습니다
#include <iostream>
#include <vector>
int main() {
std::vector<int> vec;
vec.push_back(10); // 맨 뒤에 10 추가
vec.push_back(20); // 맨 뒤에 20 추가
vec.push_back(30); // 맨 뒤에 30 추가
vec.push_back(40); // 맨 뒤에 40 추가
for (std::vector<int>::size_type i = 0; i < vec.size(); i++) {
std::cout << "vec 의 " << i + 1 << " 번째 원소 :: " << vec[i] << std::endl;
}
}
- 벡터의 크기를 리턴하는 함수인 size 의 경우, 그리턴하는 값의 타입은 size_type 멤버 타입으로 정의되어 있습니다.
- 맨 뒤에 원소를 추가하는 작업은 엄밀히 말하자면 amortized O(1) 이라고 합니다. (amortized 의 뜻은 분할상환이란 뜻)
- 왜냐면 보통은 vector 의 경우 현재 가지고 있는 원소의 개수 보다 더 많은 공간을 할당해 놓고 있습니다.
- 예를 들어 현재 vector 에 있는 원소의 개수가 10 개라면 이미 20개를 저장할 수 있는 공간을 미리 할당해놓게됩니다.
- 따라서 만약에 뒤에 새로운 원소를 추가하게 된다면 새롭게 메모리를 할당할 필요가 없이, 그냥 이미 할당된 공간에 그 원소를 쓰기만 하면 됩니다.
- 따라서 대부분의 경우 O(1) 으로 vector 맨 뒤에 새로운 원소를 추가하거나 지울 수 있습니다.
- 문제가 되는 상황은 할당된 공간을 다 채웠을 때 입니다.
- 이 때는 어쩔 수 없이, 새로운 큰 공간을 다시 할당하고, 기존의 원소들을 복사하는 수 밖에 없습니다.
- 따라서 이 경우 n 개의 원소를 모두 복사해야 하기 때문에 O(n) 으로 수행됩니다.
- 하지만 이 O(n) 으로 수행되는 경우가 매우 드물기 때문에, 전체적으로 평균을 내보았을 때 O(1) 으로 수행됨을 알 수 있습니다.
- 이렇기에 amortized O(1)O(1) 이라고 부르게 됩니다.
- vector 기능은 맨 뒤에 원소를 추가하거나 제거하는 것은 빠르지만,임의의 위치에 원소를 추가하거나 제거하는 것은 O(n) 으로 느립니다.
- 왜냐하면 어떤 자리에 새로운 원소를 추가하거나 뺄 경우 그 뒤에 오는 원소들을 한 칸 씩 이동시켜 주어야만 하기 때문이지요. 따라서 이는 nn 번의 복사가 필요로 합니다.
- 따라서 만일 맨 뒤가 아닌 위치에 데이터를 추가하거나 제거하는 작업이 많은 일일 경우 vector 를 사용하면 안되겠지요.
- 결과적으로 vector 의 복잡도를 정리해보자면 아래와 같습니다.
- 임의의 위치 원소 접근 ([], at) : O(1)
- 맨 뒤에 원소 추가 및 제거 (push_back/pop_back) : amortized O(1)O(1); (평균적으로 O(1)O(1) 이지만 최악의 경우 O(n)O(n) )
- 임의의 위치 원소 추가 및 제거 (insert, erase) : O(n)O(n)
Example
#include <iostream>
#include <vector>
#include <string>
// vector is basically like a resizeable array
using namespace std;
int main() {
vector<string> strings;
//vector is template class
//vector<> <- inside of blanket is type of the variable we are going to create
//resizeable automatically memory value.
//if we use push_back we dont need to add strings()
strings.push_back("one");
strings.push_back("two");
strings.push_back("three");
// index one two in along way
// Push_back은 vector 의 끝에 요소를 추가할 때 사용 되는 함수이다.
// push_back is delete the element in list
cout << "For loop: " << endl;
for(int i=0; i<strings.size(); i++) {
cout << strings[i] << endl;
}
cout << endl;
// .end() <- after the element
// vector.end() <- end interator를 반환
// vector.begin() <- beginning iterator 반환
//
cout << "Iterator loop: " << endl;
//The auto keyword specifies that the type of the variable that is begin declared will automatically be deduced
//from its initializer and for functions if their return type is auto then that will be evaluated by return type expression at runtime.
// auto 키워드를 사용하면 초깃값의 형식에 맞춰 선언하는 인스턴스(뱐수)의 형식이 자동으로 결정된다.
for(auto it = strings.begin(); it != strings.end(); ++it) {
cout << *it << endl;
}
cout << endl;
cout << "Single item." << endl;
vector<string>::iterator it = strings.begin();
//strings.begin()<- this will actually give us a thing called an iterator(반복자)
//which points to the first element in the vector.
//vector<string>::iterator it <- it is that equal to return value of string stop again
it += 2;
// so we gonna call the first vector + 2 index value
cout << *it << endl;
return 0;
}
Result
Vector and Memory
- capacity is the size of the internal array that the vector is using and that size is going to increase as you add elements
- we’ve reserve we precisely rated 20 elements. so capacity is 20
- capacity 배열의 크기만 신경쓴다. 값은 신경안씀!
- expenantionaly increase number of elements
- proportional to the number of elements in the array if insert an element into a vector and it has to internally create a new array a bigger capacity and then copy the elements from the order rates.
- how big our arrays going to get based on its current size and it crease the capacity based on that
- capacity is completely different the size of capacity is the size of the internal rate it reserved the size the actual number of elements that are added to that vector
- numbers.resize(100) <- only resize size of valuable.
- reserve method, we want to reserve(적립하다.) memory and in turn on a rate increase size of capacity array.
- numbers.clear() <- remove all of the element in the vector
- doent change the capacity of the internal array
- Capacity가 꽉차서 원소를 추가하게 되면 배열의 수는 더블로 늘어난다
- Ex 사이즈 2에 원소가 하나 늘어나면 Capacity 가 4 가 되고 똑같이 원소가 또 추가 되면 8되고
```
#include
#include using namespace std;
int main() {
vector<double> numbers(0);
//specifiy the argument (0)
cout << "Size: " << numbers.size() << endl;
int capacity = numbers.capacity();
//.capacity is the size of the internal array that the vector is using and that size is
//going to increase as you add elements
cout << "Capacity: " << capacity << endl;
//we've reserve we precisely rated 20 elements. so capacity is 20
//capacity 배열의 크기만 신경쓴다. 값은 신경안씀!
for(int i=0; i<10000; i++) {
if(numbers.capacity() != capacity) {
capacity = numbers.capacity();
cout << "Capacity: " << capacity << endl;
}
numbers.push_back(i);
}
// expenantionaly incresae number of elemenst
// propotiaonal to the number of elements in the array
// if insert an element into a vector and it has to internally create a new array
// a bigger capacity and then copy the elements from the order rates.
// how big our arrays going to get based on its current size
// and it crease the capacity based on that
// capacity is completely different the size of capacity is the size of the internal
// rate it reserved the size the actual number of elements that are added to that vector
numbers.reserve(100000);
//numbers.resize(100) <- only resize size of valuable.
//reserve method, we want to reserve(적립하다.) memory and in turn on a rate
//increase size of capacity array.
cout << numbers[2] << endl;
cout << "Size: " << numbers.size() << endl;
cout << "Capacity: " << numbers.capacity() << endl;
//numbers.clear() <- remove all of the element in the vector
//doent change the capacity of the internal array
return 0; }
> Result
<a href="https://postimg.cc/kVvY541T"><img src="https://i.postimg.cc/Dzt9B4q3/421321312.png" width="700px" title="source: imgur.com" /></a>
# Two Dimensional vectors
- Vector<> <- column
- Vector<vector<>> <- raw
- grid( 3<- 3 raw , vector<int>(4,7) <- some value put)
- 3 space of raw, 4 space of column all value is 7
#include
using namespace std;
int main() {
vector< vector
grid[1].push_back(8);
for(int row=0; row < grid.size(); row++) {
for(int col=0; col < grid[row].size(); col++) {
cout << grid[row][col] << flush;
//grid[row] is the vector
//and [col] is to access the elements in that particular row using
//this column
}
cout << endl;
}
return 0; } ``` > Result
Sorting Vectors Deque Friend
- Deque : 리스트의 양쪽 끝에서 삽입과 삭제를 모두 허용하는 자료의 구조. 이것은 스택과 큐의 자료 구조를 복합한 형태이다.
Deque
- 덱은 벡터와 비슷하게 O(1) 으로 임의의 위치의 원소에 접근할 수 있으며 맨 뒤에 원소를 추가/제거 하는 작업도 O(1) 으로 수행할 수 있습니다.
- 뿐만아니라 벡터와는 다르게 맨 앞에 원소를 추가/제거 하는 작업 까지도 O(1)O(1) 으로 수행 가능합니다.
- 임의의 위치에 있는 원소를 제거/추가 하는 작업은 벡터와 마찬가지로 O(n)O(n) 으로 수행 가능합니다
- 그렇다면 덱이 벡터에 비해 모든 면에서 비교 우위에 있는 걸까요?
- 안타깝게도 벡터와는 다르게 덱의 경우 원소들이 실제로 메모리 상에서 연속적으로 존재하지는 않습니다.
- 이 때문에 원소들이 어디에 저장되어 있는지에 대한 정보를 보관하기 위해 추가적인 메모리가 더 필요로 합니다.
- 실제 예로, 64 비트 libc++ 라이브러리의 경우 1 개의 원소를 보관하는 덱은 그 원소 크기에 비해 8 배나 더 많은 메모리를 필요로 합니다).
- 즉 덱은 실행 속도를 위해 메모리를 (많이) 희생하는 컨테이너라 보면 됩니다.
- 벡터와는 다르게 원소들이 메모리에 연속되어 존재하는 것이 아니라 일정 크기로 잘려서 각각의 블록 속에 존재합니다.
- 따라서 이 블록들이 메모리 상에 어느 곳에 위치하여 있는지 저장하기 위해서 각각의 블록들의 주소를 저장하는 벡터가 필요로 합니다.
- 존의 벡터와는 조금 다르게, 새로 할당 시에 앞쪽 및 뒤쪽 모두에 공간을 남겨놓게 됩니다. (벡터의 경우 뒤쪽에만 공간이 남았지요) 따라서 이를 통해 맨 앞과 맨 뒤에 O(1) 의 속도로 insert 및 erase 를 수행할 수 있는 것입니다.
- 그렇다면 왜 덱이 벡터 보다 원소를 삽입하는 작업이 더 빠른 것일까요?
- 위와 같은 상황에서 deq.push_back(10) 을 수행하였다고 생각해봅시다.
- 그렇다면 단순히 새로운 블록을 만들어서 뒤에 추가되는 원소를 넣어주면 됩니다
- 즉 기존의 원소들을 복사할 필요가 전혀 없다는 의미 입니다.
- 반면에 벡터의 경우
- 만약에 기존에 할당한 메모리가 꽉 차면 모든 원소들을 새로운 공간에 복사해야 합니다. 따라서 평균적으로 덱이 벡터보다 더 빠르게 작동합니다.
- 물론 덱의 경우 블록 주소를 보관하는 벡터가 꽉 차게 되면 새로운 공간에 모두 복사해야 합니다.
- 하지만 블록 주소의 개수는 전체 원소 개수 보다 적고 대체로 벡터에 저장되는객체들의 크기가 주소값의 크기보다 크기 때문에 복사 속도가 훨씬 빠릅니다.)
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
class Test
{
string name;
int id;
public:
Test(int id, string name) :
id(id), name(name)
{
}
bool operator<(const Test &other) const {
return name == other.name ? id < other.id : name < other.name;
//?: <- is the conditional operator
// condition ? result_if_true : result_if_false
/* int qempty()
{
if(f==r)
{
return 1;
}
else
{
return 0;
}
}*/ // example of conditional operator
}
// because of for function??
void print()
{
cout << id << ": " << name << endl;
}
friend bool comp(const Test &first, const Test &second);
// friend function은 protect data/function 에 접근이 가능하다.
};
bool comp(const Test &first, const Test &second)
{
return first.name < second.name;
}
// 알파뱃 순서로 정령한다.
int main(int argc, char const *argv[])
{
vector<Test> tests;
tests.push_back(Test(5, "Mike"));
tests.push_back(Test(10, "Sue"));
tests.push_back(Test(7, "Raj"));
tests.push_back(Test(3, "Vicky"));
sort(tests.begin(), tests.end(), comp);
//comp is the funtion pointer
for(int i = 0; i < tests.size(); i++)
{
tests[i].print();
}
return 0;
}
Result
REFERENCE
Comments