[C++ STL] 벡터(vector), 리스트(list)

vector (벡터)

• 배열처럼 연속적인 메모리를 사용하지만, 크기가 자동으로 조절되는 동적 배열이다.

데이터 추가 시 공간이 부족하면 크기를 자동으로 늘린다.

연속적인 메모리 구조이기 때문에 인덱스를 사용한 접근이 빠르다.

vector 장단점

장점	단점
• 인덱스로 데이터에 빠르게 접근할 수 있다. ➜ O(1) • 크기가 자동으로 조절되므로 수동으로 메모리를 관리할 필요가 없다. • push_back()로 데이터를 쉽게 추가할 수 있다.	• 중간에서 데이터를 삽입하거나 삭제할 때는 느리다. ➜ O(n) • 크기를 늘릴 때 새로운 메모리를 할당하고 데이터를 복사하는 오버헤드가 발생한다.

vector 헤더 파일

#include <vector>

vector 기본 형식

std::vector<자료형> 변수명;

vector 선언

using std::vector;
vector<int> v;

vector 멤버 함수

분류	멤버 함수	설명
Iterator (반복자)	begin	• 첫 번째 요소를 가리키는 iterator 반환
	end	• 마지막 요소의 다음을 가리키는 iterator 반환 • end()는 vector, list 상관없이 모든 컨테이너에서 동일하다.
	rbegin	• 맨 뒤 요소를 가리키는 iterator 반환
	rend	• 맨 앞의 요소를 가리키는 iterator 반환
Const Iterator (상수 반복자)	cbegin	• 첫 번째 요소를 가리키는 상수 iterator 반환
	cend	• 마지막 요소를 가리키는 상수 iterator 반환
	crbegin	• 맨 뒤의 요소를 가리키는 상수 iterator 반환
	crend	• 맨 앞의 요소를 가리키는 상수 iterator 반환
Addition (추가)	push_back()	• vector 맨 뒤에 요소 추가
	emplace_back()	• vector 맨 뒤에 요소 추가
Insertion (삽입)	insert()	• iterator가 가리키는 위치 앞에 요소 추가
	emplace()	• 생성자를 직접 호출하여 vector의 지정된 위치에 요소 생성 생성자 인수를 전달하면 해당 인수들로 새 요소가 들어갈 곳에 바로 요소를 생성한다. 이는 복사 후 새 컨테이너에 넣는 메모리 낭비를 막아준다. • C++11에서 새로 추가된 함수
Deletion (삭제)	pop_back()	• vector 맨 뒤 요소 삭제
	erase()	• iterator가 가리키는 위치의 요소 삭제
	clear()	• vector의 모든 요소 삭제
Access (접근)	size()	• vector의 요소 수 반환
	capacity()	• 현재 용량(할당된 메모리 크기)을 반환
	empty()	• vector가 비어 있으면(size가 0이면) true, 비어있지 않으면 false 반환
	front()	• vector의 첫 번째 요소에 대한 참조 반환
	back()	• vector의 마지막 요소에 대한 참조 반환
	at()	• index 위치의 데이터를 참조하며, operator[]보다 느리지만 범위 초과를 방지하는 점검을 거친다.
	operator[]	• 지정된 index 위치를 참조하며, 범위 점검을 하지 않아 at보다 빠르다.
Modification (수정)	resize()	• vector의 크기를 지정된 요소 수로 조정한다.
	shrink_to_fit()	• 크기에 맞게 vector의 용량을 줄인다.
	swap()	• 두 vector의 내용을 swap한다.(바꾼다.)

 

▷ 예시

#include <vector>
#include <iostream>

using std::vector;
using std::cout;
using std::endl;

