class CLASS
{
    public int a;
    public CLASS()
    {
       Console.WriteLine("CLASS");   
    }
}

class Program
{
    static void Main(string[] args)
    {
        CLASS[] c;
        c = new CLASS[10];   

        c[0].a = 10; //<=개체 참조가 개체의 인스턴스로 설정되지 않았습니다. 라고 예외발생
        Console.ReadKey();//CLASS가 전혀 출력되지 않는다.
    }
}


☆ 이유 ☆
  c = new CLASS[10]; 에서 c는 10개의 칸을 가진 CLASS 타입의 배열 객체이지만 이 배열 안의 CLASS는 각각은 인스턴스화가 안되서 객체가 아니다.

☆ 해결법 ☆
 c[0] = new CLASS();   ......각각  할당시켜줘야 한다.




참고

http://nuberus.blog.me/50182739063 

​

저작자표시



https://www.dostips.com/DtTipsStringManipulation.php


저작자표시

'0x0001 > C, C++' 카테고리의 다른 글

[C, C++] 매크로함수 VS 인라인함수  (0) 2019.02.09
[C언어] 주석 TIP  (0) 2019.02.09
[C언어] n 에서 m 까지의 합을 재귀로 작정  (0) 2019.02.09
[C++] Vector와 List의 차이점  (0) 2019.02.08
[C++] 함수객체 ( Functor )  (0) 2019.02.08


multimap은 여러 key를 중복해서 저장할 수 있습니다. map과 다른 유일한 차이점 입니다.

중복 key를 허용하는 multimap은 [] 연산자를 제공하지 않습니다. 

 

 

[ multimap의 count()와 find() 멤버 함수  ] 

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <map>
using namespace std;
 
int main(){
 
    multimap<int, int> mm;
    mm.insert(pair<int, int>(5, 100));
    mm.insert(pair<int, int>(3, 100));
    mm.insert(pair<int, int>(8, 100));
    mm.insert(pair<int, int>(3, 100)); // 중복
    mm.insert(pair<int, int>(1, 100));
    mm.insert(pair<int, int>(7, 100));
    mm.insert(pair<int, int>(8, 100)); // 중복
 
     // key 3의 원소의 개수 count() 멤버함수 사용
    cout<<"key 3의 원소의 개수 : "<< mm.count( 3 )<<endl;
 
    // find() 멤버함수 사용
    // 찾은 key원소의 처음 반복자리턴(중복 되있으니까)
    // 즉! (3, 100)을 가르키는 반복자
    multimap<int, int>::iterator Iter = mm.find( 3 );
    if( Iter != mm.end() ){
        cout<<"key 3에 매핑된 value : "<< Iter->second << endl;
    }else{
        cout<<"못찾았음!!"<<endl;
    }
 
    system("pause");
    return 0;
}

 

 

 

[ multimap의 lower_bound(), upper_bound(), equal_range() 멤버 함수 ] 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <map>
using namespace std;
 
int main(){
 
    multimap<int, int> mm;
    mm.insert(pair<int, int>(5, 100));
    mm.insert(pair<int, int>(3, 100));
    mm.insert(pair<int, int>(8, 30));
    mm.insert(pair<int, int>(3, 40)); // 중복
    mm.insert(pair<int, int>(1, 70));
    mm.insert(pair<int, int>(7, 100));
    mm.insert(pair<int, int>(8, 50)); // 중복
 
 
 
    // lower_bound(), upper_bound() 멤버함수 사용
    multimap<int, int>::iterator Iter_lower = mm.lower_bound( 3 );
    multimap<int, int>::iterator Iter_upper = mm.upper_bound( 3 );
 
    multimap<int, int>::iterator Iter;
    cout<<"구간 [lower_bound(), upper_bound()) 순차열, 원소값은 ";
    for( Iter = Iter_lower; Iter != Iter_upper; ++Iter ){
        cout<<"("<< Iter->first <<", " << Iter->second <<")"<<" ";
    }
    cout<<endl;
 
    
    
    // equal_range() 멤버 함수 사용
    pair< multimap<int, int>::iterator, multimap<int, int>::iterator > pr;
    pr = mm.equal_range( 8 );
    if( pr.first != pr.second ){
 
        cout<<"구간 [pr.first, pr.second) 순차열, 원소값은 ";
        for( Iter = pr.first; Iter != pr.second; ++Iter ){
            cout<<"("<< Iter->first <<", " << Iter->second <<")"<<" ";
        }
 
    }else{
        cout<<"순차열을 찾을 수 없습니다.";
    }    
    cout<<endl;
 
 
    system("pause");
    return 0;
}

 

 

 

시퀀스 컨테이너와 연관 컨테이너의 차이점

 

: 시퀀스 컨테이너는 원소의 상대적인 순서가 유지되며 연관 컨테이너는 특정 정렬 기준에 따라 원소가 정렬 됩니다.

 

 

연관 컨테이너의 lower_bound()와 upper_bound()의 반환값

 

: lower_bound()는 찾는 원소의 순차열 시작반복자를 반환하며 upper_bound()는 찾는 원소의 순차열 끝 반복자를 반환 합니다. 원소를 찾지 못하면 찾는 원소의 순차열 끝 반복자를 반환합니다. 

 

      begin Iter                                end 

ex ) 10      30      30      40      50      60 

             lower        upper

 

원소를 찾지 못하면 upper가 가리키는 반복자를 리턴합니다. end()가 아닙니다.

 

저작자표시

'0x0001 > STL' 카테고리의 다른 글

[C++ STL] 연관 컨테이너 - 맵(map)  (0) 2019.02.16
[C++ STL] 연관 컨테이너 - 멀티셋(multiset)  (0) 2019.02.16
[C++ STL] 연관 컨테이너 - 셋(set)  (0) 2019.02.16
[C++ STL] 시퀀스 컨테이너 - 리스트(list)  (0) 2019.02.16
[C++ STL] 시퀀스 컨테이너 - 덱(deque)  (0) 2019.02.16



map 컨테이너는 연관 컨테이너 중 자주 사용하는 컨테이너로 원소를 key와 value의 쌍으로 저장합니다.

map 컨테이너는 set 컨테이너 처럼 원소의 key는 컨테이너에 중복 저장 될 수 없습니다.

 

map의 원소는 pair 객체로 저장되며 pair 객체의 first 멤버변수는 key로 second 멤버 변수는 value 입니다.

 

map 컨테이너는 insert() 멤버함수와 []연산자를 통해서 원소를 추가 할 수 있습니다.

 

 

[ map의 insert() 멤버 함수 ]

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <map>
 
using namespace std;
 
