C++ #11
이중 연결 리스트
단순 연결 리스트
- 자신의 다음 노드에 대한 링크만을 가지기 때문에 뒤쪽으로만 이동할 수 있으며 앞쪽으로는 이동할 수 없다.
- 링크 조작 시 양쪽 노드의 링크를 액세스 할 수 없기 때문에 항상 지정한 노드의 오른쪽에만 삽입할 수 있다.
이중 연결 리스트
- 전후 노드에 대한 링크를 각각 따로 갖는다.
struct Node
{
int value;
Node* prev;
Node* next;
}- 노드의 데이터 이외 앞쪽 노드의 버지를 가지는 prev, 뒤쪽 노드의 번지를 가지는 next 링크가 포함되어 있다.
노드의 삽입
-
새로운 노드가 생성되었으므로 링크 조정을 해야 한다.
-
New의 다음 노드는 Right가 되고 이전 노드는 Target이 된다.
셋(set)
셋(set)이란
- set이란 사전적 의미로 '집합'이라는 뜻인데, 동일한 타입의 데이터를 모아놓은 것이다.
- 데이터는 정렬된 위치에 삽입되므로 검색 속도가 빠르고, 키가 중복되지 않는다.
셋(set)의 사용형태
- 셋의 형식으로 타입이 T형인 셋의 객체를 선언한 형태이다.
set<T> st;- 일반 컨테이너와 사용 형태는 동일하다.
#include<iostream>
#include <set>
void main()
{
int arr[] = { 1,2,3,2,6,5,3 };
set<int> scon;
set<int>::iterator it;
for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
{
scon.insert(arr[i]);
}
for (it = scon.begin(); it != scon.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}출력결과
1 2 3 5 6
#include<iostream>
#include <set>
void main()
{
const char* strtmp = "rhrlajrrhtlvek";
set<char> scon(&strtmp[0], &strtmp[15]);
set<char>::iterator it;
for (it = scon.begin(); it != scon.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}출력결과
a e h j k l r t v
맵(map)
맵(map)이란
- 맵은 두 개의 데이터가 하나의 쌍을 이루어 저장하는 컨테이너로 정렬된 상태로 관리되고, 검색 속도가 빠르다.
- 대용량의 데이터를 검색할 경우 유리하고, 데이터 삽입, 삭제 시 데이터의 이동이 발생하므로 상대적으로 느리다.
맵(map)의 사용형태
- 맵의 형식으로 타입이 T형인 맵의 객체를 선언한 형태이다.
map<key, data> mp;- 맵의 첫 번째 전달인자 key에는 숫자, 문자 타입 상관 없이 들어올 수 있다.
- 맵의 두 번째 전달인자 data는 key를 통해 가져올 데이터를 의미하는데, 또한 숫자, 문자 타입 상관 없이 들어올 수 있다.
Map<string, int> person;
Person'["김모모"] = 43;
Person'["이마마"] = 10;- 이름이라는 키값에 나이라는 데이터를 넣은 형태이다.
#include<iostream>
#include<map>
#include<string>
void main()
{
map <string, int> person;
map <string, int>::iterator it;
string name;
person["김모모"] = 30; // {'김모모' : 30} key-value 형태
person["이모모"] = 25;
person["박모모"] = 20;
while (true)
{
cout << "이름 입력 : ";
cin >> name;
if (name == "q")
break;
it = person.find(name);
if (it == person.end()) // 찾지 못했다는 의미
{
cout << "그런 사람은 없습니다." << endl;
}
else
{
cout << it->first << " , " << it->second << endl;
}
}
}출력결과
이름 입력 : (김모모)
김모모 , 30
이름 입력 : (박씨)
그런 사람은 없습니다.
이름 입력 : (q)
컨테이너 : 벡터, 데크, 리스트, 셋, 맵
서로 다른 자료구조
사용 문법 동일, 비슷
원활한 협업, 일반화 프로그래밍
반복자(Iterator)
반복자의 개념
- 모든 반복자는 컨테이너의 구간에 대해 값을 읽어올 수 있도록 기능을 제공한다.
- 모든 컨테이너에 대해서 동일하게 동작하여 값을 얻어올 수 있게 한다.
반복자의 범위
- 반복자는 포인터와 흡사하다.
- 예를 들어 정수 배열을 가리키는 포인터일 경우 ++연산을 하게 되면 그 다음번 주소의 정수값을 읽을 수 있듯이 반복자 또한 ++ 연산을 적용할 수 있다.
- 포인터는 그 다음 주소값을 읽어오지만 반복자는 다음번 요소를 읽어온다.
#include<iostream>
#include<vector>
void main()
{
int arr[] = { 1,2,3,4,5 };
vector<int> vi(&arr[0], &arr[5]);
vector<int>::iterator it;
for (it = vi.begin(); it != vi.end(); it++)
{
cout << *it << endl;
}
}
알고 쓰자!