[c++][자료구조] Vector / List 비교 및 STL 정리

Vector

 

◎ 동적 배열(dynamic array) 구조

◎ Iterator & Index 접근이 가능 (개별 원소에 접근 가능)

◎ 접근 속도가 빠름

 

● 삽입/삭제가 느림 (배열 기반)

 

List

◎ Double Linked List(더블 링크드 리스트) 구조

◎ Iterator를 이용한 접근

◎ 삽입 / 삭제가 빠름

 

● 접근 속도가 느리다.

● 개별 원소에 접근 불가능

 

 

어떤 경우에 어떤 container를 사용해야 할까?

 

삽입 , 삭제가 빈번할 경우 -> List

개별 원소에 접근을 자주 해야할 경우 -> vector

 

 

Vector STL

 

헤더파일

#include <vector>

 

 

선언

 

    vector<int> v1 ;

    vector<int> v2 = {4,3,2};

    vector<int> v3(4,3); // v3 = {3, 3, 3, 3}

    vector<int> v4(v3); // v3 복사

 

 

cout << (v2 > v3) << endl; // True(1) 출력 . //v2의 첫 번째 원소 값 : 4 , v3의 첫 번째 원소 값 : 3 이여서

 

 

함수

 

 

v.assign(int a , int b)      : 값 할당 (b를 a개 할당)

vector<int> v;
vector<int> v2 ={3, 3, 3, 3};

v.assign(3,4); // v = {4, 4, 4}
v2.assign(3,4); // v2 = {3, 3, 3, 3} -> v2 = {4 , 4 , 4}

 

 

v.at(int index)      /     v[index] :  index 이용한 값 참조

vector<int> v = {4 ,4 , 4};

v[0] = 1; // v = {1, 4, 4}; // index가 범위를 벗어나면 에러.
v.at(1) = 3 // v = {1, 3 , 4}; // index가 범위를 벗어나면 예외를 던짐.

 

 

v.front()     /     v.back()         : 값 참조 (맨앞 / 맨 뒤)

vector<int> v = { 4, 4, 4}

v1.front() = 5;

cout << v1.front() << endl; // 5
cout << v1.end() << endl; // 4

 

 

v.size()      /       v.capacity()       : 값 갯수 , 공간 크기 

vector<int> v = { 1, 2 , 3}

cout << v.size() << v.capacity() << endl;  // 출력 : 3 3

vector<int> v1 = {1 ,2 , 3, 4}

cout << v1.size() << v1.capacity() << endl; // 출력 : 4 6

동적 배열이라 꽉차면 자동으로 늘어난다.

size : 늘어 날 때마다 1 씩 증가

capacity : 1씩 늘어 나지 않고 꽉차면 기존 메모리 *2로 늘어난다.

 

 

 

v.push_back(int data)   /    v.pop_back()       :     맨 뒤에 값 삽입 , 맨 뒤에 값 삭제

vector<int> v = { 1 , 2 , 3 , 4};

v.push_back(3); // v= {1 , 2, 3 , 4 , 3}

v.pop_back(); // v = {1, 2, 3 ,4}

 

 

v.swap(v2) :  v와 v2의 원소와 capacity를 바꿈.

vector<int> v1 = { 1 , 2, 3};
vector<int> v2 = {5};

v1.swap(v2);

// v1 = { 5 } , v2 = {1 , 2 , 3}

 

 

v.empty()    :  비어있으면 true, 아니면 false return

if(!v.empty()){
	cout << "no empty" ;
}
else{
	cout << "empty" ;
}

 

v.clear()

vector<int> v = {1 , 2 , 3 , 4};
v.clear(); //v = {};

size만 줄어든다. capacity는 그대로 유지

 

 

vector iterator

 

선언

vector<int> iterator:: iter;

 

 

iterator 할당 및 이동

vector<int> v = {1 , 2 , 3 , 4};
vector<int>:: iterator iter;

//iter 할당 및 이동.
iter = v.begin(); //v의 1을 가리킴