int main(){
 
    // key, value 모두 정수형인 컨테이너 생성
    // 기본 정렬 기준 less
    map<int, int> m;
 
    m.insert(pair<int, int>(5,100)); // 임시 pair객체 생성후 저장
    m.insert(pair<int, int>(3,100));
    m.insert(pair<int, int>(8,30));
    m.insert(pair<int, int>(4,40));
    m.insert(pair<int, int>(1,70));
    m.insert(pair<int, int>(7,100));    
 
    // pr 객체 생성후 저장
    pair<int, int> pr(9, 50);
    m.insert(pr);
 
    map<int, int>::iterator Iter;
    for( Iter = m.begin(); Iter != m.end(); ++Iter ){
 
        cout<<"Key : "<<(*Iter).first<<", Value : "<<(*Iter).second<<endl;
    }
    cout<<endl;
 
 
    // 반복자는 -> 연산자가 연산자 오버로딩되어 있으므로 
    // 포인터처럼 멤버를 -> 연산자로 접근할 수 있습니다.
    for( Iter = m.begin(); Iter != m.end(); ++Iter ){
        cout<<"("<<Iter->first<<","<<Iter->second<<")"<<" ";
    }
    cout<<endl;
 
    // 삽입 성공 여부를 나타내는 pair객체를 리턴하는 insert() 멤버함수
    pair<map<int, int>::iterator, bool > s_pr;
    s_pr = m.insert(pair<int, int>(5, 200)); // 키 값이 저장되어있기때문에 실패!!
 
                                             // 성공시 저장된 위치의 반복자 리턴
                                             // 실패한다면 이전에 저장된 원소의 반복자 리턴
    if( s_pr.second ){
        cout<< "Key : " << s_pr.first->first << ", Value : "
            <<s_pr.first->second<<" 저장"<<endl;
    }else{
        cout<<"키값이 중복되어 삽입 실패!"<<endl;
    }
 
    system ("pause");
    return 0;
}

 

 

insert() 멤버함수는 pair객체를 인자로 받아 map의 원소인 key와 value의 쌍을 저장합니다.

 

 

[ map의 [] 연산자 ]

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <map>
using namespace std;
 
int main(){
 
    map<int, int> m;
 
    m[5] = 100; // key 5, value 100의 원소를 m에 삽입한다.
    m[3] = 100;
    m[8] = 30;
    m[4] = 40;
    m[1] = 70;
    m[7] = 100;
    m[9] = 50;
 
    map<int, int>::iterator Iter;
    for( Iter = m.begin(); Iter != m.end(); ++Iter ){
        cout<<"["<<Iter->first<<","<<Iter->second<<"]"<<" ";
    }
    cout<<endl;
 
    m[5] = 200; // key 5의 value를 200으로 갱신한다.
 
    for( Iter = m.begin(); Iter != m.end(); ++Iter ){
        cout<<"["<<Iter->first<<","<<Iter->second<<"]"<<" ";
    }
    cout<<endl;
 
    system("pause");
    return 0;
}

 

 

map의 [] 연산자를 사용하여 쉽게 원소(key, value)를 추가하거나 value값을 갱신 할 수 있습니다.

 

key에 해당하는 원소가 map에 없다면 추가 연산

key에 해당하는 원소가 map에 있다면 원소의 value를 갱신

 

 

[ map 컨테이너의 정렬 기준 조건자 greater ]

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <string>
#include <map>
using namespace std;
 
int main(){
 
    // greater 정렬 기준의 key:int, value:string 타임의 컨테이너 m생성
    map<int, string, greater<int>> m;
 
    m[5] = "five"; //원소 추가
    m[3] = "three";
    m[8] = "eight";
    m[4] = "four";
    m[1] = "one";
    m[7] = "seven";
    m[9] = "nine";
 
    map<int, string, greater<int>>::iterator Iter;
    for( Iter = m.begin(); Iter != m.end(); ++Iter ){
        cout<<"["<<Iter->first<<","<<Iter->second<<"]"<<" ";
    }
    cout<<endl;
    
    system("pause");
    return 0;
}

 

 

[ map의 find(), lower_bound(), upper_bound(), equal_range() ]

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <map>
using namespace std;
 
int main(){
 
    map<int, int> m;
 
    m[5] = 100;
    m[3] = 100;
    m[8] = 30;
    m[4] = 40;
    m[1] = 70;
    m[7] = 100;
    m[9] = 50;
 
    map<int, int>::iterator Iter;
 
    // find() 멤버 함수 사용 key값 5의 해당하는 위치의 반복자 리턴
    Iter = m.find( 5 );
 
    if( Iter != m.end() ){ //찾았으면 해당위치 반복자, 실패면, end()
        cout<< "key " << "[" << Iter->first << "]" <<" 의 value값 : "<< Iter->second <<endl;
    }
 
 
 
    // lower_bound(), upper_bound() 함수 사용 순차열 구간 확인
    map<int, int>::iterator Iter_lower;
    map<int, int>::iterator Iter_upper;
    Iter_lower = m.lower_bound( 5 );
    Iter_upper = m.upper_bound( 5 );
 
    for( Iter = Iter_lower; Iter != Iter_upper; ++Iter ){
        cout<<"구간[lower_bound(), upper_bound()) 의 순차열, 원소값"
            <<"("<<Iter->first<<","<<Iter->second<<")"<<" "; // (5, 100)
    }
    cout<<endl;
 
 
 
    // equal_range() 멤버 함수사용, pair 객체 리턴
    pair< map<int, int>::iterator, map<int, int>::iterator > pr;
    pr = m.equal_range( 5 );
 
    for( Iter = pr.first; Iter != pr.second; ++Iter ){
        cout<<"구간[pr.first, pr.second) 의 순차열, 원소값"
            <<"("<<Iter->first<<","<<Iter->second<<")"<<" "; // (5, 100)
    }
    cout<<endl;
 
 
    system("pause");
    return 0;
}

 

저작자표시

'0x0001 > STL' 카테고리의 다른 글

[C++ STL] 연관 컨테이너 - 멀티맵(multimap)  (0) 2019.02.23
[C++ STL] 연관 컨테이너 - 멀티셋(multiset)  (0) 2019.02.16
[C++ STL] 연관 컨테이너 - 셋(set)  (0) 2019.02.16
[C++ STL] 시퀀스 컨테이너 - 리스트(list)  (0) 2019.02.16
[C++ STL] 시퀀스 컨테이너 - 덱(deque)  (0) 2019.02.16


multiset은 set과 다르게 key가 중복으로 저장 됩니다.

 

[ multiset의 insert() 멤버 함수 ]

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <set>
 
using namespace std;
 
int main(){
 
    // multiset은 원소 중복 가능
    multiset<int> ms;
    ms.insert(50);
    ms.insert(30);
    ms.insert(80);
    ms.insert(80);
    ms.insert(30);
    ms.insert(70);
    
    multiset<int>::iterator Iter;
 
    // 저장된 위치의 반복자를 리턴
    Iter = ms.insert(10);
 
    cout<< "Iter의 원소 : " << *Iter <<endl;
    for( Iter = ms.begin(); Iter != ms.end(); ++Iter ){
        cout<< *Iter <<" ";
    }
    cout<<endl;
 
    system ("pause");
    return 0;
}

 

위의 예제 multiset의 구조

 

   50 

 30                   80

 10             30        70           80

 

mutiset의 탐색순서 : 10   30   30   50   70   80   80  ( 정렬 기준 less( < 연산 ) )

 