int main() {
	vector<int> vecInt;

	// 데이터 추가
	vecInt.push_back(10);
	vecInt.push_back(20);
	vecInt.push_back(30);
	//vecInt.push_front(30);  // 오류 => 애초에 벡터는 push_front를 제공해주지 않는다.
	// push_front 기능을 사용할거면 리스트를 사용하는게 더 효율적이기 때문이다.

	cout << "인덱스로 접근하여 출력" << endl;
	for (int i = 0; i < vecInt.size(); i++) {
		cout << vecInt[i] << endl;  // 인덱스로 접근
	}

	// 배열 버전 (마치 배열처럼 연산자를 사용하여 접근)
	vecInt[0] = 100;  // 0번째 인덱스 값 100 대입
	// 함수 버전
	// 특정 인덱스로 접근해서 값을 래퍼런스 반환해준다.
	vecInt.at(1);  // vecInt[1];와 같다.

	// 가변 배열에 데이터를 넣으면 객체 안이 아니라 힙 메모리를 가리키고 그곳에 데이터를 저장한다.
	// 첫 번째 주소(멤버로 치면(CArr.h) m_pData) 즉, 시작 주소를 반환해주는 함수
	vecInt.data();

	// 가변 배열 안의 데이터 개수
		// 실제 유효한 요소(element)의 개수
	vecInt.size();

	// 현재 기준으로 몇 칸까지가 허용 범위인지
		// 벡터가 메모리에 할당된 크기
		// 벡터의 요소들을 담을 수 있는 메모리가 할당되어있는 공간의 용량
	vecInt.capacity();
	cout << "at으로 i번째 데이터 출력" << endl;
	for (size_t i = 0; i < vecInt.size(); ++i)  // 벡터에 넣어놓은 데이터 개수만큼 반복된다.
	// typedef unsigned __int64 size_t;
		// __int 64는 8byte라서 long long과 똑같다.
		// size_t는 8byte 정수 자료형 (long long)으로 typedef(type define) 즉, 이름 재정의 했을 뿐이다.
		// size_t를 사용한 이유 : 벡터의 반환타입이 size_t라서 맞춰주려고
	{
		// i번째 데이터 출력
		cout << vecInt.at(i) << endl;  // vecInt.at(i)를 vecInt[i]로 표현해도 된다.
	}
    
	// 구현되어있는 클래스가 마치 네임스페이스처럼 iterator를 지칭하는데, 벡터에 있는 iterator와 리스트에 있는 iterator는 엄연히 다른 클래스이다.
	vector<int>::iterator veciter = vecInt.begin();  // vector<int>라는 클래스 안에 구현되어있는 iterator
	*veciter = 100;  // vecInt[0];과 같다. (벡터 안에 넣어놓은 첫 번째 데이터에 접근)
	++veciter;  // 다음 데이터를 가리킨다.
	vecInt[0] = 100;

	return 0;
}

▽ 출력 결과

인덱스로 접근하여 출력
10
20
30
at으로 i번째 데이터 출력
100
20
30

---

list (리스트)

• 각 요소는 이전과 다음 요소를 가리키는 포인터를 가지는 이중 연결 리스트(doubly linked list)이다.

• 연속적인 메모리 구조가 아니다.

• 포인터만 수정하면 돼서 데이터 삽입과 삭제가 빠르다.

list 장단점

장점	단점
• 중간에서 데이터를 삽입하거나 삭제할 때 빠르다. ➜ O(1) • 메모리 크기를 미리 지정하지 않아도 된다.	• 인덱스 접근이 불가능해서 순차적으로 탐색해야 한다. ➜ O(1) • 각 요소가 추가적인 포인터를 저장하기 때문에 메모리 사용량이 많다.

list 헤더 파일

#include <list>

list 기본 형식

std::list<자료형> 변수명;

list 선언

using std::list;
list<int> l;

list 멤버 함수

분류	멤버 함수	설명
Iterator (반복자)	begin()	• list의 첫 번째 요소를 가리키는 iterator 반환
	end()	• list의 맨 마지막 요소의 다음을 가리키는 iterator 반환
	rbegin()	• 맨 뒤의 요소를 가리키는 iterator 반환 • 기본 iterator와는 달리 뒤에서부터 순차적으로 접근할 때 사용한다.
	rend()	• 맨 앞의 이전 원소를 가리키는 iterator 반환
Const Iterator (상수 반복자)	cbegin()	• 첫 번째 요소를 가리키는 상수 iterator 반환
	cend()	• 마지막 요소를 가리키는 상수 iterator 반환
	crbegin()	• 맨 뒤의 요소를 가리키는 상수 iterator 반환
	crend()	• 맨 앞의 요소를 가리키는 상수 iterator 반환
Addition (추가)	push_front()	• list 맨 앞에 요소 추가
	push_back()	• list 맨 뒤에 요소 추가
	emplace_front()	• list 맨 앞에 요소 추가
	emplace_back()	• list 맨 뒤에 요소 추가