iter++; //v의 2를 가리킴.

iter += 2; //v의 4를 가리킴.

 

 

iterator 값 참조 / index 참조

vector<int> v = {1 , 2 , 3 , 4};
vector<int> :: iterator iter;
iter = v.begin() + 1;

// iter이 가리키는 원소의 값 반환
cout << *iter << endl; // 출력 : 2
cout << iter[1] << endl; // 출력 : 3
cout << iter[-1] << endl; // 출력 : 1

// iter이 가리키고 있는 index 반환
cout << iter -v.begin() << endl ; // 출력 : 1

 

 

iterator을 이용한 함수

 

 

v.begin()    /    v.end()       :    v의 (첫 번째 원소)/(마지막 원소 다음)을 가리키는 iterator 반환

 

사용법1 : sort

vector<int> v = {3,  2 , 1 , 4};

sort(v.begin() , v.end());

for(auto x : v)
	cout << x << ' '; // 출력 : 1 2 3 4

사용법2 : 출력

vector<int> v = {1 , 2 , 3 , 4};
vector<int>::iterator iter;

for(iter = v.begin() ; iter != v.end() ; iter++)
	cout << *iter << ' '; // 출력 : 1 2 3 4

 

 

 

v.rbegin() / v.rend() :        거꾸로 해서 (첫 번째 원소)/ (마지막 원소 다음)을 가리키는 iterator 반환

 

사용법 1 : 역방향 sort

vector<int> v = {1, 2, 3, 4}

sort(v.rbegin() ,v.rend()); // v = {4 ,3, 2, 1}
for(auto x : v)
	cout << x << ' '; // 출력 : 4 3 2 1

 

사용법 2 : 역방향 출력

vector<int> v = {1, 2, 3, 4};
vector<int>:: reverse_iterator it;

for(it = v.rbegin() ; it != v.rend() ; it++)
	cout << *it << ' '; // 출력 : 4 3 2 1

◎ rbegin과 rend 함수는 reverse_iterator와 함께 써야 함.

◎ reverse_iterator 에 +1 을 하면 반대 방향으로 진행한다.

 

 

 

v. insert( iterator , int b)           :              a 위치에 b를 삽입.

vector<int> v = {1 , 2 , 3};
v.insert(v.begin() + 1 , 3); v = {1 , 3 , 2 , 3}

 

 

v.erase( iterator )

 

vector<int> v = { 1 , 2 , 3 , 4};

v.erase(v.begin() + 2); // index 2 인 data 3 삭제

 

 

 

List STL

 

vector stl과 유사하다.

 

 

헤더파일

#include <list>

 

 

선언

    list<int> li(3,4); // li = {4 , 4 , 4}    (갯수 , 값)으로 할당.
    list<int> li2(5); // li2 = { 0 , 0 , 0 , 0 , 0 }     (갯수) 만큼 0값으로 할당.
    list<int> li3 = { 1, 2, 3, 4 };   // li3 = { 1 , 2 , 3, 4}
    list<int> li4(li3); // li4 = { 1 , 2 , 3  , 4 }

 

 

함수

 

list<int> li 를 기준으로 설명 하겠다.

 

 

값 할당

li.assign( 갯수 , 값 )

	list<int> li5;

	li5.assign(3,4); // li5 = { 4, 4, 4 }

 

 

값 반환

li.front()  / li.back()     

list<int> li = {1, 2, 3, 4, 5}

cout << list.front() << ' ' << list.back() << endl; // 출력 : 1 5

front : 맨 앞 값 반환      /       back : 맨 뒤 값 반환

 

 

값 삽입 / 삭제

li.push_back( int data )    /    li.push_front( int data )       /       li.pop_back()        /       li.pop front()

list<int> li = {2 , 3, 4};

li.push_front(1); //li = {1, 2, 3, 4}  // 맨 앞 삽입
li.push_back(5); // li = {1, 2, 3, 4, 5} // 맨 뒤 삽입