mutiset의 insert() 멤버함수는 중복 저장이 될 수 있으므로, set의 삽입 성공(중복)유무를 담는 pair객채를 리턴하지 않아도 됩니다.

즉! 저장된 위치만을 가리키는 반복자를 반환 합니다.

 

 

[ multiset의 count(), find(), lower_bound(), upper_bound() 멤버 함수( 찾기 관련 함수 ) ]

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <set>
 
using namespace std;
 
int main(){
 
    // multiset은 원소 중복 가능
    multiset<int> ms;
    ms.insert(50);
    ms.insert(30);
    ms.insert(80);
    ms.insert(80);
    ms.insert(30);
    ms.insert(70);
    ms.insert(10);
    
    multiset<int>::iterator Iter;
    for( Iter = ms.begin(); Iter != ms.end(); ++Iter ){
        cout<< *Iter <<" ";
    }
    cout<<endl;
 
    // count() 멤버 함수
    cout<< "30 원소의 개수 : " << ms.count(30) <<endl;
 
    // find() 멤버 함수 
    Iter = ms.find(30); //30 첫번째 원소의 반복자
    cout<<"Iter : "<<*Iter << endl;
 
    multiset<int>::iterator Iter_lower;
    multiset<int>::iterator Iter_upper;
 
    // lower_bound(), upper_bound() 멤버 함수
    Iter_lower = ms.lower_bound(30); // 30 순차열의 시작 반복자
    Iter_upper = ms.upper_bound(30); // 30 순차열의 끝 반복자
   
    // 30 != 40
    if( Iter_lower != Iter_upper ){
        cout<<"ms에 있음!";
    }else{
        cout<<"ms에 없음!";
    }
    cout<<endl;
 
    //
    cout<<"[lower_bound, upper_bound)의 순차열 : ";
    Iter_lower = ms.lower_bound(10);
    Iter_upper = ms.upper_bound(80);
 
    for( Iter = Iter_lower; Iter != Iter_upper; ++Iter){
        cout<< *Iter << " ";
    }
    cout<<endl;
 
    system ("pause");
    return 0;
}



[ lower_Iter와 upper_Iter  ]

 

        Iter

10        30        30        50        70         80        80       N

    lower_Iter      upper_Iter

 

마지막 중복원소의 다음 원소인 (50)을 upper_Iter가 가르킴

 

 

[ 결과 ]

 


 

 

[ multiset의 equal_range() 멤버 함수 ]

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <set>
using namespace std;
 
int main(){
    
    multiset<int> ms;
 
    ms.insert(50);
    ms.insert(30);
    ms.insert(80);
    ms.insert(80);
    ms.insert(30);
    ms.insert(70);
    ms.insert(10);
    ms.insert(80);
 
    multiset<int>::iterator Iter;
    for( Iter = ms.begin(); Iter != ms.end(); ++Iter ){
        cout<<*Iter<<" ";
    }
    cout<<endl;
    
    // equal_range() 멤버함수 사용
    // 10 30 30 50 70 80 80 80
 
    pair<multiset<int>::iterator, multiset<int>::iterator> pr;
    pr = ms.equal_range(80);
 
    // [lower, upper) 구간의 순차열
    cout<<"구간 [lower, upper)의 순차열 : ";
    for( Iter = pr.first; Iter != pr.second; ++Iter ){
        cout<<*Iter<<" "; // 80 80 80
    }
    cout<<endl;
 
    system("pause");
    return 0;
}

 

저작자표시

'0x0001 > STL' 카테고리의 다른 글

[C++ STL] 연관 컨테이너 - 멀티맵(multimap)  (0) 2019.02.23
[C++ STL] 연관 컨테이너 - 맵(map)  (0) 2019.02.16
[C++ STL] 연관 컨테이너 - 셋(set)  (0) 2019.02.16
[C++ STL] 시퀀스 컨테이너 - 리스트(list)  (0) 2019.02.16
[C++ STL] 시퀀스 컨테이너 - 덱(deque)  (0) 2019.02.16

[ 연관 컨테이너 ]

 

연관 컨테이너는 특정 정렬 기준(조건자)에 따라 원소를 자동 정렬 하는 컨테이너 입니다. 이때 정렬 기준은 템플릿 매갭변수에 지정 할 수 있으며, 기본 정렬 기준은 less 조건자입니다.  그렇다 보니 시퀀스 컨테이너에서 순서와 관련된 함수류인 push_back(), push_front(), pop_back(), pop_front(), front(), back()을  제공하지 않습니다.

 

또한, 연관 컨테이너의 핵심은 빠른 원소 찾기이며, 균형 이진 트리를 사용하므로 찾기 연산(find(), lower_bound(), upper_bound(), equal_range(), count())에 뛰어난 성능(로그시간)을 보이며 insert() 멤버 함수를 이용한 삽입도 로그 시간 복잡도를 보입니다.

 

모든 연관 컨테이너의 key는 삽입, 검색, 제거등에 모두 이용됩니다. 그래서 모든 연고나 컨테이너의 key는 변경할 수 없습니다.



set 컨테이너는 연관 컨테이너 중 단순한 컨테이너로 key라 불리는 원소(value)의 집합으로 이뤄진 컨테이너 입니다.

모든 연관 컨테이너는 노드 기반 컨테이너 이며 균형 이진 트리로 구현 되므로 균형 이진 트리의 모든 특징을 가집니다.

 

 

[ set 컨테이너의 insert() 멤버 함수 ]

 

set은 컨테이너에 원소(key)를 저장(삽입)하는 유일한 멤버함수 insert()를 제공합니다.( 삽입관련 다른 함수 없음 )

set은 원소를 key라 하며 이 키를 비교하여 내부 원소를 정렬합니다.

set은 원소의 중복을 허용 하지 않습니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <set>
 
using namespace std;
 
int main(){
 
    //정수 원소를 저장하는 기본정렬기준 less인 빈 컨테이너 생성
    set<int> s;
        
    pair<set<int>::iterator, bool> pr;
    pr = s.insert(50);
    if( pr.second ){
        cout<< *pr.first << " 삽입 성공!" <<endl;
    }else{
        cout<< *pr.first << " 중복으로 삽입 실패!" <<endl;
    }
    s.insert(30);
    s.insert(80);
    s.insert(40);
    s.insert(10);    
    s.insert(70);
    s.insert(90);
 
    pr = s.insert(30); //중복된 원소는 삽입 실패!!
    if( pr.second ){
        cout<< *pr.first << " 삽입 성공!" <<endl;
    }else{
        cout<< *pr.first << " 중복으로 삽입 실패!" <<endl;
    }    
 
    set<int>::iterator Iter;
    for( Iter = s.begin(); Iter != s.end(); ++Iter ){
        cout<<*Iter<<" "; // 10 30 40 50 70 80 90
    }
    cout<<endl;    
 
    system("pause");
    return 0;
}

 

insert()멤버 함수는 원소의 중복을 허용하지 않기 때문에 반환값으로 실패를 확인할 수 있습니다.

반환값은 pair객체이며,  

first와 second는 각각 삽입된 원소(key)의 위치를 가리키는 반복자와 true, false를 나타내는 boo l값입니다. 

 

 