Insertion (삽입)	insert()	• 해당 iterator가 가리키는 위치 앞에 요소 추가
	emplace()	• 해당 iterator 위치 앞에 요소 삽입 • C++11에서 새로 추가된 함수
Deletion (삭제)	pop_front()	• list 맨 앞 요소 삭제
	pop_back()	• list 맨 뒤 요소 삭제
	erase()	• iterator가 가리키는 위치의 요소 삭제
	erase(iterator a, iterator b)	• iterator a부터 b 앞까지의 범위 삭제
	remove()	• list 안에 value와 같은 값을 가지는 element를 모두 제거한다.
	remove_if(predicate)	• list 안에 해당 조건자(predicate)가 제공하는 조건을 만족하는 값 제거
	unique()	• 본인과 본인 다음에 있는 노드가 같으면 한 개만 남기고 삭제한다.
	clear()	• list의 모든 요소 삭제
Access (접근)	*iterator	• iterator가 가리키는 요소에 접근
	size()	• list의 요소 수 반환
	max_size()	• list의 최대 크기를 반환
	resize()	• list의 크기를 재설정한다. 바꾸려고 하는 크기가 list보다 작으면 뒤쪽이 잘린다.
	empty()	• list가 비어있으면 `true`, 비어있지 않으면 `false` 반환
	front()	• 첫 번째 요소의 참조 반환
	back()	• 마지막 요소의 참조 반환
Modification (수정)	reverse()	• 요소를 거꾸로 뒤집는다. • `std::list`는 `reverse()` 멤버 함수를 제공하지 않지만 `std::reverse()`는 iterator와 함께 동작하는 `<algorithm>` 라이브러리의 비멤버 함수이다.
	swap()	• lt와 lt2를 swap한다.(바꾼다.)
	splice()	• iterator를 기준으로 list를 뒤에 붙인다.
	sort()	• 모든 요소를 오름차순으로 정렬
	merge()	• list를 합병 정렬한다. `sort()`처럼 매개변수에 비교 함수를 넣어주면 원하는 조건으로 정렬이 가능하다.
	assign()

• 리스트는 배열처럼 메모리가 연속적이지 않아 인덱스로 바로 접근이 불가능하므로 `operator[]`를 제공하지 않는다.

listInt[1] = 100;  // listInt는 list의 객체이다.

2번째 넣은 데이터에 100을 넣는 것을 구현할 수는 있지만 순차적으로 목록을 탐색하기 위한 순회 비용이 많이 들어 비효율적이다.

 

+) 삭제

`remove_if(predicate)`

predicate(조건자)
• bool값(true 또는 false)을 반환하는 호출 가능한 객체(함수, lambda 또는 functor)
일반적으로 조건을 평가하거나 입력에 대한 논리적 테스트를 수행하는 데 사용된다.
`std::remove_if`, `std::find_if`, std::count_if`, std::sort` 등에 사용된다.

 

+) 수정

`reverse()`

#include <algorithm>

참고 링크
• iterator

 

▷ 예시

#include <list>
#include <iostream>

using std::list;
using std::cout;
using std::endl;

int main() {
    list<int> lst;
    list<int>::iterator it;
	
    // 데이터 추가
    lst.push_back(10);
    lst.push_back(20);
    // 앞에 데이터 추가
    lst.push_front(5);

    for (it = lst.begin(); it != lst.end(); ++it) {
        cout << *it << endl;  // 순차 접근
    }
    
    listInt.size();  // 리스트 안의 데이터 개수
	//listInt.capacity();  // 오류 => 리스트는 넣을 때마다 메모리 공간을 만들기 때문에 리스트에 capacity()는 존재하지 않는다.
    	// 리스트에 maxCount가 없는 이유도 마찬가지이다.
        
    // iter는 리스트의 첫 번째 노드를 가리킨다.
    list<int>::iterator iter = listInt.begin();  // list<int>라는 클래스 안에 구현되어있는 iterator
	// 사용자는 노드인지 뭔지 생각할 필요가 없고, 리스트가 첫 번째 데이터를 가리키고 있다는 것만 생각하면 된다.
	
    // 연산자 오버로딩 - operator*()
    // *iter는 리스트 안의 첫 번째 데이터를 받아오고 그것을 역참조하여 값을 확인한다.
	int iData = *iter;  // 10
	// iter가 마치 포인터처럼 동작하지만 iterator 클래스의 객체이다.

    return 0;
}

▽ 출력 결과

5
10
20