STL - List #2

#include <iostream>

#include <vector>

#include <list>

using namespace std;

// List

// vector 동적배열

// [             ]

// 단일 / 이중 / 원형

// [1] -> [2] -> [3] -> [4] -> [5]

// [1] <-> [2] <-> [3] <-> [4] <-> [5] <-> [ Myhead : end() ] <->  메모리 상으로는 end()와 begin()이 연결되어 있지만 오류를 잡아내기위한 오류임

// [1] <-> [2] <-> [3] <-> [4] <-> [5] <-> [1]

// list : 연결 리스트

class Node {

public:

public:

 Node* _next; //객체가 직접 들어갈 순 없고 포인터여야함

 Node* _prev;

 int _data;

};

// 연속적이지 않게 저장됨

// 즉 다음 데이터가 어디있는지 알고있음

int main()

{

 // list (연결 리스트)

 // - list 동작 원리

 // - 중간 삽입/삭제 (GOOD / GOOD)

 // - 처음/끝 삽입/삭제 (GOOD / GOOD)

 // - 임의 접근 (1번째 데이터는 어디 있습니까?) li[3] 굉장히 느리다...

 list<int> li;

 list<int>::iterator itRemember;

 for (int i = 0;i < 100;i++) {

 if (i == 50) {

 itRemember = li.insert(li.end(), i);

 }

 else {

 li.push_back(i);

 }

 }

 // 벡터와는 다르게 push_front를 지원함

 // 어느정도 벡터보단 처음 삽입이 효율적으로 작동한다는 증거?

 li.push_front(10);

 int size = li.size();

 //int cap=li.capacity; 지원하지 않음 why? 실시간으로 노드를 생성해 연결하기 때문

 int first = li.front();

 int last = li.back();

 //li[3]=10; 임의 접근 지원하지 않음  노드에 접근해 다음 노드로 하나씩 이동하는 방식이기 때문에 지원하지 않음

 list<int>::iterator it; //iterator 지원 그러나 벡터의 iterator와는 다르게 작동함

 list<int>::iterator itBegin=li.begin();

 list<int>::iterator itEnd=li.end();

 it = ++itBegin;

 it = --itBegin;

 it = itBegin++;

 it = itBegin--;

 // it = itBegin + 10; 지원하지않음

 for (list<int>::iterator it1 = li.begin();it1 != li.end();++it1) {

 cout << *it1 << endl;

 }

 li.insert(itBegin, 100);

 li.erase(li.begin()); li.pop_front(); //처음 삭제

 li.remove(10); // 10이라는 값을 가진 모든 데이터를 삭제함. 중간 삭제가 쉽기 때문

 // 임의 접근이 안된다.

 // 중간 삽입/삭제는 빠르다 (?)

 // 50번 인덱스에 있는 데이터를 삭제!

 //it = li.begin();

 //for (int i = 0;i < 50;i++) {

 // it++; //굉장히 연산이 많이 필요함

 //}

 //li.erase(it);

 // 그럼 왜 중간 삽입/삭제가 빠르다고 하는 걸까

 // 이유 list::insert()를 이용하면 삽입된 주소를 반환할 수 있다.

 // 그 주소를 저장해 둔 후 후에 삭제가 필요할 때 바로 접근이 가능

 li.erase(itRemember);

 for (list<int>::iterator it1 = li.begin();it1 != li.end();++it1) {

 cout << *it1 << endl;

 }

 return 0;

}