위의 예제에서 set의 구조

 50

30                   80

10              40     70             90

 

set의 반복자로 원소를 탐색하는 순서

- 10 30 40 50 70 80 90 ( 모든 노드의 부모노드는 왼쪽 자식노드보다 크고 오른쪽 자식노드보다 작습니다.)

 

위의 예제에서 쉽게 놓치는 부분중 하나는 pr.second가 성공이면 pr.first는 삽입한 원소(30)를 가리키는 반복이고, 실패하면 pr.first는 이미 삽입 되어있던 원소(30)를 가리키는 반복자 입니다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <set>
 
using namespace std;
 
int main(){
 
    // 정수 원소를 저장하는 기본정렬기준 less인 빈 컨테이너 생성
    set<int> s;
 
    // 정렬 기준으로 greater<int> 조건자를 사용( > 오름차순 )
    //set< int, greater<int> > s;
    /*                50
    *            80          30
    *
    *        90     70   40      10
    */
        
    pair<set<int>::iterator, bool> pr;
    s.insert(50);    
    s.insert(30);
    s.insert(80);
    s.insert(40);
    s.insert(10);    
    s.insert(70);
    pr = s.insert(90);// 삽입한 원소 pr.first(90)
 
    // 삽입할 위치지정 insert()멤버함수 사용
    // pr.first가 가리키는 위치부터 탐색을 시작하여 85를 삽입합니다.
    s.insert(pr.first, 85);// 90의 원소의 반복자에서 검색 시작후 삽입
 
    set<int>::iterator Iter;
    for( Iter = s.begin(); Iter != s.end(); ++Iter ){
        cout<<*Iter<<" "; // 10 30 40 50 70 80 85 90
    }
    cout<<endl;    
 
    system("pause");
    return 0;
}

 

위의 예제는 원소(key)의 삽입 위치를 지정하는 버전이며,

 

삽입 탐색을 시작할 위치로 삽입 위치가 정렬 순서와 맞는 다면, 바로 삽입되지만 아니라면 로그시간이 걸립니다. 즉! 삽입되는 원소가 탐색을 시작할 위치에 정렬순서상 맞는다면 바로 삽입 됩니다.

 

 

[ set의 key_comp(), value_comp() 멤버 함수 ]

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <set>
using namespace std;
 
int main(){
 
    set<int, less<int>> s1;      // 기준정렬 less 조건자
    set<int, greater<int>> s2; // 기준정렬 greater 조건자
 
 
    // s1 사용중인 정렬 기준 조건자를 리턴
    set<int, less<int>>::key_compare l_cmp = s1.key_comp();
    cout<< l_cmp(10, 20) << endl; // 10 < 20 연산
    
    // s2 사용중인 정렬 기준 조건자를 리턴
    set<int, greater<int>>::key_compare g_cmp = s2.key_comp();
    cout<< g_cmp(10, 20) << endl; // 10 > 20 연산
    cout<<endl;
 
 
    /**
    *    set은 저장 원소인 값(value)이 곧 비교로 사용되는키(key)가됩니다.
    */
    cout << "key_compare type : " << typeid(s1.key_comp()).name() << endl;
    cout << "value_compare type : " << typeid(s1.value_comp()).name() << endl;
    cout<<endl;
 
    cout << "key_compare type : " << typeid(s2.key_comp()).name() << endl;
    cout << "value_compare type : " << typeid(s2.value_comp()).name() << endl;
 
    system("pause");
    return 0;
}

 

위의 얘제 key_comp(), value_comp()의 출력값이 같은 이유는

set 컨테이너는 저장 원소인 값(value)이 곧 비교로 사용되는 키(key)값 이기 때문 입니다.

 

 

[ set의 count() 멤버 함수 ]

 

1
cout<< "원소 50의 갯수 : " << s.count(50) <<endl;

 

set은 중복된 원소를 가지지 않아 컨테이너의 원소중 50인 원소는 1개 아니면 0개 이다. 굳이 count() 함수가 필요 있어 보이지는 않지만, 연관 컨테이너의 인터페이스는 모두 같으므로 set도 count() 멤버 함수를 제공 합니다. ( 실행시간 : 로그시간복잡도 )

 

 

[ set의 find() 멤버 함수 ]

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <set>
using namespace std;
 
int main(){
 
    set<int> s;
    s.insert(50);
    s.insert(30);
    s.insert(80);
    s.insert(40);
    s.insert(10);
    s.insert(70);
    s.insert(90);
 
    set<int>::iterator Iter;
 
    // 30원소의 반복자를 반환
    // 30원소가 없으면, s.end()와 같은 반복자를 반환 합니다.
 
    // 연관컨테이너는 원소를 찾을 때 == 연산을 사용하지 않습니다.
    // 정렬 기준에 의해 key가 정렬되어 있으므로 
    // 컨테이너의 정렬 기준 조건자를 이용해 찾기 연산을 수행합니다.
 
    // !(*Iter<30) && !(30<*Iter) 30보다 작거나 크지 않다.
    // !s.key_comp()(a,b) && !s.key_comp()(b,a) 이면 두원소는 같음
    Iter = s.find(30);
 
    // end() 멤버 함수가 끝 표시 반복자를 반환하므로 
    // end()멤버 함수와 비교해서 검색이 성공했는 유무를 판단
    if( Iter != s.end() ){
        cout<<*Iter<< "가 s에 있다"<<endl;
    }else{
        cout<<"20이 s에 없다."<<endl;
    }
 
    // 30이 50보다 앞서 있지 않고 50도 30보다 앞서 있지 않은가?
    cout<< ( !s.key_comp()(30, 50) && !s.key_comp()(50, 30) ) <<endl; // false
    // 30이 30보다 앞서 있지 않고 30도 30보다 앞서 있지 않은가?
    cout<< ( !s.key_comp()(30, 30) && !s.key_comp()(30, 30) ) <<endl; // true
 
    system("pause");
    return 0;
}

 

 

 

[ set의 lower_bound(), upper_bound(), equal_range() 멤버 함수 ]

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <set>
using namespace std;
 
