[C++] 벡터(std::vector)
- std::array의 크기는 컴파일 시간에 결정되는 상수여야 함. 따라서 프로그램 실행 중에는 변경할 수 없음.
- std::array의 크기가 고정되어 있어서 원소를 더 추가하거나 삭제할 수 없음.
- std::array의 메모리 할당 방법을 변경할 수 없습니다. 항사 스택 메모리를 사용함.
위와 같은 std::array의 단점을 피하고 동적,가변의 데이터를 처리하기 위해 std::vector가 등장함.
vector는 가변 크기 배열 이라고 생각하면 됨.
std::vector 초기화
// 크기가 0인 벡터 선언
std::vector<int> vec;
// 지정한 초깃값으로 이루어진 크기가 5인 벡터 선언
std::vector<int> vec = {1, 2, 3, 4, 5};
// 크기가 10인 벡터 선언
std::vector<int> vec(10);
// 크기가 10이고, 모든 원소가 5로 초기화된 벡터 선언
std::vector<int> vec(10, 5);
push_back() 또는 insert()
벡터에 새로운 원소를 추가하려면 push_back() 또는 insert()함수를 사용함.
push_back()함수는 벡터의 맨 마지막에 새로운 원소를 추가함.
insert()함수는 삽입할 위치를 나타내는 반복자를 첫 번째 인자로 받음으로써 원하는 위치에 원소를 추가함.
push_back()함수의 동작을 수도코드로 나타내면 다음과 같음.
push_back(val):
if size capacity //새 원소를 추가할 공간이 있는 경우
- 마지막 원소 다음에 val 저장 - 벡터 크기를 1만큼 증가
- return;
if vector is already full //할당된 메모리 공간이 가득 차 있는 경우
- 2*size 크기의 메모리를 새로 할당
- 새로 할당한 메모리로 기존 원소 전부를 복사/이동
- 데이터 포인터를 새로 할당한 메모리 주소로 지정
- 마지막 원소 다음에 val을 저장하고, 벡터 크기를 1만큼 증가
맨 뒤에 원소를 삽입할 때, 뒤쪽에 남아있는 공간이 있다면 O(1)의 시간이 걸림.
그러나 공간이 충분하지 않으면 모든 원소를 복사/이동해야 하며, 이때는 O(n)의 시간이 걸림.
insert() 함수의 경우, 지정한 반복자 위치 다음의 모든 원소를 이동시키는 연산이 필요함.
필요한 경우 메모리를 새로 할당하는 작업도 수행됨.
원소들을 이동하는 연산 때문에 insert() 함수는 O(n)의 시간이 걸림.
그리고 벡터는 일반 배열과 같은 방식의 접근방법이 허용됨.
[ ]기호를 활용할수 있다는 뜻임.
vector<int> vec;
vec.push_back(2);
vec.push_back(5);
cout<<vec[1]<<endl;
//결과:5 출력됨
find()
- 헤더파일: #include
벡터에서 특정 값이 들어 있는지 찾고, 해당 값이 있는 위치를 알기 위해서 find()함수를 사용.
1. vector내에 해당 원소가 존재하는지 확인
find(v.begin(), v.end(), 찾을 대상)
리턴 값이 v.end()인 경우 => 해당 원소가 존재하지 않는 것
리턴 값이 v.end()가 아닌 경우 => 해당 원소 존재하는 것
2. vector내에서 해당 원소가 위치하는 인덱스 찾기
find(v.begin(), v.end(), 찾을 대상) - v.begin()
push_back()과 insert()함수와 find()함수를 사용하는 예제 코드는 다음과 같음.
std::vector<int> vec; // 비어 있는 벡터 생성: {}
vec.push_back(1); // 맨 뒤에 1 추가: {1}
vec.push_back(2); // 맨 뒤에 2 추가: {1, 2}
vec.insert(vec.begin(), 0); // 맨 앞에 0 추가: {0, 1, 2}
vec.insert(find(vec.begin(), vec.end(), 1), 4); // 1 앞에 4 추가: {0, 4, 1, 2}
emplace_back() 또는 emplace()
emplac_back() 또는 emplace()함수를 사용하면 효율적인 원소 추가가 가능함
push_back() 또는 insert() 함수의 단점 중 하나는 이들 함수가 추가할 원소를 먼 저 임시로 생성한 후, 벡터 버퍼 내부 위치로 복사 또는 이동을 수행한다는 점임.
이러한 단 점은 새로운 원소가 추가될 위치에서 해당 원소를 생성하는 방식으로 최적화할 수 있으며, 이러한 기능이 emplace_back() 또는 emplace() 함수에 구현되어 있음.
그러므로 push_back() 또는 insert() 같은 일반적인 삽입 함수 대신 emplace_back() 또는 emplace() 함수를 사용하는 것이 성능향상에 도움이 될 수 있음.
이 경우 새 원소 위치에서 곧바로 객체가 생성되기 때문에 이들 함수인자에 생성된 객체를 전달하는 것이 아니라 생성자에 필요한 매개변수를 전달해야 함. 그러면 emplace_back() 또는 emplace() 함수가 전달된 생성자 인자를 적절하게 사용하여 객체를 생성하고 삽입함.
그러나, 자주 쓰이는 함수 같지는 않고, MS측에서 호환성이 떨어진다는??식의 답변을 해서 개인적으로만 사용하는게 좋을 것 같음.
또한 push_back또 최적화되는 방식에 따라서 emplace_back()과 큰 차이가 없이 동일한 로직으로 돌아갈 수도 있음.
원소 제거를 위한 pop_back(), erase()
pop_back() 함수는 벡터에서 맨 마지막 원소를 제거하며, 그 결과 벡터 크기는 1만큼 줄어듬.
erase() 함수는 두 가지 형태로 오버로딩 되어있음.
한 가지 형태는 반복자 하나를 인자로 받아 해당 위치 원소를 제거하고, 다른 형태는 범위의 시작과 끝을 나타내는 반복자를 받아 시작부터 끝 바로 앞 원소 까지 제거함. 즉, 시작 위치 원소는 제거되지만 끝 위치 원소는 제거되지 않음.
C++표준에서는 이들 함수 동작 시 벡터의 용량이 감소할 필요가 없지만, 컴파일러마다 달라질 수 있다고 함.
(저장된 원소의 갯수는 줄지만 실제 해당 벡터가 차지하는 용량을 의미)
pop_back()은 맨 뒤만 건드리기때문에 빠르고, 시간복잡도는 O(1)임.
그러나 erase()는 특정 위치 원소를 삭제한 후, 뒤쪽의 원소들을 모두 앞으로 이동해야 하기 때문에 O(n)의 시간이 소요됨.
std::vector<int> vec = {0, 1, 2, 3, 4, 5, 6, 7, 8,9};
// 맨 마지막 원소 하나를 제거합니다: {0, 1, 2, 3, 4, 5, 6, 7, 8}
vec.pop_back();
//맨처음원소를제거합니다: {1,2,3,4,5,6,7,8}
vec.erase(vec.begin());
// 1번째 원소부터 4번째 앞 원소까지 제거합니다: {1, 5, 6, 7, 8}
vec.erase(vec.begin() + 1, vec.begin() + 4);
유용한 std::vector 멤버 함수
clear(): 모든 원소를 제거하여 완전히 비어 있는 벡터로 만들음shrink_to_fit(): 여분의 메모리 공간을 해제하는 용도로 사용됨. 이 함수를 호출하면 벡터의 용량이 벡터 크기와 같게 설정됨. 벡터 크기가 더 이상 변경되지 않을 때 사용하면 유용reserve(capacity): 벡터에서 사용할 용량을 지정함. 매개변수로 지정한 값이 현재 용량보다 크면 메모리를 매개변수만큼 재할당함. 매개변수 값이 현재 용량보다 같거나 작으면 아무런 동작을 하지 않음. 이 함수는 벡터의 크기를 변경하지 않음.resize(count): count만큼 배열의 원소 갯수를 조정함. reserve와 비슷해 보이지만, resize는 v.size()>count 일 경우 원소의 갯수를 줄이고 v.size<count일 경우 value가 없으면 value_type의 기본 생성자를 호출해 size가 count가 될때까지 늘림.
reserve()와 resize()의 차이는 아래 코드로 확인 가능.
vector<int> v1, v2;
v1.reserve(10000);
v2.resize(10000);
cout << "v1.size(): " << v1.size() << '\n';
cout << "v1.capacity(): " << v1.capacity() << '\n';
cout << "v2.size(): " << v2.size() << '\n';
cout << "v2.capacity(): " << v2.capacity() << '\n';
//////////////////////////////////////////////////////////
결과:
v1.size() : 0
v1.capacity() : 10000
v2.size() : 10000
v2.capacity() : 10000
벡터 복사 copy()
vector<int> v1={1,2,3};
vector<int> v2(v1.size()); //반드시 복사할 벡터크기 이상이어야함
std::copy(v1.begin(),v1.end(),v2.begin());
// v2속 원소는 1,2,3으로 v1과 같게됨
벡터 이어붙이기 insert()
vector<int> v1 { 1,2,3 };
vector<int> v2 { 4,5,6 };
// 1 2 3 4 5 6
vector<int>::iterator it = v1.insert(v1.end(), v2.begin(), v2.end());
cout<<*it; //4출력됨
insert()함수는 삽입할 위치를 나타내는 반복자를 첫 번째 인자로 받음으로써 원하는 위치에 원소를 추가함.
return값은 추가를 시작 한 곳의 위치를 나타내는 반복자임.
즉 위 예시같이 cout«*it를하면 4가 출력됨.
vec.insert(vec.begin(), 0); // 맨 앞에 0 추가: {0, 1, 2}
이런식으로 특정 값을 앞에도 붙일 수 있음.
std::vector는 템플릿 매개변수에서 데이터 타입 다음에 할당자(allocator)를 전달할 수 있습니다.
사용자 정의 할당자를 사용하려면 정해진 인터페이스를 따라야합니다.
벡터는 메모리 접근과 관련된 대부분의 동작에서 할당자 함수를 사용하므로 할당자는
allocate(),deallocate(),construct(),destroy()등의 함수를 제공해야함.
댓글남기기