class iterator {
private:
CArr* vec_start; //바뀔 수도 있는 가변배열을 위해 추가
T* i_start; //자료구조상, 데이터의 시작주소
int i_index; //인덱스위처럼 CArr 포인터를 가지도록 iterator를 수정하였다.
그 이유는, 현재 사용자정의 가변배열을 만들어둔게,
배열의 크기가 다 찼는데 데이터가 들어오는 경우 resize를 하면,
새로 공간을 할당하고, 해당 주소를 매핑하므로,
T* i_start에서 생성자때 한 번 받고 그 이후로 받을 수가 없기 때문이다. 라고 봤는데
int main()
{
CArr<int> myarr;
std::cout << myarr.data() << std::endl;
CArr<int>::iterator i = myarr.begin();
for (int i = 0; i < 20; i++) {
myarr.push_back(i+1);
}
i = myarr.begin();
std::cout << myarr.data() << std::endl;
return 0;
}해당 코드를 실행했을때, i의 값은 둘이 같다.
즉, iterator.begin함수를 실행하면, 시작주소가 재할당되므로
굳이 CArr을 iterator에 추가해야하는지 모르겠다.
추가로, 굳이 기존에 구현된 iterator를 다시 만들어야할 필요성을 모르겠다.
iterator의 ++i, i++를 보았을 때,
++i는 바로 증가한 값을 리턴하지만,
i++는 현재 값을 복사할 같은 자료형의 객체를 생성하여 저장해두고,
복사생성자 iterator copy_iter = *this;
객체의 생성과 동시에 같은 자료형객체의 값을 대입한다.
값을 증가시킨 후에, 복사해둔 객체의 값을 리턴한다.
그러면
현재는 증가되지 않은 값이 보여지지만, 실제로는 이미 증가된 것이다.
그래서 왠만하면 전위증가를 사용하는 이유가,
후위증가는 무의미한 객체의 생성 및 해제 비용이 생길 수 있다는 것이다.
그리고 사용자자료형에 = 이라는 대입 오퍼레이터에 대한 함수도
자동으로 생성해주기 떄문에,
어떤객체를 만들어도 서로 대입이 가능하게 된다.
생성자 중에 복사생성자라는 것도 자동으로 생성이 된다.
복사의 원형이 되는 같은 자료형을 받아와서
해당 값 그대로 생성자로 쓰는 것이다.
//1번째 방식으로 c1과 c2 생성
CArr c1;
c1.i=100;
CArr c2;
c2 = c1;//2번째 방식으로 c1과 c2 생성
CArr c1;
c1.i=100;
CArr c2(c1)위의 2개의 코드는 같은 결과를 낳지만,
복사생성자를 사용하면 더 간단하게 생성과 동시에 초기화할 수 있다.
//3번째 방식으로 c1과 c2 생성
CArr c1;
c1.i=100;
CArr c2 = c1;위의 코드는 2번과 같다.
만들 면서 대입 하는 것이라서.
C++이 자동으로 복사생성자를 호출하는 것이다.
그리고 생성자를 사용자가 단 하나라도 만들었다면,
C++은 기본 생성자를 만들어주지 않는다고 한다.
위의 복사생성자를 오버로딩해도 기본생성자를 생성하지 않는다.
추가로, 어떤 클래스의 내부클래스는,
자신을 품는 클래스 즉 외부클래스의 private에 접근할 수 있다.
하지만 외부클래스가 내부클래스의 private 접근은 불가능하다.
하지만, 내부외부 두 클래스 사이에 친구선언을
friend class CArr; 라고 한다면,
CArr이 iterator의 private까지 공유할 수 있게 된다.
서로 공유한다.
이게 헷갈리게 되는데,
private에 접근하려고 요청하는 쪽에서 friend선언하는 것이아니라,
private값을 가지고 있는 쪽에서 요청하는 쪽을 friend선언 해야 한다.
굳이 private을 참조하는건 사실 방어적코딩 입장에서 좋은 방법은 아니다.
veciter = vecInt.erase(veciter);
해당 iterator가 가리키는 부분을 삭제하고,
안전한 다음 요소의 주소를 전달해주는 역할을 한다.
헤더의 템플릿에서 멤버함수를 외부에 자동완성하면 inline이라는 키워드가 붙는다.
해당 함수를 호출하는 쪽에 그냥 구현부를 그대로 붙여 넣겠다는 말이다.
함수를 호출하는 비용을 줄이기 위해서이다.
inline은 컴파일러가 적절히 판단하여, 너무 긴 코드는 붙여넣지는 않는다.
코드의 길이가 짧고, 자주 쓰이는 함수 같은 경우에 적합하다.
트리 - 순회가 불가능한 그래프
계층관계를 표현하는데 특화
이진탐색트리는 배열로 표현이 가능하다.
이진탐색인 2개의 뭉치로 나눠서 탐색을 하는 방법이고,
정렬된 데이터에서만 사용가능한데, 이걸 트리로 표현한게
BST라고 하고,
BST는 입력시에 값을 비교하면서 작은건 왼쪽으로 들어가므로,
효율적이지 못하지만, 값을 검색하는 경우에 효율적이다.
입력/탐색 모두 logN
하지만, 부모값이 만약 제일 작은 값이라면?
그냥 배열과 다를바가 없을 것이다.
매우 비효율적으로 된다.
부모노드가 중간값이 된다는 보장이 없으므로
아래와 같은 트리가 만들어졌다.
[SELF-BALANCED 기능이 추가된 트리]
AVL
RED-BLACK
알아서 루트노드를 균형을 맞춰서 변경한다.
트리를 제대로 사용하려면, 위처럼 구현해야만 한다.
C++에서 RED-BLACK트리가 구현된
map이라는 자료구조가 존재한다.
set이라는 트리형 자료구조도 존재한다.
using std::set
set<int> setInt;
setInt.insert(100);위처럼 쓰고, 트리에 가장 처음 들어간 값은 루트노드가 된다.
해당 트리 setInt라는 자료구조는 힙에 만들어질 것이다.
map이 set보다 더 많이 사용된다.
map<int, float> mapData;map은 2개의 자료형 중
처음 값을 키 값 (정렬을 위해 쓰이는 값)
마지막 값은 실제 저장하고 싶은 데이터값을 의미한다.
그래서 학생정보같은 경우에,
학생의 이름을 키값으로 하고, 학생의 정보를 실제 데이터로 두는 경우가 있을 것이다.
당연히 구조체를 인수로 넣을 수 있다.
#include <iostream>
#include<map>
#include "CArr.h";
using std::map;
using std::make_pair;
#define MAN 1 // ; 를 절대로 찍으면 안된다.
#define WOMAN 2
struct stdInfo {
private:
wchar_t name[5]; //사람 이름 최대로 4글자정도 (마지막글자는 문자열 끝)
unsigned char age; //사람 나이도 최대여봤자 100이기 때문에 최소정수형
unsigned char gender; //성별 2개뿐
public:
stdInfo() : name{}, age(0), gender(0)
{ }
stdInfo(const wchar_t* _name, char _age, char _gender) : name(), age(_age), gender(_gender)
{
//name은 그대로 사용하지 못해서, 주소가 가리키는 곳의 문자열을 배열로 한땀한땀 옮기기
wcscpy_s(name, _name);
}
};위처럼 stdInfo라는 학생정보용 구조체를 만들었고,
구조체에 값을 넣을 생성자를 만들건데, 매개변수가 존재하는 생성자를 만들면,
기본 아무것도 없는 생성자는 자동으로 생성이 되지 않으므로,
기본 생성자도 따로 정의해준다.
그리고 char문자열을 사용하는거나
const wchar_t*를 사용하는거나 똑같아서 그냥 wchar_t를 사용하여
문자열을 다루게 된다.
따로 해당 값을 가져와서 대입할 수가 없어서,
wcscpy_s로 생성자로서 값을 대입하는 것이라고 한다.
int main()
{
map<const wchar_t*, stdInfo> mapData;
//맵에 넣을 학생정보 생성
stdInfo st1 = {L"아이유", 20, WOMAN};
stdInfo st2 = {L"해린", 18, WOMAN };
//맵에 이름(key), 학생정보(value)를 저장
mapData.insert(make_pair(L"아이유", st1)); //반드시 make_pair로 짝을 맞춰서 넣어줘야함
mapData.insert(make_pair(L"해린", st2));
//find는 데이터를 가리키는 iterator를 반환한다.
//그래서 iterator로 해당 값을 가리키는 iteraotr를 받고,
//iterator에 *을 붙여서 포인터처럼 쓰도록 된 iterator연산자오버로딩 *를 사용하여, 값에 접근한다.
//값에 접근하게 되면, pair로 값을 반환하게 된다.
map<const wchar_t*, stdInfo>::iterator mapiter;
mapiter = mapData.find(L"해린");
//const wchar_t*, stdInfo 2개를 넣어놓은 pair가 나오게 되고,
//first는 이름부분, second는 학생정보구조체로 나오게 된다.
mapiter->first;
mapiter->second;
//찾는 키값이 존재하지 않을 경우, end-iterator가 반환된다.
mapiter = mapData.find(L"마누");
//mapData.end()는 이터레이터 함수.
if (mapiter == mapData.end()) {
//값이 존재하지 않는다.
}
}위처럼 map을 생성하고,
구조체를 생성한다.
그리고 map의 insert는 반드시 pair로 값이 k-v로 묶여서 들어가야하며,
map의 find함수는 iterator를 반환하게 된다.
그리고 해당 iterator의 참조인 (*mapiter).first로
첫번째 자료형의 값에 접근할 수 있게 된다.
find할 수 없으면 end iterator가 반환된다.
해당 map 자료형의 iterator의 end로 end_iterator와 논리식을 작성할 수 있다.
