Container(컨테이너)란?
- container: 데이터의 저장 및 관리를 위한 클래스
1. Container 분류
1.1. Sequance Container(순차 컨테이너)
- 임의의 위치에 삽입, 삭제
- 데이터를 순차적으로 저장
- 일반적인 자료구조와 동일한 형태
- 자료 양이 적고 검색 속도가 중요하지 않을 때 사용
- ex. vector, list, deque
1.2. 연관 컨테이너
- 일정 규칙에 따라 자료를 조직화하여 저장
- 자료를 정렬/해시 등을 이용해 저장하기 때문에 검색에 유리
- ex. set, map, multiset, multimap
1.3. 어뎁터 컨테이너
- 데이터를 미리 정해진 방식에 따라 관리
- 순차 컨테이너를 변형시켜 저장
- ex. stack(LIFO), queue(FIFO)
2. 컨테이너 종류
2.1. Vector
- 동적으로 원소 추가 가능
- 속도 측면에서 배열에 비해 떨어짐
- 하지만 메모리를 효율적으로 관리 가능
- 배열과 마찬가지로 하나의 메모리 블록에 연속하게 저장 됨
- 따라서 원소가 추가되거나 삽입될 때 메모리 재할당이 발생할 수 있어 상당한 부하가 발생
1) 구조
- vector를 생성하면 메모리 heap에 생성되며 동적할당 됨
- front(): 첫 번째 원소
- back(): 마지막 원소
- begin(): 첫번째 위치
- end(): 마지막의 다음 위치
- size(): 원소의 개수
- capacity(): 할당된 공간의 크기
2) 사용법
- Vector 선언
vector<int> v; //int 타입 백터 생성
vector<int> v = { 1,2,3 }; //생성 후 초기화
vector<int> v[10]; //int타입 백터 배열 생성
vector<int> v[] = { {1,2},{3,4} }; //int형 백터 배열 생성(행은 가변이지만 열은 고정)
vector<vector<int>> v; //2차원 백터 생성(행과 열 모두 가변)
vector<int> v(5); //5개의 원소를 0으로 초기화
vector<int> v(5, 3); //5개의 원소를 3으로 초기화
vector<int> v2(v); //벡터 v를 복사하여 벡터 v2 생성-
원소 삽입
v.push_back(10); //맨 뒤에 추가 vector<int>::iterator it = v.begin(); it = v.insert(it, 2); //중간에 삽입- push_back(원소): vector 제일 끝에 원소 추가
- insert(위치, 원소): 해당 위치에 원소 삽입
- 참고
#include <iostream> #include <vector> using namespace std; int main(void) { vector<int> v; v.push_back(10); vector<int>::iterator it = v.begin(); it = v.insert(it, 2); it = v.begin(); while (it != v.end()) { cout << *it << endl; it++; } return 0; }
-
원소 삭제
v.pop_back(); //맨 뒤 원소 삭제 v.erase(v.begin() + 1); //위치 원소 삭제 v.clear(); //모든 원소 삭제- 참고
#include <iostream> #include <vector> using namespace std; int main(void) { vector<int> v; cout << "삽입" << endl; v.push_back(10); vector<int>::iterator it = v.begin(); it = v.insert(it, 2); it = v.insert(it, 3); it = v.insert(it, 4); it = v.begin(); while (it != v.end()) { cout << *it << endl; it++; } cout << "삭제" << endl; v.pop_back(); v.erase(v.begin() + 1); it = v.begin(); while (it != v.end()) { cout << *it << endl; it++; } cout << "전체 제거" << endl; v.clear(); it = v.begin(); while (it != v.end()) { cout << *it << endl; it++; } return 0; }
-
Vector 크기 구하기
v.size(); //vector의 원소 갯수
v.capacity; //vector의 물리적 크기2.2. string
- 문자열을 다루는 클래스
- char*, char[]과 다르게 문자열의 끝에 '\0'문자가 들어가지 않으며, 문자열의 길이를 동적으로 변경 가능
1) 입출력
- cin, cout
cin>>str;: 공백 이전 까지의 문자열을 입력받음
cout<<str;: 문자열 출력 - getline
getline(cin, str);: '\n'이전까지의 문자열을 입력받음(공백 포함)
getline(cin, str, 'a'): 'a'문자 이전까지의 문자열을 입력받음
2) string class 생성
string str; : 빈 문자열 str 생성
string str = "abcdef" : "abcdef"로 선언된 str 생성
string str("abcdef") : "abcdef"로 선언된 str 생성
string str2(str1) : str1 문자열을 복사한 str2 생성
char s[ ] = {'a', 'b', 'c', 'd', 'e', 'f'}; string str(s) : c의 문자열과 호환
string *str = new string("abcdef") : new를 이용한 동적할당
3) string 클래스 연산자 활용
- 문자열 비교(<,>,==): 두 문자열의 사전 순서를 비교, 또는 동일 여부를 확인
- 문자열 연결(+): 두 문자열을 이어주는 역할
str1 = str1 + str2;
4) 멤버 함수
- 원소 접근
str.at(index): index 위치와 문자 반환, 유효한 범위인지 체크str[Index]: index 위치의 문자 반환, 유요한 범위인지 체크하지 않음(속도 빠름)str.front(): 문자열의 가장 앞 문자 반환str.back(): 문자열의 가장 뒤 문자 반환
- string 크기
str.lenght(),str.size(): 문자열 길이 반환str.capacity(): 문자열이 사용중인 메모리 크기 반환str.resize(n): stirng을 n의 크기로 만듦str.empty(): str이 빈 문자열인지 확인
- string 삽입, 추가, 삭제
str.append(str2): str 뒤에 str2 문자열을 이어 붙여줌('+'와 같음)str.append(str2, n, m): str 뒤에 'str2의 n index부터 m개의 문자'를 이어 붙여줌str.append(n, 'a'): str 뒤에 n개의 'a'를 이어 붙여줌str.insert(n, str2): n번째 index 앞에 str2 문자열을 삽입str.replace(n, k, str2): n번째 index부터 k개의 문자를 str2로 대체함str.clear(): 저장된 문자열을 모두 지움str.erase(n, m): n번째 index부터 m개의 문자를 지움str.push_back(c): str의 맨 뒤에 c 문자를 붙여줌str.pop_back(): str의 맨 뒤의 문자를 제거str.assign(str2): str에 str2 문자열을 할당
- 유용한 함수
str.find("abcd"): "abcd"가 str에 포함되어있는지를 확인. 찾으면 해당 부분의 첫번째 index를 반환str.find("abcd", n): n번째 index부터 "abcd"를 findstr.substr(): str 전체를 반환str.substr(n, k): str의 n번째 index부터 k개의 문자를 부분문자열로 반환str.compare(str2): str과 str2가 같은지를 비교. 같다면 0, str<str2 인 경우 음수, str>str2 인 경우 양수를 반환swap(str1, str2): str1과 str2를 바꿔줌. reference를 교환하는 방식isdigit(c): c 문자가 숫자이면 true, 아니면 false를 반환isalpha(c): c 문자가 영어이면 true, 아니면 false를 반환toupper(c): c 문자를 대문자로 변환tolower(c): c 문자를 소문자로 변환
2.3. map
- 각 노드가 key(first)와 value(second)쌍으로 이루어진 트리
- 중복을 허용하지 않음
- C++의 내부구현은 검색, 삽입, 삭제가 O(logn)인 레드블랙트리로 구성
- key를 기준으로 오름차순 정렬
1) 삽입, 삭제
map<string, int> m;
m.insert({"Cam",300});
m.erase(m.begin()+2); //위치를 사용해 삭제
m.erase("Cam"); //key값을 사용해 삭제
m.erase(m.begin(), m.end()); //전체 범위 삭제
m.clear();2) 데이터 찾기
- iterator를 사용
- 못찾았을 경우 iterator는 end()를 반환
map<string, int> m;
if(m.find("Cam") !-m.end())
{
cout<<"find"<<endl;
}
else
{
cout<<"not find"<<endl;
}3) 데이터 접근
for(auto iter = m.begin(); iter != m.end(); iter++)
{
cout<<iter->first<<" "<<iter->second<<endl;
}2.4. unorderd_map
- map보다 더 빠른 탐색을 위한 자료구조
- 해쉬 테이블로 구현한 자료구조로 시간복잡도가 O(1)
- key가 유사한 데이터가 많을 시 해시충돌로 인한 성능감소가 있을 수 있음
- 사용방법은 map과 유사
1) 데이터 접근
- map과 마찬가지로 index로 접근이 불가
for(pair<string, int> elem : um)
{
cout<< "key: "<<elem.first<<"value : "<<endl;
}2.5. queue
- FIFO구조
1) 데이터 추가: queue.push(element)
2) 데이터 삭제: queue.pop()
3) 첫번째 데이터 반환: queue.front()
4) 마지막 데이터 반환: queue.back()
5) 사이즈 반환: queue.size()
6) 비어있는지 확인: queue.empty()
2.6. stack
- FILO구조
1) 데이터 추가: stack.push(element)
2) 데이터 삭제: stack.pop()
3) 첫번째 데이터 반환: stack.top()
4) 사이즈 반환: queue.size()
5) 비어있는지 확인: queue.empty()
그냥 하자