리스트(std::list)

장 점

1. 더블 링크드 리스트 형식
2. 삽입 삭제 시에도 속도가 빠르다.

단 점

1. 임의 접근이 불가능하다.

가능한점

1. 크기 변경
2. 중간 삽입 삭제
3. 순차 접근

원본>  http://blog.naver.com/bravedog/100005053219

■ list의 능력

list의 내부 자료구조는 vector, deque와는 완전히 다르다. 그러므로 vector, deque와 비교를 할 때

다음과 같은 차이점이 보인다

  ● list는 랜덤 액세스를 지원하지 않는다. 예를 들어, 5번째 원소를 액세스하기 위해서 list는 앞의

     1~4번째 원소를 거쳐서 액세스하게 된다. 그러므로 특정 위치의 원소를 액세스하는 경우 속도

     는 느릴 것이다.

  ● 어떠한 위치에서건 삽입과 삭제가 빠르게 이루어진다. 다른 원소들은 이동될 필요가 없기

     때문에 삽입, 삭제 동작은 상수 시간 복잡도를 가지게 된다. 내부적으로 보자면, 단지 포인터

     값들만 조작하면 그만이다.

  ● 삽입과 삭제 동작이 모든 포인터와 레퍼런스, 그리고 반복자를 무효화시키지는 않는다.

  ● list는 거의대부분의 동작들이성공하거나 아니면 아무런 영향도 받지않는 예외핸들링을 제공한다.

list의 멤버 함수들은 vector와 deque와의 다른 점들을 반영한다

  ● list는 [] 연산자와 at()을 제공하지 않는다. 왜냐하면, 랜덤 액세스를 지원하지 않기 때문이다.

  ● list는 용량과 재할당과 관련된 함수들을 제공하지 않는다. 왜냐하면, 두 함수 모두 필요없기

    때문이다.

    각각의 원소들은 자신만의 메모리를 가지고 있으며 이것은 원소가 지워지기 전까지 유효하다.

  ● list는 원소를 이동시키기 위한 특별한 멤버 함수들을 제공한다. 이 멤버 함수들은 같은 이름의

    STL 알고리즘보다 빠르게 동작한다. 왜냐하면, 알고리즘은 이들을 복사한 후 이동하지만,

    멤버 함수으 lruddn는 단지 포인터 값만 재지정하기 때문이다.

자료의 집합을 나타내는 클래스 템플릿. 단위 작업에 필요한 시간복잡도에 의해 구분된다.

다른 타입의 데이터를 저장할 수 있게 쉽게 커스터마이징(이용자가 사용방법과 기호에 맞춰 설정하거나 기능을 변경)할 수 있다.

알고리즘의 동작을 결정하는 객체. 함수호출 연산자( ()연산자 ) 를 적용할 수 있는 모든 대상이 함수자가 될 수 있다. 일반함수, 혹은 ()연산자를 오버로딩한 클래스의 객체들이 해당된다. greater<>, less<>등등 여러 알고리즘에서 유용하게 사용할 수 있는 템플릿이다.

STL :  7가지 basic type이 사용가능할 뿐만 아니라 basic type에서 상속된 3가지 타입이 더 있다그리고 basic type에서 상속 받는 자신만의 콘테이너를 만들수도 있다 

메인 카테고리 : sequence  ,  associative

sequence : vector, list, deque

associative : set, multiset, map, multimap

sequence containers

line으로 시각화 할수 있는 요소들의 집합을 저장. 각 요소들은 선을 따라서 다른 요소들과 연결되어 있다.

끝요소를 제외한 각 요소들은 어떤 요소들의 앞에 있을 수 있고 뒤에 있을 수 있다.

 associative

키를 이용하여 데이터를 엑세스. 사전과 비슷한 개념. 키오브젝트가 인덱스 역할을 하고 value오브젝트가 인덱스가 가리키는 값이 됨

각 컨테이너들을 include

#include <vector>

#include <list>

#include ........................

Member Function

size()

empty()

max_size()

begin()

end()

rbegin()

rend()

container가  가진 데이터를 다양한 방법으로 처리하는 프로시져다

그렇지만 container의 멤버함수는 아니고 템플릿 함수들이다.

 #include <algorithm> 

1. find(시작주소, 끝주소, 찾을값)

   ->주어진 원소와 같은것으로 판단되는 원소를 검색하는 선형 검색 알고리즘. 기본적으로 == 연산자를 사용

   ->동일한 최초의 값을 리턴

   ex) int arr[5] = {1, 2, 3, 4, 5};

   int* k = find(arr, arr+5, 3);

   cout<<(*k)<<endl;  => 3

   -> 반환값 : 찾는 값의 주소

2. sort(시작, 끝)

   -> 정렬 알고리즘(지정한 순서로 정렬)

   ex) int arr[5] = {1, 5, 2, 3, 4};

   sort(arr, arr+5);  //1,2,3,4,5 순으로 정렬

3. make_heap()

   -> 어떤 구간[S,E)를 힙으로 만든다

4.  count(시작주소, 끝주소, 찾을값)

   -> 엘리먼트의 갯수를 리턴

   -> 반환값 : 찾는 값의 갯수 (갯수만큼 count가 ++됨)

5.  search(B의시작주소, B의 끝주소, A의시작주소, A의 끝주소)

   -> 어떤 한 container(A)의 연속적은 패턴(값들)을 다른 한 container(B)에서 찾아본다

   -> 반환값 : 최초에 발견된 값들의 B의 시작주소

6.  equal()

   -> 두 콘테이너의 데이터가 완전히 같으면 true를 리턴

7.  copy()

   -> 시퀀스 값을 복사

8. swap()

   -> 값을 서로 바꾼다.

9. iter_swap()

   -> 시퀀스 값을 서로 바꾼다

10. fill()

    -> 시퀀스의 특정 위치에 값을 채운다.

11. max()

    -> 주어진 입력중에서 가장 큰 값을 구한다. 기본 자료형 이외에도 연산자를 오버로딩한 클래스나 구조체를 입력으로 받을 수 있다.

12. min()

    -> max()와 같지만 최소값을 반환한다

13. insert()

    -> if( (*iter) == 3)                  //iter가 3과 같으면

    (*iter).insert(iter, 100);    //그 앞에 100을 넣어라.

14. iter_swap()

    -> 시퀀스 값을 서로 바꾼다.

15.  merge(src1의 시작주소, src1의 끝주소, src2의 시작주소, src2의 끝주소, dest의 시작주소)

    -> 두개의 저장소를 결합한다.

16.  accumulate()

    -> 주어진 범위의 값을 더한다.

17.  for_each(시작, 끝, 각각의element를 함수로 넘겨줌)

    ->각 콘테이너의 엘리먼트 값을 탐색

    ex) void AddNum(int num)

    {

    cout << (num+10) << endl;

    }

    void main()

    {

    int arr[5] = {1, 2, 3, 4, 5};

    for_each(arr, arr+5, AddNum);

    }

    -> +10씩 더해진 값이 나옴