int main(){
 
    set<int> s;
    s.insert( 50 );
    s.insert( 30 );
    s.insert( 80 );
    s.insert( 40 );
    s.insert( 10 );
    s.insert( 70 );
    s.insert( 90 );
 
    set<int>::iterator Iter_lower;
    set<int>::iterator Iter_uppder;
 
    // 30이 시작하는 구간의 반복자
    Iter_lower = s.lower_bound(30);
 
    // 30이 끝나는 구간의 반복자( 찾는 원소의 다음 원소 반복자)
    Iter_uppder = s.upper_bound(30);
 
    cout<< *Iter_lower <<endl; // 30
    cout<< *Iter_uppder <<endl;// 40
 
    if( Iter_lower != Iter_uppder ){
        cout<<"["<<*Iter_lower<<","<<*Iter_uppder<<"] "<<"s에 있음!"<<endl;
    }else{
        cout<<"["<<*Iter_lower<<","<<*Iter_uppder<<"] "<<"s에 없읍!"<<endl;
    }
    
    // 55 원소의 시작과 끝구간을 리턴
    // 10 30 40 50 70 80 90 에서 55를 찾지못해 55의 다음 반복자
    // 밑에 보면 리턴되는 원소의 반복자의 시작과 끝이 같으므로 해당원소없음
    Iter_lower = s.lower_bound(55); //70
    Iter_uppder = s.upper_bound(55);//70
    
    if( Iter_lower != Iter_uppder ){
        cout<<"["<<*Iter_lower<<","<<*Iter_uppder<<"] "<<"s에 있음!"<<endl;
    }else{
        cout<<"["<<*Iter_lower<<","<<*Iter_uppder<<"] "<<"s에 없읍!"<<endl;
    }
    cout<<endl;
 
 
 
    // equal_range() 멤버 함수 사용
    pair< set<int>::iterator, set<int>::iterator > pr;
    pr = s.equal_range(30);
 
    cout<< *pr.first << endl;
    cout<< *pr.second << endl;
 
    if( pr.first != pr.second ){
        cout<<"s에 있음!"<<endl;
    }else{
        cout<<"s에 없음!"<<endl;
    }
 
    system("pause");
    return 0;
}

 

lower_bound(key) : 찾은 원소의 시작 반복자를 반환, 못찾았다면 입력된 key값의 다음 반복자 리턴

                            중복시 찾는 원소의 첫번째 원소( set은 해당사항없음 ) 

upper_bound(key) : 찾은 원소의 다음 원소를 가리키는 반복자를 반환, 못찾았다면 다음 반복자 리턴

 

[lower_bound, upper_bound) 구간에서 두 반복자가 같다면 찾는 원소가 없습니다.

 

equal_range(key) : lower_bound(), upper_bound()의 반복자 쌍을 pair객체로 반환 해줍니다.

저작자표시

'0x0001 > STL' 카테고리의 다른 글

[C++ STL] 연관 컨테이너 - 맵(map)  (0) 2019.02.16
[C++ STL] 연관 컨테이너 - 멀티셋(multiset)  (0) 2019.02.16
[C++ STL] 시퀀스 컨테이너 - 리스트(list)  (0) 2019.02.16
[C++ STL] 시퀀스 컨테이너 - 덱(deque)  (0) 2019.02.16
[C++ STL] 시퀀스 컨테이너 - 벡터(vector)  (0) 2019.02.16


list는 시퀀스 컨테이이며, 노드 기반 컨테이너로 원소가 노드 단위로 저장되며 list는 이중 연결 리스트(Double Linked List)로 구현됩니다.

list는 시퀀스 컨테이너가 갖는 모든 특징을 갖습니다. (push_front, push_back, pop_front, pop_back, front, back, insert, erase )

 

순차열 중간에 삽입, 제거가 빈번하게 발생하며, 원소의 상대적인 순서가 중요하다면 list 컨테이너를 사용합니다. 

 

list는 노드 기반 컨테이너로 at()과 []연산자가 없으며 임의 접근 반복자가 아닌 양방향 반복자를 제공합니다.

그래서 모든 원소를 탐색하려면 양방향 반복자의 연산인 ++, --를 사용합니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <list>
 
using namespace std;
 
int main(){
 
    list<int> lt;
    lt.push_back(10);
    lt.push_back(20);
    lt.push_back(30);
    lt.push_back(40);
    lt.push_back(50);
 
    list<int>::iterator Iter = lt.begin();
    for( ; Iter != lt.end(); ++Iter){
        cout<< *Iter <<" ";
    }
    cout<<endl;
 
    lt.push_front(100); //앞쪽에 추가
    lt.push_front(200); 
    
    for(Iter = lt.begin(); Iter != lt.end(); ++Iter){
        cout<< *Iter <<" "; // 200 100 10 20 30 40 50
    }
 
    system("pause");
    return 0;
}

 

 

list의 가장 큰 특징 중 하나는 순차열 중간에 원소를 삽입(insert), 제거(erase)하더라도 상수 시간 복잡도의 수행 성능을 보인다는 점입니다. 이유는 배열 기반 컨테이너 vector나 deque처럼 원소를 밀어내지 않고 노드를 서로 연결하기만 하며녀 되기 때문입니다. 

 

또한, 노드 기반 컨테이너의 삽입(insert)과 제거(erase) 동작은 반복자를 무효화 시키지 않습니다. 반복자가 가리키는 원소 자체가 제거되지 않는 한 반복자가 가리키는 원소는 그대로 존재합니다. 하지만, 배열 기반 컨테이너(vector, deque)의 반복자는 원소의 삽입과 제거 동작이 발생하면 "메모리가 재할당되거나 원소가 이동"할 수 있으므로 반복자가 무효화 됩니다.

 

[ 반복자 무효화 현상 ]

 

: 반복자가 가리키고 있는 원소를 지웠을 때 반복자가 다음을 가르키지 못하는 현상

while( v1.empty() != true )

{

v1.erase(Iter);

Iter++;   // erase삭제 후 현재 가르키는 위치가 무효화 되어 연산을 할 수 없다.

}

위의 예제처럼 주로 삭제시 발생하는데, 위의 에러를 방지 하려면, 아래와 같이 코딩 해야한다.

while( v1.empty() != true ) 

{ 

Iter = v1.erase(Iter); 

} 

 