li.pop_front();  //li = {2, 3, 4, 5} //맨 앞 삭제
li.pop_back();   //li = {2, 3, 4} //맨 뒤 삭제

 

 

li.sort()

list<int> li = {2 , 1 , 3 , 4};

li.sort(); // li = {1 , 2 , 3 , 4};

li.sort(greater<>()); // li = {4 , 3, 2 , 1};

greater<>() 를 쓰면 내림차순 정렬.

 

 

li.remove(int a)

list<int> li = { 1 , 2 , 3 , 3 , 4};

li.remove(3); // li에 모든 3 값 제거.

for(auto x : li)
	cout << x << ' '; // 출력 1 2 4

li.reverse()

list<int> li = {1 , 2 , 3 , 4};

    li.reverse();

    for(auto x : li) cout << x << ' '; // 4 3 2 1

 

li.size()

list<int> li = {1 ,2 , 3, 4};

cout << li.size() ; // 4

 

li.swap( li2 )

list<int> li = { 1 ,2 ,3 ,4};
list<int> li2 = { 5 , 6, 7};

li.swap(li2); // li = {5 , 6, 7} , li2 = { 1 , 2 , 3 , 4}

 

li.splice( iter ,li2) :  li의 iterator인 iter가 가리키는 곳에 li2의 원소를 제거하고 제거한 원소들을 집어넣음.

	list<int> li = { 1 ,2 ,3 ,4}; 
  	list<int> li2 = { 5 , 6, 7 , 8};

  	list<int>::iterator iter2 = li2.begin();
  	
    //advance(iter2,2); // iter2을 +2 만큼 해줌 -> 원소 7 가리킴.
  	
    
    li.splice(li.end() , li2); // li.end() 에 li2 원소 다 집어넣기.
    // li.splice(li.end() , li2 , iter2); // li.end()에 li2의 iter2가 가리키는 원소 집어넣기.
    
    //li.splice(li.end(),li2, iter2, li2.end()); // li.end()에 li2의 ier2가 가리키는 곳 부터 li2.end() 까지 집어넣기.

 

li.unique() : 중복 원소 제거(sort 필요)

list<int> li = { 1, 2, 3 ,4 ,4 ,5};

li.unique(); // li = { 1, 2, 3, 4, 5}

 

iterator 선언 및 사용

list<int> li = {1, 2, 3, 4};

list<int>::iterator it; //선언
it = li.begin(); // 첫 번째 값 1을 가리킴.

it++ ; // 다음 값 2를 가리킴.

cout << *it << endl; // 참조 값 반환 출력 : 2


//vector는 가능하지만 list는 불가능 한 방법들 (index 관련)
// cout << it - li.begin(); // 에러 - 인덱스 반환 불가
// cout << *(it+1) // 에러 - 연산 사용 불가.
// cout << *(++it) // 가능

 

li.begin()        /           li.end()          /           li.rbegin()        /          li.rend()

list<int> li = {1 , 2 , 3 , 4};
list<int> :: iterator iter;

for(iter = li.begin() ; iter != li.end() ; iter++){
	cout << *iter << ' '; // 출력 1 2 3 4
}

list<int> :: reverse_iterator iter_r;

for(iter_r = li.rbegin() ; iter_r != li.rend() ; iter++){
	cout << *iter << ' ' ; // 출력 4 3 2 1
}

vector와 동일

 

 

li.insert ( iterator , int data ) / li.erase (iterator)

list<int> li = {1, 2, 3, 4, 5};

list<int> :: iterator it = li.begin();
it++; // 2를 가리키고 있다.

li.insert( it , 6 ); // li = {1 , 6 , 2, 3, 4, 5} it는 여전히 2를 가리키고 있음.
li.erase(it) ; // ii = {1, 6, 3, 4, 5}

insert : iterator가 가리키는 값 바로 앞에 data를 삽입.

erase : iterator가 가리키는 값 삭제.