백준 문제풀이 하면서 STL을 다양하게 사용해보고 있는데 헷갈려서 정리한다
목차
vector 의 특징
vector 는 동적 배열 구조로 여러 가지 자료형으로 정의하여 사용 할 수 있다.
vector 는 데이터를 선형적으로 만들려고 하며 저장 공간을 초과하는 데이터를 추가 하는 경우 현재 보유하고 있는
메모리의 두 배 만큼을 할당. (메모리의 사용량이 증가하고 속도가 느려질수있음)
또한 배열의 크기가 빈번하게 변경될때도 성능이 저하될수 있다.
vector 의 검색 시 시간 복잡도는 O(n) 으로, 검색이 빈번한 경우 성능을 고려하면 map등 다른 자료구조가 효율적이
vector 기본 사용법
생성
고정 길이로 선언할시 미리 뒤에 vector 의 크기를 정의한다.
// 고정 크기
// 변수도 사용 가능
vector<int> vec(n);// 가변 크기
vector<int> vec;
선언 시 초기화
// 배열의 개수, 초기 값
vector<int> vec(10,0);* int 의 경우 기본적으로 0으로 초기화되어 있다.
요소 초기화
vec.clear()
삽입
push_back()으로 삽입
vec.push_back(it.first);
삭제
erase() 로 삭제
인덱스 기준으로 삭제와 값 기준으로 삭제 다 가능
// 인덱스 기준
vec.erase(vec.begin() + idx);
정렬
오름차순, 내림차순 정렬
// 오름차순(기본)
sort(freqno.begin(), freqno.end());
// 내림차순
sort(freqno.begin(), freqno.end(), greater<int>());사용자 정의 정렬(compare 함수 사용)
bool compare(Users user1, Users user2)
{
// 나이를 기준으로 오름차순 정렬
if (user1.age != user2.age)
{
return user1.age < user2.age;
}
// 나이가 같다면 들어온 순서(number)를 기준으로 정렬
return user1.number < user2.number;
}sort(user.begin(), user.end(), compare);
특정 원소의 개수
// vector 안에서 3의 개수를 구함
count(vec.begin(), vec.end(), 3)* 시간복잡도는 그냥 반복문으로 구하는거랑 똑같음
vector의 요소의 개수 출력
vec.size();