[ 배열 기반 컨테이너 반복자 무효상태 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <vector>
using namespace std;
 
int main(){
 
    vector<int> lt;
    lt.push_back(10);
    lt.push_back(20);
    lt.push_back(30);
    lt.push_back(40);
    lt.push_back(50);
 
    vector<int>::iterator Iter = lt.begin();
    Iter++;
    Iter++; // 30을 가르킴
 
    // 메모리 재할당으로 인한 반복자 무효화 상태
    lt.push_back(60); 
    lt.push_back(70);
    lt.push_back(80);
 
    cout<<*Iter<<endl; // 에러발생
 
    system("pause");
    return 0;
}

 

 

[ list의 insert(), erase() 멤버함수 ]

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <list>
using namespace std;
 
int main(){
 
    list<int> lt;
    lt.push_back(10);
    lt.push_back(20);
    lt.push_back(30);
    lt.push_back(40);
    lt.push_back(50);
 
    list<int>::iterator Iter = lt.begin();
    Iter++;
    Iter++; // 30을 가르킴
    
    // vector와 다르게 반복자 무효화 현상은 잃어 나지 않음
    lt.push_back(60); 
    lt.push_back(70);
    lt.push_back(80);
    
    //30이 삭제되고 40을 가리키는 반복자 리턴
    Iter = lt.erase(Iter);     
    lt.insert(Iter, 30); // 40의 앞쪽에 30을 넣는다.
 
    Iter = lt.begin();
    while( Iter != lt.end() ){
        cout<< *(Iter++) <<endl;
    }
 
    system("pause");
    return 0;
}

 

위의 예제에서 insert(), erase() 사용법과, 반복자의 무효화 현상이 일어나지 않음을 확인할 수 있다.

list는 노드단위로 생성되어 Iter가 가르키는 위치에 노드하나만 연결만 시켜주기때문에 속도가 빠르며, 반복자들이 무효화 되지 않습니다.

즉! 각각의 노드단위로 구성되어있기때문에, 가르키는 노드가 삭제되지 않는 한 무효화 되지 않는다고 보면 된다.

 

[ list의 remove() 멤버 함수 ]

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <list>
using namespace std;
 
int main(){
 
    list<int> lt;
    lt.push_back(10);
    lt.push_back(20);
    lt.push_back(30);
    lt.push_back(40);
    lt.push_back(10);
    lt.push_back(30);
    lt.push_back(10);
    lt.push_back(40);
    lt.push_back(10);
    lt.push_back(10);
 
    list<int>::iterator Iter = lt.begin();            
    lt.remove(10); // 10 원소의 노드를 모두 제거 한다.
 
    Iter = lt.begin();
    while( Iter != lt.end() ){
        cout<< *(Iter++) <<endl;
    }
 
    system("pause");
    return 0;
}

 

list의 remove() 함수는 컨테이너의 모든 원소를 순차적으로 검색하며, 해당원소를 제거 합니다.

또한, list만이 remove() 멤버함수를 유일하게 가지고, erase()처럼 해당 값의 노드만을 제거하므로 속도가 빠르다.

반복자가 아닌 원소의 값으로 컨테이너의 원소를 제거해야 한다면 list 컨테이너를 선택하는 것이 좋습니다.

 

 

[ list의 remove_if() 멤버 함수 ]

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <list>
using namespace std;
 
 
bool predicate( int n ) // 단항 조건자
{
    return 10 <= n && n <= 30;
}
 
int main(){
 
    list<int> lt;
    lt.push_back(10);
    lt.push_back(20);
    lt.push_back(30);
    lt.push_back(40);
    lt.push_back(50);
    lt.push_back(10);
    lt.push_back(10);
    lt.push_back(10);
    lt.push_back(10);    
    
    list<int>::iterator Iter = lt.begin();
    while( Iter != lt.end() ){
        cout<< *(Iter++) <<" ";
    }
    cout<<endl;
 
    // 조건자가 참인 모든 원소를 제거
    lt.remove_if(predicate);
 
    Iter = lt.begin();
    while( Iter != lt.end() ){
        cout<< *(Iter++) <<" ";
    }
    cout<<endl;
 
    system("pause");
    return 0;
}

 

remove_if() 멤버함수는 단항 조건자가 참인 모든 원소를 제거합니다. 조건자는 bool 형식을 반환하는 함수류( 함수, 함수객체, 함수 포인터) 입니다.

 

[ list의 splice() 멤버 함수 ]

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <iostream>
#include <list>
using namespace std;
 
int main(){
 
    list<int> lt;
    list<int> lt2;
    lt.push_back(10);
    lt.push_back(20);
    lt.push_back(30);
    lt.push_back(40);
    lt.push_back(50);
        
    lt2.push_back(100);
    lt2.push_back(200);
    lt2.push_back(300);
    lt2.push_back(400);
    lt2.push_back(500);
    
    list<int>::iterator Iter = lt.begin();
    cout<<"lt1 : ";
    while( Iter != lt.end() ){
        cout<< *(Iter++) <<" "; //10 20 30 40 50
    }
    cout<<endl;
 
    Iter = lt2.begin();
    cout<<"lt2 : ";
    while( Iter != lt2.end() ){
        cout<< *(Iter++) <<" "; //100 200 300 400 500
    }
    cout<<endl << "====================="<<endl;
 
    Iter = lt.begin();
    ++Iter;
    ++Iter; // lt의 30을 가르킴
 
    list<int>::iterator Iter2 = lt2.begin();
    ++Iter2; // lt2의 200을 가르킴
 
 
    // splice() 1번 방법 반복자가 가리키는 원소를 잘라붙임
    // Iter가 가리키는 위치에 Iter2가 가리키는 위치의 lt2의 원소를 잘라붙임
    lt.splice(Iter, lt2, Iter2);
    Iter = lt.begin();
    cout<<"lt1 : ";
    while( Iter != lt.end() ){
        cout<< *(Iter++) <<" "; //10 20 200 30 40 50
    }
    cout<<endl;
 
    Iter2 = lt2.begin();
    cout<<"lt2 : ";
    while( Iter2 != lt2.end() ){
        cout<< *(Iter2++) <<" ";
    }
    cout<<endl << "====================="<<endl;
 
    // splice() 2번 list의 순차열을 잘라 붙임
    // lt.end()가 가리키는 위치에 순차열 [lt2.begin(), lt2.end())를 잘라붙임
    lt.splice(lt.end(), lt2, lt2.begin(), lt2.end() );
    Iter = lt.begin();
    cout<<"lt1 : ";
    while( Iter != lt.end() ){
        cout<< *(Iter++) <<" "; //10 20 200 30 40 50 100 300 400 500
    }
    cout<<endl;
 
    if( lt2.empty() ){
        cout<< "원소 없음!!";
    }else{
        Iter2 = lt2.begin();
        cout<<"lt2 : ";
        while( Iter2 != lt2.end() ){
            cout<< *(Iter2++) <<" "; // lt2의 순차열을 lt.end() 에 붙였기 때문에 lt2는 원소 없음
        }
    }    
    cout<<endl << "====================="<<endl;
 
 
    // splice() 3번 lt2의 모든 원소를 잘라 붙임
    // Iter2가 가리키는 위치에 lt의 모든원소를 잘라 붙임
    Iter2 = lt2.begin();
    lt2.splice(Iter2, lt);
 
    if( lt.empty() ){
        cout<< "원소 없음!!";
    }else{
        Iter = lt.begin();
        cout<<"lt1 : ";
        while( Iter != lt.end() ){
            cout<< *(Iter++) <<" "; //lt의 모든 원소를 lt2에 붙였기 때문에 lt는 원소 없음
        }
    }    
    cout<<endl;
    
    Iter = lt2.begin();
    cout<<"lt2 : ";
    while( Iter != lt2.end() ){
        cout<< *(Iter++) <<" "; //10 20 200 30 40 50 100 300 400 500
    }
    cout<<endl;
 
    system("pause");
    return 0;
}

 

[ 결과 ]

 


 

splice() 멤버함수는 다른 list 컨테이너의 순차열을 잘라 붙일 수 있습니다.

splice() 멤버함수는 상수 시간의 실행 동작을 보입니다. 이유는 lt와 lt2의 노드들을 단지 연결하기 때문 입니다.

 

 

[ list의 reverse() 멤버 함수 ]

 

1
2
//모든 원소를 뒤집는다.
lt.reverse();

 

 

reverse() 멤버 함순는 모든 원소의 순차열을 반대로 뒤집습니다.

reverse() 멤버 함수는  이중 연결 리스트의 탐색 경로를 서로 바꿈으로써 순차열을 리버스 시킵니다.

 

 

 

[ list의 unique() 멤버 함수 ]

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <list>
using namespace std;
 
//이항 조건자
bool predicate(int first, int second){
 
    // 다음원소 - 현재 원소 <=  0
    // 조건자 : 두원소의 차가 0보다 작거나 같으면
    return second - first <= 0 ;
}
 
int main(){
 
    list<int> lt;
    lt.push_back(10);
    lt.push_back(10);
    lt.push_back(20);
    lt.push_back(30);
    lt.push_back(30);
    lt.push_back(30);
    lt.push_back(40);
    lt.push_back(50);
    lt.push_back(10);
 
    for( list<int>::iterator Iter = lt.begin(); Iter != lt.end(); ++Iter ){
        cout<< *Iter <<" "; // 10 10 20 30 30 30 40 50 10
    }
    cout<<endl;
 
    // 1번 unique() 함수 사용법
    // 인접한 같은 원소를 유일하게 만듭니다. ( 10 20 30 40 50 10 )
    // 연속된 같은 원소는 삭제하고 하나로 만듬
    // 연속된 원소만 하나만 남긴다. 그래서 맨마지막 10이 남은것 이다.
    lt.unique();
    for( list<int>::iterator Iter = lt.begin(); Iter != lt.end(); ++Iter ){
        cout<< *Iter <<" ";
    }
    cout<<endl;
    cout<<endl;
    //----------------------------------------------------------------------------
 
    list<int> lt2;
    lt2.push_back(10);
    lt2.push_back(10);
    lt2.push_back(20);
    lt2.push_back(30);
    lt2.push_back(30);
    lt2.push_back(30);
    lt2.push_back(40);
    lt2.push_back(50);
    lt2.push_back(10);
 
    for( list<int>::iterator Iter = lt2.begin(); Iter != lt2.end(); ++Iter ){
        cout<< *Iter <<" "; //10 10 20 30 30 30 40 50 10
    }
    cout<<endl;
 
    // 2번 이항조건자를 이용한 unique() 함수 사용법
    lt2.unique(predicate);
 
    for( list<int>::iterator Iter = lt2.begin(); Iter != lt2.end(); ++Iter ){        
        cout<< *Iter <<" "; //10 20 30 40 50
    }
    cout<<endl;
 
    system("pause");
    return 0;
}

 

 

unique() 멤버 함수는 인접한 같은 원소를 유일하게 만듭니다. ( 단! 연속되지 않으면 중복될 수 있음 )

 

 

 

[ list의 sort() 멤버 함수 ]

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <list>
using namespace std;
 
struct Greater{
    
    bool operator() (int left, int right){
            return left > right; // 내림차순 > 연산
    }
};
 
int main(){
 
    list<int> lt;
    lt.push_back(20);
    lt.push_back(10);
    lt.push_back(50);
    lt.push_back(30);
    lt.push_back(40);
 
    list<int>::iterator Iter;
    for( Iter = lt.begin(); Iter != lt.end(); ++Iter ){
        cout<< *Iter <<" "; // 20 10 50 30 40
    }
    cout<<endl;
 
    // 1번 sort() 멤버함수 사용
    lt.sort(); // 디폴트 : 오름차순(less)정렬 ( < 연산 )
    for( Iter = lt.begin(); Iter != lt.end(); ++Iter ){
        cout<< *Iter <<" "; // 10 20 30 40 50
    }
    cout<<endl;
    cout<<endl;
    //---------------------------------------------------------------
    
    list<int> lt2;
    lt2.push_back(20);
    lt2.push_back(10);
    lt2.push_back(50);
    lt2.push_back(30);
    lt2.push_back(40);
    
    for( Iter = lt2.begin(); Iter != lt2.end(); ++Iter ){
        cout<< *Iter <<" ";
    }
    cout<<endl;
 
    // 2번 조건자사용 sort() 멤버함수 사용
    // 참 이면 두원소(left, right)를 바꾸지않고, 거짓이면 바뀜 
    lt2.sort(Greater());
 
    for( Iter = lt2.begin(); Iter != lt2.end(); ++Iter ){
        cout<< *Iter <<" ";
    }
    cout<<endl;
    
    system("pause");
    return 0;
}

 

정렬을 수행할 수 있는 컨테이너는 시퀀스 컨테이너( vector, deque, list ) 입니다.

연관 컨테이너는 자체 정렬 기준에 의해 자동정렬 됩니다.

 

vector와 deque은 알고리즘 함수 sort() 을 사용하여 정렬 할 수 있습니다.

하지만 list는 sort() 알고리즘을 수행할 수 없습니다.

 

sort() 알고리즘은 임의 접근 반복자( 대부분 quick sort로 구현됨 )를 지원하는 컨테이너만 사용 가능 하기 때문입니다.

그래서 list는 자체 정렬 멤버함수인 sort()를 제공합니다.

 

 

[ list의 merge() 멤버 함수 ]

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <list>
using namespace std;
 
int main(){
 
    list<int> lt1;
    lt1.push_back(10);
    lt1.push_back(20);
    lt1.push_back(30);
    lt1.push_back(40);
    lt1.push_back(50);
 
    list<int> lt2;
    lt2.push_back(25);
    lt2.push_back(35);
    lt2.push_back(45);    
 
 
    list<int>::iterator Iter;
    for( Iter = lt1.begin(); Iter != lt1.end(); ++Iter ){
        cout<< *Iter <<" "; // 10 20 30 40 50
    }
    cout<<endl;
 
    for( Iter = lt2.begin(); Iter != lt2.end(); ++Iter ){
        cout<< *Iter <<" "; // 25 35 45
    }
    cout<<endl<<"============================="<<endl;
 
    // 1번 merge() 멤버함수 사용
    // lt2를 lt1으로 합병 정렬. 정렬 기준은 less 오름차순
    // merge() 멤버함수는 lt1과 lt2가 오름차순 정렬되어있다고 가정하에 동작하며
    // 결과도 오름차순 정렬됩니다.
    lt1.merge(lt2); 
 
    for( Iter = lt1.begin(); Iter != lt1.end(); ++Iter ){
        cout<< *Iter <<" "; // 10 20 25 30 35 40 45 50
    }
    cout<<endl;
 
    if( lt2.empty() ){
        cout<<"비었음!!";
    }else{
        for( Iter = lt2.begin(); Iter != lt2.end(); ++Iter ){
            cout<< *Iter <<" ";
        }
    }    
    cout<<endl<<"============================="<<endl;
    cout<<endl;
 
    list<int> lt3;
    lt3.push_back(50);
    lt3.push_back(40);
    lt3.push_back(30);
    lt3.push_back(20);
    lt3.push_back(10);
 
    list<int> lt4;
    lt4.push_back(45);
    lt4.push_back(35);
    lt4.push_back(25);
 
    for( Iter = lt3.begin(); Iter != lt3.end(); ++Iter ){
        cout<< *Iter <<" "; // 50 40 30 20 10
    }
    cout<<endl;
 
    for( Iter = lt4.begin(); Iter != lt4.end(); ++Iter ){
        cout<< *Iter <<" "; // 45 35 25
    }
    cout<<endl<<"============================="<<endl;
 
    // 2번 이항 조건자 사용 merge()멤버함수 
    // lt3과 lt4의 정렬기준이 내림차순 같아야 한다. 아니면 오류
    // 두 list의 정렬기준이 greater( >  연산)라는 것을 predicate로 지정
    lt3.merge(lt4, greater<int>());
 
    for( Iter = lt3.begin(); Iter != lt3.end(); ++Iter ){
        cout<< *Iter <<" "; // 50 45 40 35 30 25 20 10
    }
    cout<<endl;
 
    if( lt4.empty() ){
        cout<<"비었음!!";
    }else{
        for( Iter = lt4.begin(); Iter != lt4.end(); ++Iter ){
            cout<< *Iter <<" ";
        }
    }
    cout<<endl;
 
    system("pause");
    return 0;
}

 

merge() 멤버 함수는 두 list를 합병합니다.

merge() 멤버 함수는 정렬된 두 list를 하나의 정렬된 list로 합병하므로 합병할 두 list는 정렬 되어 있어야 합니다.

 

만약 정렬 기준이 틀렸거나 합병할 list가 정렬돼 있지 않았다면 merge() 멤버 함수는 실패하며 오류가 발생합니다. 

반드시 정렬 되어 있어야 합니다. 

 

 

 

vector의 erase()와 list의 erase()의 차이점

: vector의 erase()는 제거하는 원소 다음의 모든 원소를 앞쪽으로 이동시켜야 하지만 list의 erase()는 제거하는 원소의 노드만 제거하면 됩니다.

 

vector의 insert()와 list의 insert()의 차이점

: erase()와 마찬가지로 vector의 insert()는 삽입하는 원소 다음의 모든 원소를 뒤쪽으로 이동시켜야 하지만, list의 erase()는 삽입하는 원소의 노드를 앞뒤로 연결하면 됩니다.

 

list의 insert() 멤버 함수와 splice() 멤버 함수의 차이점

: insert()는 원본(source)의 순차열에 변화가 없지만, splice()는 원본(source)의 순차열을 잘라내어 대상 순차열에 붙입니다.

저작자표시

'0x0001 > STL' 카테고리의 다른 글

[C++ STL] 연관 컨테이너 - 멀티셋(multiset)  (0) 2019.02.16
[C++ STL] 연관 컨테이너 - 셋(set)  (0) 2019.02.16
[C++ STL] 시퀀스 컨테이너 - 덱(deque)  (0) 2019.02.16
[C++ STL] 시퀀스 컨테이너 - 벡터(vector)  (0) 2019.02.16
[C++ STL] STL 구성요소( 컨테이너, 반복자, 알고리즘, 함수객체, 어댑터, 할당기 )  (0) 2019.02.16



deque 컨테이너는 vector 컨테이너와 기능과 동작이 가장 비슷한 컨테이너로 vector의 단점을 보완하는 몇 가지 특징을 갖습니다. deque도 vector 컨테이너와 같이 시퀀스 컨테이너이며 배열 기반 컨테이너 입니다.

 

※ 중요

deque이 vector와 다른 점은 메모리 블록 할당 정책입니다.

deque은 여러 개의 메모리 블록을 할당하고 사용자에게는 하나의 블록처럼 보이게 하는 정책을 사용합니다.

원소의 추가 시 메모리가 부족할때마다 일정한 크기의 새로운 메모리 블록을 할당하여 이전 메모리를 제거하거나 이전 원소를 복사하는 등의 연산을 수행하지 않습니다.

 

즉! vector 처럼 메모리가 부족하여, 새로운 메모리 블록을 만들고, 다시 원소를 복사하는 일은 없습니다.

 

[ deque 기본 생성 ]

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <deque>
using namespace std;
 
int main(){
 
    deque<int> dq;
    dq.push_back(10);
    dq.push_back(20);
    dq.push_back(30);
    dq.push_back(40);
    dq.push_back(50);
 
    deque<int>::iterator Iter = dq.begin();
    for( ; Iter != dq.end(); ++Iter ){
        cout<< *Iter <<endl;
    }
 
    system("pause");
    return 0;
}

 

 

[ deque의 push_front() ]

 

1
2
3
4
5
6
7
8
9
10
11
12
deque<int> dq;
dq.push_back(10);
dq.push_back(20);
dq.push_back(30);
dq.push_back(40);
dq.push_back(50);
 
dq.push_front(100);// 앞쪽에 추가합니다.
dq.push_front(200);    
for(deque<int>::size_type i = 0; i< dq.size(); ++i ){
    cout<< dq[i] <<endl;
}

 

deque은 원소를 앞쪽에 추가하면 새로운 메모리 블록을 할당하고 원소를 저장해 갑니다.

deque의 반복자는 vector의 반복자와 동일하게 동작합니다.

 

deque의 insert() 멤버함수는 vector보다 효율적으로 동작합니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <deque>
using namespace std;
 
int main(){
 
    deque<int> dq;
    dq.push_back(10);
    dq.push_back(20);
    dq.push_back(30);
    dq.push_back(40);
    dq.push_back(50);
 
    // 30을 가르킴
    deque<int>::iterator Iter = dq.begin()+2;
    deque<int>::iterator Iter_Insert = dq.insert(Iter, 100);
 
    for( Iter = dq.begin(); Iter != dq.end(); ++Iter ){
        cout<< *Iter <<" ";
    }
    cout<<endl;
    cout<< *Iter_Insert <<endl;
 
    system("pause");
    return 0;
}

 

위의 예제에서 Iter는 30을 가르키는데, Iter가 가리키는 위치보다 삽입할 원소(100)이 앞쪽에 삽입 됩니다.

블럭 -> 10, 20, 100, 30, 40 ( Iter를 기준으로 앞쪽 원소 2개, Iter를 포함한 뒤쪽원소는 3개 )

블럭 -> 50

 

이렇게 삽입되면 Iter가 가리키는 원소(100)의 앞쪽 원소 개수가 적기 때문에 앞쪽으로 밀어내며 삽입이 됩니다.

블럭 ->                 10 <- 메모리 할당

블럭 -> 20, 100, 30, 40

블럭 -> 50

 

deque의 erase() 멤버함수도 vector처럼 제거될 위치부터 모든 원소를 밀어내지만,

vector보다는 조금 더 효율적으로 동작합니다.

 

vector는 모든 원소를 뒤쪽으로만 밀어 내지만 deque은 뒤쪽이나 앞쪽으로 밀어낼 수 있기 때문입니다.

 

저작자표시

'0x0001 > STL' 카테고리의 다른 글

[C++ STL] 연관 컨테이너 - 셋(set)  (0) 2019.02.16
[C++ STL] 시퀀스 컨테이너 - 리스트(list)  (0) 2019.02.16
[C++ STL] 시퀀스 컨테이너 - 벡터(vector)  (0) 2019.02.16
[C++ STL] STL 구성요소( 컨테이너, 반복자, 알고리즘, 함수객체, 어댑터, 할당기 )  (0) 2019.02.16
[C++ STL] STL ( Standard Template Library ) 이란?  (0) 2019.02.16

+ Recent posts

티스토리툴바