비트 연산은 우선순위가 낮은 편이기 때문에 원하는 위치에 괄호를 작성하여 정확하게 계산할 수 있도록 하는게 중요하다.



C++에서 1은 부호있는 32비트 상수이기  때문에, 64비트를 사용할 때에는 1뒤에 ull을 붙여줘야 제대로 인식한다.


unsigned long long bit = (1ull<<40)-1; (O) -> 1099511627775


unsigned long long bit = (1<<40)-1; (X) -> 18446744073709551615



공집합( 모든 비트가 0)

unsigned int bit = 0;


꽉찬 집합(모든 비트가 1)


unsigned int bit = (1<<n) - 1;


사용할 비트 수만큼 왼쪽으로 시프트한 다음 1을 빼면 된다.


unsigned int bit = (1<<32) - 1; -> 1111 1111 1111 1111 1111 1111 1111 1111



기존 비트에서 원하는 비트의 위치를 1로 바꾸기

비트를 1로 바꿀 만큼 왼쪽으로 시프트 시킨 후 , or연산을 한다.

bit |= (1<<n);



특정 비트가 1인지 확인하기

if(bit & (1<<n)) -> 특정 비트가 1이면 1<<n 반환, 0이면 0 반환



기존 비트에서 원하는 비트의 위치를 0으로 바꾸기

bit &= ~(1<<n);


n번째 비트가 0이면 1로, 1이면 0으로 바꾸기

bit ^= (1<<n); -> xor 연산을 하면 가능하다.



비트에서 1의 개수 세기

1
2
3
4
5
6
int bitCount(int x)
{
    if (x == 0)
        return 0;
    return x % 2 + bitCount(x / 2);
}
cs



처음 1인 비트 찾기

int first = ( bit & -bit);

2^n의 값이 반환된다.

즉 10진수 240 은 1111 0000로, 처음 1은 4번째 비트에서 나타난다. 그러면 위 식에 의해 2^4 = 16의 값을 가지게 된다.


처음 1인 비트를 0으로 바꾸기


bit &= (bit -1);



모든 부분집합 탐색

처음 시작은 모든 비트가 1로 채워져있어야 한다.


1
2
3
4
for (int subset = a; subset; subset = ((subset - 1) & a))
    {
        
    }
cs



참고문헌: 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략

'컴퓨터공학 > 알고리즘' 카테고리의 다른 글

이진 탐색(Binary Search)  (0) 2018.08.08

1. 배열을 이용한 큐 구현


단순히 스택과 같이 큐를 배열을 이요하여 구현하면 아래와 같다.

문제점은 큐의 크기를 한번 다 사용하고 나면 큐는 실제로는 비어있지만 더이상 데이터를 삽입할 수가없다.

그렇기 때문에 배열을 이요할 때에는 원형 큐를 구현하게된다.




init: 큐 초기화

isEmpty: 큐가 비어있으면 1반환, 데이터가 있으면 0 반환

isFull: 큐가 가득 차있으면 1반환, 빈공간이 있으면 0반환

enqueue: 큐에 데이터 삽입

dequeue: 큐에서 데이터 추출


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
#include <stdio.h>
 
#define MAX_SIZE 10
 
typedef struct _queue {
    int data[MAX_SIZE];
    int front;
    int rear;
}queue;
 
void init(queue* q)
{
    q->front = 0;
    q->rear = 0;
}
int isEmpty(queue* q)
{
    if (q->front == q->rear)
        return 1;
    else
        return 0;
}
int isFull(queue* q)
{
    if (q->rear == MAX_SIZE)
        return 1;
    else
        return 0;
}
void enqueue(queue* q, int data)
{
    if (isFull(q))
    {
        printf("queue is full\n");
        return;
    }
 
    q->data[q->rear] = data;
    q->rear++;
}
int dequeue(queue* q)
{
    if (isEmpty(q))
    {
        printf("queue is empty\n");
        return -1;
    }
    
    return q->data[q->front++];
}
int seek(queue* q)
{
    if (isEmpty(q))
    {
        printf("queue is empty\n");
        return -1;
    }
    return q->data[q->front];
}
int main(void)
{
    queue q;
    init(&q);
    for (int i = 1; i <= 11; i++)
    {
        enqueue(&q, i * 10);
        printf("queue front : %d\n", seek(&q));
    }
    while (!isEmpty(&q))
        printf("dequeue data : %d \n", dequeue(&q));
    printf("queue front : %d\n", seek(&q));
    return 0;
}
 
cs


2. 배열을 이용한 원형 큐 구현


원형 큐의 경우, 배열을 지속적으로 사용할 수 있는 장점이 있다.

배열이 비어있는상태, 꽉차있는 상태를 구분하기 위해, 배열의 크기 - 1 만큼을 큐에서 사용한다.

front==rear인 경우 큐가 비어있는 상태이며, front-1 = rear인 경우 큐가 가득차 있는 상태이다.


isNext: 다음 인덱스를 가져오는 함수이다.


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
#include <stdio.h>
 
#define MAX_SIZE 10
 
typedef struct _queue {
    int data[MAX_SIZE];
    int front;
    int rear;
}queue;
 
void init(queue* q)
{
    q->front = 0;
    q->rear = 0;
}
int isEmpty(queue* q)
{
    if (q->front == q->rear)
        return 1;
    else
        return 0;
}
int isNext(int pos)
{
    if ( pos == MAX_SIZE-1)//마지막 인덱스면 첫번째로 돌아간다.
        return 0;
    else
        return pos + 1;
}
void enqueue(queue* q, int data)
{
    if (isNext(q->rear)==q->front)
    {
        printf("queue is full\n");
        return;
    }
    q->rear = isNext(q->rear);
    q->data[q->rear] = data;
}
int dequeue(queue* q)
{
    if (isEmpty(q))
    {
        printf("queue is empty\n");
        return -1;
    }
    q->front = isNext(q->front);
    return q->data[q->front];
}
int seek(queue* q)
{
    if (isEmpty(q))
    {
        printf("queue is empty\n");
        return -1;
    }
    return q->data[isNext(q->front)];
}
int main(void)
{
    queue q;
    init(&q);
    for (int i = 1; i <= 11; i++)
    {
        enqueue(&q, i * 10);
        printf("queue front : %d\n", seek(&q));
    }
    while (!isEmpty(&q))
        printf("dequeue data : %d \n", dequeue(&q));
    printf("queue front : %d\n", seek(&q));
    return 0;
}
 
cs


위 코드를 실행하면 아래와 같은 값이 나온다.

큐의 크기는 10이지만, 실제로 사용하는 영역은 9칸 이기 때문에, 11개의 데이터를 삽입하려고 시도하면 2번의 에러가 발생한다.




3. 리스트를 이용한 큐 구현


리스트를 사용할 경우, 데이터 삽입을 위해 리스트의 가장 마지막을 노드를 가르키는 포인터(여기서는 Tail)이 필요하다.

큐에서 데이터 삽입시 Tail 위치에 삽입하며, 삭제시 Head가 가르키는 노드를 삭제한다.




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
#include <stdio.h>
#include <stdlib.h>
 
typedef struct _node {
    int data;
    struct _node* next;
}node;
 
typedef struct _queue {
    node* head;
    node* tail;
}queue;
 
void init(queue* q)
{
    q->head = NULL;
    q->tail = NULL;
}
 
int isEmpty(queue* q)
{
    if (q->head == NULL)
        return 1;
    else
        return 0;
}
 
void enqueue(queue* q, int data)
{
    node* newnode = (node*)malloc(sizeof(node));
 
    newnode->data = data;
    newnode->next = NULL;
    
    if (isEmpty(q))
    {
        q->head = newnode;
        q->tail = newnode;
    }
    else
    {
        q->tail->next = newnode;
        q->tail = newnode;
    }
}
 
int dequeue(queue* q)
{
    if (isEmpty(q))
    {
        printf("queue is empty\n");
        return -1;
    }
 
    int ret = q->head->data;
    node* temp = q->head;
 
    q->head = temp->next;
    free(temp);
 
    return ret;
}
 
int seek(queue* q)
{
    if (isEmpty(q))
    {
        printf("queue is empty\n");
        return -1;
    }
    return q->head->data;
}
 
int main(void)
{
    queue q;
    init(&q);
 
    for (int i = 1; i <= 11; i++)
    {
        enqueue(&q, i * 10);
        printf("queue front : %d\n", seek(&q));
    }
 
    while(!isEmpty(&q))
        printf("dequeue data : %d \n", dequeue(&q));
 
    printf("queue front : %d\n", seek(&q));
 
    return 0;
}
 
 
cs


'컴퓨터공학 > 자료구조' 카테고리의 다른 글

스택(stack)  (0) 2018.08.09
1.2 포인터와 동적 메모리 할당  (0) 2015.07.19
1.1 시스템 생명 주기(System Life Cycle)  (0) 2015.07.19
C로 쓴 자료구조론  (0) 2015.07.19

1. 배열을 이용한 스택 구현


정해진 크기의 배열에서, 배열의 크기에 여유가 있으면 데이터를 하나씩 추가한다.



init: 스택을 초기화 하는 함수. top을 가르키는 변수를 -1로 초기화 한다.

isEmpty: 스택이 비어있는지 체크하는 함수. 비어있으면 1, 비어있지 않으면 0을 반환한다.

push: 스택에 데이터를 삽입하는 함수. 스택이 가득차 있으면 더이상 추가하지 않는다.

pop: 스택에서 데이터를 추출하는 함수. 스택의 top에 에있는 데이터를 반환한다. 스택이 비어있으면 꺼내지 않는다.

seek: 스택의 top에 저장된 데이터를 반환하는 함수. 없어도 되지만 책에 있어서 추가해봤다.


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
#include <stdio.h>
 
#define MAX_SIZE 10
 
typedef struct _stack {
    int data[MAX_SIZE];
    int top;
}stack;
 
void init(stack* st)
{
    st->top = -1;
}
 
int isEmpty(stack* st)
{
    if (st->top == -1)
        return 1;
    else
        return 0;
}
 
void push(stack* st, int data)
{
    if (st->top == MAX_SIZE-1)
    {
        printf("stack is full\n");
        return;
    }
 
    st->data[++st->top] = data;
}
 
int pop(stack* st)
{
    if (isEmpty(st))
    {
        printf("stack is empty\n");
        return -1;
    }
    return st->data[st->top--];
}
 
int seek(stack* st)
{
    if (isEmpty(st))
    {
        printf("stack is empty\n");
        return -1;
    }
    return st->data[st->top];
}
 
int main(void)
{
    stack st;
    init(&st);
 
    for (int i = 1; i <= 11; i++)
    {
        push(&st, i * 10);
        printf("stack top : %d\n", seek(&st));
    }
 
    while(!isEmpty(&st))
        printf("pop data : %d \n", pop(&st));
 
    printf("stack top : %d\n", seek(&st));
 
    return 0;
}
 
 
cs

예전에 TOP을 초기화할 땐 -1로 했던 것 같은데 요즘엔 0이 대세인 것 같기도하다.
하지만 큰 차이없으니 개인의 취향대로 구현하면 될 것이다.

2. 리스트를 이용한 스택 구현

리스트를 이용할 경우, 배열과 다른점은 top이라는 변수가 따로 없는 것이다. Head가 top과 유사한 역할을 수행한다.
또, 리스트는 제한된 크기가 없기때문에, 메모리가 허용하는 만큼의 데이터를 삽입할 수 있다.
데이터 삽입시 새로운 노드를 생성하고, 새로운 노드에 데이터 할당, NEXT는 HEAD가 가르키고 있던 노드를 할당한다.
그다음 HEAD는 새로운 노드를 가르키게 하면된다.




함수는 배열을 이용한 스택과 같다.


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
#include <stdio.h>
#include <stdlib.h>
 
typedef struct _node {
    int data;
    struct _node* next;
}node;
 
typedef struct _stack {
    node* head;
}stack;
 
void init(stack* st)
{
    st->head = NULL;
}
 
int isEmpty(stack* st)
{
    if (st->head == NULL)
        return 1;
    else
        return 0;
}
 
void push(stack* st, int data)
{
    node* newnode = (node*)malloc(sizeof(node));
    newnode->data = data;
    newnode->next = st->head;
    
    st->head = newnode;
}
 
int pop(stack* st)
{
    if (isEmpty(st))
    {
        printf("stack is empty\n");
        return -1;
    }
 
    int ret = st->head->data;
    node* temp = st->head;
 
    st->head = temp->next;
    free(temp);
 
    return ret;
}
 
int seek(stack* st)
{
    if (isEmpty(st))
    {
        printf("stack is empty\n");
        return -1;
    }
    return st->head->data;
}
 
int main(void)
{
    stack st;
    init(&st);
 
    for (int i = 1; i <= 11; i++)
    {
        push(&st, i * 10);
        printf("stack top : %d\n", seek(&st));
    }
 
    while(!isEmpty(&st))
        printf("pop data : %d \n", pop(&st));
 
    printf("stack top : %d\n", seek(&st));
 
    return 0;
}
 
 
cs


'컴퓨터공학 > 자료구조' 카테고리의 다른 글

큐(queue)  (0) 2018.08.09
1.2 포인터와 동적 메모리 할당  (0) 2015.07.19
1.1 시스템 생명 주기(System Life Cycle)  (0) 2015.07.19
C로 쓴 자료구조론  (0) 2015.07.19

이진 탐색 알고리즘은 정렬된 배열에서만 사용 가능하다.


아주 많은 데이터가 저장되어 있는 배열에서 순차탐색보다 효과적으로 값을 찾을 수 있다.


기본 원리는 배열에서 중간 위치를 기준으로  찾고자 하는 값이 더 작으면 중간 위치의 왼쪽에서 계속 탐색,

찾고자 하는 값이 더 크면 중간 위치보다 오른쪽에 있는 값들을 탐색하며,


다음 위치는 계속 남은 배열의 중간위치를 기준으로 탐색한다.



위 그림의 예시에서 1부터 10까지 저장된 배열에서 2를 찾을 것이다.


초기값으로 front = 0, rear = 9가 되며, mid = (0 + 9 ) / 2 = 4 를 가진다.


mid인덱스에서 가지고 있는 값은 5이므로, 찾고자 하는 숫자가 더 작다. 


그러므로 rear의 값을 mid - 1로 바꿔서 다시 탐색한다.


그러면 front = 0, rear = 3, mid = 1이 된다.


1번 인덱스는 2이므로, 찾고자하는 숫자와 일치하므로 이진 탐색을 종료한다.



반복문을 사용하는 방법과, 재귀호출을 통한 구현이 모두 가능하다.

일반적으로는 반복문을 사용해서 구현하면 된다.


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
//Binary Search
#include <stdio.h>
 
int binarySearchRecursion(int number[], int front, int rear, int target)
{
    int mid = (front + rear) / 2;
 
    if (front > rear)//배열에서 탐색하지 못함
    {
        return -1;
    }
 
    if (number[mid] == target)//찾은 경우
    {
        return mid;
    }
    else if (number[mid] < target)//찾고자 하는 값이 더 크므로 오른쪽 탐색
    {
        return binarySearchRecursion(number, mid + 1, rear, target);
    }
    else//찾고자 하는 값이 더 작으므로 왼쪽 탐색
    {
        return binarySearchRecursion(number, front, mid - 1, target);
    }
}
 
int binarySearchIteration(int number[], int size, int target)
{
    int front = 0;
    int rear = size-1;
    int mid;
 
    while (front <= rear)
    {
        mid = (front + rear) / 2;
        if (number[mid] == target)//찾은 경우
        {
            return mid;
        }
 
        if (number[mid] < target)
        {//찾는 값이 더 크므로 mid를 기준으로 오른쪽 탐색
            front = mid + 1;
        }
        else // if(number[mid] > target)
        {//찾는 값이 더 작으므로 mide를 기준으로 왼쪽 탐색
            rear = mid - 1;
        }
    }
    //찾지 못하고 while문이 종료되면 실패 반환
    return -1;
}
 
int main(void)
{
    int number[200];
 
    for (int i = 0; i < 200; i++)
        number[i] = i + 1;
 
    int findNum = 201;
 
    printf("Binary Search Iterative\n");
    int index = binarySearchIteration(number, sizeof(number) / sizeof(int), findNum);
    if(index!=-1)
        printf("NUM : %d = %d index\n", findNum, index);
    else
        printf("NUM : %d is not exist\n", findNum);
 
    printf("Binary Search Recursive\n");
    index = binarySearchRecursion(number, 0, (sizeof(number) / sizeof(int)) - 1, findNum);
    if (index != -1)
        printf("NUM : %d = %d index\n", findNum, index);
    else
        printf("NUM : %d is not exist\n", findNum);
 
    return 0;
}
cs


'컴퓨터공학 > 알고리즘' 카테고리의 다른 글

비트연산  (0) 2018.08.10

C++ algorithm


기타 algorithm에 속한 다른 함수들을 알아본다.


1. sort(begin, end)

구간 [begin, end)를 오름차순 기준으로 정렬한다


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
#include <iostream>     // std::cout
#include <algorithm>    // std::sort
#include <vector>       // std::vector
#include <functional>
 
bool myfunction(int i, int j) { return (i>j); }
 
struct myclass {
    bool operator() (int i, int j) { return (i<j); }
} myobject;
 
int main() {
    int myints[] = { 32,71,12,45,26,80,53,33 };
    std::vector<int> myvector(myints, myints + 8);               // 32 71 12 45 26 80 53 33
 
                                                                 // using default comparison (operator <):
    std::sort(myvector.begin(), myvector.end());               //(12 26 32 33 45 53 71 80)
    std::cout << "myvector contains:";
    for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';
 
 
                                                                 // using function as comp
    std::sort(myvector.begin(), myvector.end(), myfunction);     // (80 71 53 45 33 32 26 12)
    std::cout << "myvector contains:";
    for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';
 
                                                                 // using object as comp
    std::sort(myvector.begin(), myvector.end(), myobject);       //(12 26 32 33 45 53 71 80)
 
                                                               // print out content:
    std::cout << "myvector contains:";
    for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';
 
                                                                        // using function as greater
    std::sort(myvector.begin(), myvector.end(), std::greater<int>());    // (80 71 53 45 33 32 26 12)
    std::cout << "myvector contains:";
    for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';
 
    return 0;
}
cs



기본은 오름차순 정렬이며

내림차순으로 정렬하기 위햇서는 비교 함수를 구현하거나

<functional> 헤더를 추가하여 41번째 줄과 같이 std::greater<int>() 를 이용해서 비교하면 내림차순으로 정렬할 수 있다.


2. stable_sort(begin, end)

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
#include <iostream>     // std::cout
#include <algorithm>    // std::stable_sort
#include <vector>       // std::vector
 
bool compare_as_ints(double i, double j)
{
    return (int(i)<int(j));
}
 
int main() {
    double mydoubles[] = { 3.14, 1.41, 2.72, 4.67, 1.73, 1.32, 1.62, 2.58 };
 
    std::vector<double> myvector;
 
    myvector.assign(mydoubles, mydoubles + 8);
 
    std::cout << "using default comparison:";
    std::stable_sort(myvector.begin(), myvector.end());
    for (std::vector<double>::iterator it = myvector.begin(); it != myvector.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';
 
    myvector.assign(mydoubles, mydoubles + 8);
 
    std::cout << "using 'compare_as_ints' :";
    std::stable_sort(myvector.begin(), myvector.end(), compare_as_ints);
    for (std::vector<double>::iterator it = myvector.begin(); it != myvector.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';
 
    return 0;
}
cs


위 예제에서 비교 연산자없이 stable_sort를 호출하면, 오름차순으로 정렬된다.

하지만 비교 조건으로 int로 변환했을 때(정수부의 값이)를 기준으로 오름차순 정렬하도록 조건을 주었다.

이런 경우 1.41 1.73 1.32 1.62가 모두 1의 값을 가지게 되는데, 이럴 때, 원래 가지고 있던 순서 그대로 위치하게 된다.



3. binary_search(begin, end, value)

정렬된 구간 [begin, end)에서 이진 탐색으로 value를 찾으면 true반환, 못찾으면 false를 반환한다.

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>     // std::cout
#include <algorithm>    // std::binary_search, std::sort
#include <vector>       // std::vector
 
bool myfunction(int i, int j) { return (i<j); }
 
int main() {
    int myints[] = { 1,2,3,4,5,4,3,2,1 };
    std::vector<int> v(myints, myints + 9);                         // 1 2 3 4 5 4 3 2 1
 
                                                                    // using default comparison:
    std::sort(v.begin(), v.end());
 
    std::cout << "looking for a 3... ";
    if (std::binary_search(v.begin(), v.end(), 3))
        std::cout << "found!\n"; else std::cout << "not found.\n";
 
    // using myfunction as comp:
    std::sort(v.begin(), v.end(), myfunction);
 
    std::cout << "looking for a 6... ";
    if (std::binary_search(v.begin(), v.end(), 6, myfunction))
        std::cout << "found!\n"; else std::cout << "not found.\n";
 
    return 0;
}
cs



4. lower_bound(begin, end, value) 

구간 [begin, end)에서 value보다 작지 않은 첫 번째 이터레이터 반환


5. upper_bound(begin, end, value)

구간 [begin, end)에서 value보다 큰 첫 번째 이터레이터 반환


사용 예제

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>     // std::cout
#include <algorithm>    // std::lower_bound, std::upper_bound, std::sort
#include <vector>       // std::vector
 
int main() {
    int myints[] = { 10,20,30,30,20,10,10,20 };
    std::vector<int> v(myints, myints + 8);           // 10 20 30 30 20 10 10 20
 
    std::sort(v.begin(), v.end());                // 10 10 10 20 20 20 30 30
 
    std::vector<int>::iterator low, up;
    low = std::lower_bound(v.begin(), v.end(), 20); //          ^
    up = std::upper_bound(v.begin(), v.end(), 20); //                   ^
 
    std::cout << "lower_bound at position " << (low - v.begin()) << '\n';
    std::cout << "upper_bound at position " << (up - v.begin()) << '\n';
 
    return 0;
}
cs



6. next_permutation(begin, end)

구간 [begin, end)를 순열로 보았을 때, 사전 순으로 다음에 오는 순열을 만든다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>     // std::cout
#include <algorithm>    // std::next_permutation, std::sort
 
int main() {
    int myints[] = { 1,2,3 };
 
    std::sort(myints, myints + 3);
 
    std::cout << "The 3! possible permutations with 3 elements:\n";
    do {
        std::cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
    } while (std::next_permutation(myints, myints + 3));
 
    std::cout << "After loop: " << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
 
    return 0;
}
cs



7. heap

make_heap: 힙을 생성한다. (최대힙)

push_heap: 힙에 원소를 추가한다.

pop_heap: 힙에서 원소를 제거한다.

sort_heap: 힙을 정렬한다. 



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>     // std::cout
#include <algorithm>    // std::make_heap, std::pop_heap, std::push_heap, std::sort_heap
#include <vector>       // std::vector
 
int main() {
    int myints[] = { 10,20,30,5,15 };
    std::vector<int> v(myints, myints + 5);
 
    std::make_heap(v.begin(), v.end());
    std::cout << "initial max heap   : " << v.front() << '\n';
 
    std::pop_heap(v.begin(), v.end()); v.pop_back();
    std::cout << "max heap after pop : " << v.front() << '\n';
 
    v.push_back(99); std::push_heap(v.begin(), v.end());
    std::cout << "max heap after push: " << v.front() << '\n';
 
    std::sort_heap(v.begin(), v.end());
 
    std::cout << "final sorted range :";
    for (unsigned i = 0; i<v.size(); i++)
        std::cout << ' ' << v[i];
 
    std::cout << '\n';
 
    return 0;
}
cs




참조: http://www.cplusplus.com/reference/algorithm/

참고문헌: 뇌를 자극하는 C++ STL

'컴퓨터공학 > STL' 카테고리의 다른 글

[STL] C++ STL algorithm2  (0) 2018.07.30
[STL] C++ STL algorithm1  (0) 2018.07.30
[STL] C++ STL multimap  (0) 2018.07.22
[STL] C++ STL map  (0) 2018.07.22
[STL] C++ STL multiset  (0) 2018.07.22

C++ algorithm


이번 글에서는 원소를 수정하는 알고리즘에서 몇가지를 알아본다.



1. fill(begin, end, value)

구간 [begin, end)를 value로 채운다.


fill 사용 예제

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>     // std::cout
#include <algorithm>    // std::fill
#include <vector>       // std::vector
 
int main() {
    std::vector<int> myvector(8);                       // myvector: 0 0 0 0 0 0 0 0
 
    std::fill(myvector.begin(), myvector.begin() + 4, 5);   // myvector: 5 5 5 5 0 0 0 0
    std::fill(myvector.begin() + 3, myvector.end() - 2, 8);   // myvector: 5 5 5 8 8 8 0 0
 
    std::cout << "myvector contains:";
    for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';
 
    return 0;
}
cs



2. reverse(begin, end)

구간 [begin, end)의 순서를 역순으로 만든다.


reverse 사용 예제

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>     // std::cout
#include <algorithm>    // std::reverse
#include <vector>       // std::vector
 
int main() {
    std::vector<int> myvector;
 
    // set some values:
    for (int i = 1; i<10; ++i) myvector.push_back(i);   // 1 2 3 4 5 6 7 8 9
 
    std::reverse(myvector.begin(), myvector.end());    // 9 8 7 6 5 4 3 2 1
 
                                                       // print out content:
    std::cout << "myvector contains:";
    for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';
 
    return 0;
}
cs



3. rotate(begin, mid, end)

구간 [begin, end)를 mid를 기준으로 왼쪽으로 회전시킨다. 

즉, begin에는 mid값이 들어가고, end-1에는 mid-1의 값이 들어간다.


rotate 사용 예제

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>     // std::cout
#include <algorithm>    // std::rotate
#include <vector>       // std::vector
 
int main() {
    std::vector<int> myvector;
 
    // set some values:
    for (int i = 1; i<10; ++i) myvector.push_back(i); // 1 2 3 4 5 6 7 8 9
 
    std::rotate(myvector.begin(), myvector.begin() + 3, myvector.end());
    // 4 5 6 7 8 9 1 2 3
    // print out content:
    std::cout << "myvector contains:";
    for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';
 
    return 0;
}
cs



4. swap(a, b)

a와 b에 위치한 값을 바꾼다.


swap 사용 예제

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>     // std::cout
#include <algorithm>    // std::swap
#include <vector>       // std::vector
 
int main() {
 
    int x = 10, y = 20;                              // x:10 y:20
    std::swap(x, y);                              // x:20 y:10
 
    std::vector<int> foo(4, x), bar(6, y);       // foo:4x20 bar:6x10
    std::swap(foo, bar);                          // foo:6x10 bar:4x20
 
    std::cout << "foo contains:";
    for (std::vector<int>::iterator it = foo.begin(); it != foo.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';
 
    return 0;
}
cs



5. unique(begin, end)

구간 [begin, end)에서 연속되는 같은 값 하나를 제외하고 제거

제거는 하지만 컨테이너의 크기를 줄이지는 않는다. (아래 예제에서 15번째 줄을 보면 제거한 뒤 쪽 공간은 남아있다)

제거한 뒤 end 이터레이터를 반환한다. (그래서 18번째 줄을 보면 end까지 벡터의 크기를 변경한다)


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
#include <iostream>     // std::cout
#include <algorithm>    // std::unique, std::distance
#include <vector>       // std::vector
 
bool myfunction(int i, int j) {
    return (i == j);
}
 
int main() {
    int myints[] = { 10,20,20,20,30,30,20,20,10 };           // 10 20 20 20 30 30 20 20 10
    std::vector<int> myvector(myints, myints + 9);
 
    // using default comparison:
    std::vector<int>::iterator it;
    it = std::unique(myvector.begin(), myvector.end());   // 10 20 30 20 10 ?  ?  ?  ?
                                                          //                ^
 
    myvector.resize(std::distance(myvector.begin(), it)); // 10 20 30 20 10
 
                                                          // using predicate comparison:
    std::unique(myvector.begin(), myvector.end(), myfunction);   // (no changes)
 
                                                                 // print out content:
    std::cout << "myvector contains:";
    for (it = myvector.begin(); it != myvector.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';
 
    return 0;
}
cs



참조: http://www.cplusplus.com/reference/algorithm/

참고문헌: 뇌를 자극하는 C++ STL

'컴퓨터공학 > STL' 카테고리의 다른 글

[STL] C++ STL algorithm3  (0) 2018.07.30
[STL] C++ STL algorithm1  (0) 2018.07.30
[STL] C++ STL multimap  (0) 2018.07.22
[STL] C++ STL map  (0) 2018.07.22
[STL] C++ STL multiset  (0) 2018.07.22

C++ algorithm


알고리즘 시험 볼 때 유용하게 사용할 수 있는 STL이다.


레퍼런스 사이트에서 보면 각 함수들을 9가지 종류로 분류해 놓았다. 


이번 글에서는 그중 원소를 수정하지 않는 알고리즘(Non-modifying sequence) 중 몇가지를 알아본다.



1. count(begin, end, value) 

구간 [begin, end)에서 value의 원소 개수를 찾는다.


2. count_if(begin, end, f)

구간 [begin, end)에서 f 조건에 맞는 원소 개수를 찾는다.


count / count_if 예제


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>     // std::cout
#include <algorithm>    // std::count
#include <vector>       // std::vector
 
int main() {
    // counting elements in array:
    int myints[] = { 10,20,30,30,20,10,10,20 };   // 8 elements
    int mycount = std::count(myints, myints + 8, 10); //10의 개수
    std::cout << "10 appears " << mycount << " times.\n";
 
    // counting elements in container:
    std::vector<int> myvector(myints, myints + 8);
    mycount = std::count(myvector.begin(), myvector.end(), 20); //20의 개수
    std::cout << "20 appears " << mycount << " times.\n";
 
    mycount = count_if(myvector.begin(), myvector.end(), [](int x) { return (x / 10) % 2 == 0; });//십의 자리 숫자가 짝수인 수의 개수
    std::cout << "myvector contains " << mycount << "\n";
 
    return 0;
}
cs




3. find(begin, end, value)

구간 [begin, end)에서 value와 같은 첫 번째 이터레이터를 찾는다.


4. find_if(begin, end, f)

구간 [begin, end)에서 f 조건에 해당하는 첫 번째 이터레이터


찾지 못하면 end를 반환


find / find_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
// find_if example
#include <iostream>     // std::cout
#include <algorithm>    // std::find_if
#include <vector>       // std::vector
 
int main() {
    std::vector<int> myvector;
 
    myvector.push_back(10);
    myvector.push_back(25);
    myvector.push_back(40);
    myvector.push_back(55);
 
    std::vector<int>::iterator it;
 
    it = find(myvector.begin(), myvector.end(), 40);
    if (it != myvector.end())
        std::cout << "Element found in myvector: " << *it << '\n';
    else
        std::cout << "Element not found in myvector\n";
 
 
    it = find(myvector.begin(), myvector.end(), 100);
    if (it != myvector.end())
        std::cout << "Element found in myvector: " << *it << '\n';
    else
        std::cout << "Element not found in myvector\n";
 
    it = std::find_if(myvector.begin(), myvector.end(), [](int x) { return x % 2 == 1; });
    std::cout << "The first odd value is " << *it << '\n';
 
    return 0;
}
cs





5. max(a, b)

a와 b 중 더 큰 값 반환


6. min(a, b)

a와 b 중 더 작은 값 반환


max / min 사용 예제

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>     // std::cout
#include <algorithm>    // std::min / std::max
 
int main() {
    std::cout << "max(1,2)==" << std::max(1, 2) << '\n';
    std::cout << "max(2,1)==" << std::max(2, 1) << '\n';
    std::cout << "max('a','z')==" << std::max('a', 'z') << '\n';
    std::cout << "max(3.14,2.72)==" << std::max(3.14, 2.72) << "\n\n";
 
 
    std::cout << "min(1,2)==" << std::min(1, 2) << '\n';
    std::cout << "min(2,1)==" << std::min(2, 1) << '\n';
    std::cout << "min('a','z')==" << std::min('a', 'z') << '\n';
    std::cout << "min(3.14,2.72)==" << std::min(3.14, 2.72) << '\n';
    return 0;
}
cs



7. min_element / max_element

구간 [begin, end)에서 최소/최대값의 이터레이터를 반환한다.


참조: http://www.cplusplus.com/reference/algorithm/

참고문헌: 뇌를 자극하는 C++ STL

'컴퓨터공학 > STL' 카테고리의 다른 글

[STL] C++ STL algorithm3  (0) 2018.07.30
[STL] C++ STL algorithm2  (0) 2018.07.30
[STL] C++ STL multimap  (0) 2018.07.22
[STL] C++ STL map  (0) 2018.07.22
[STL] C++ STL multiset  (0) 2018.07.22

C++ multimap


multimap을 사용하기 위해서는 <map>을 인클루드 해야한다.


map에서 중복된 key가 가능하다는 차이점 외에는 다 같다.  라고 책에는 나와있는데 multimap은 중복된 key를 허용하기 때문에, 앞서 map과는 다르게 [] 사용시 multimap에서는 오류가 발생한다. 이 차이점 외에는 다 같은것이 맞는 것 같다.


생성자 사용 예제

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
#include <iostream>
#include <map>
#include <functional>
 
int main()
{
    std::multimap<char, int> first;
 
    first.insert(std::pair<char, int>('a', 10));
    first.insert(std::pair<char, int>('b', 30));
    first.insert(std::pair<char, int>('c', 50));
    first.insert(std::pair<char, int>('d', 70));
 
    std::multimap<char, int> second(first.begin(), first.end());
 
    std::multimap<char, int> third(second);
 
    std::multimap<char, int, std::greater<int> > fourth = { { 'a', 10 },{ 'b', 30 },{ 'c', 50 },{ 'd', 70 } };
    
    std::cout << "first : ";
    for (auto it = first.begin(); it != first.end(); it++)
        std::cout << (*it).first << ' ' << (*it).second << ' ';
    std::cout << '\n';
 
    std::cout << "second : ";
    for (auto it = second.begin(); it != second.end(); it++)
        std::cout << (*it).first << ' ' << (*it).second << ' ';
    std::cout << '\n';
 
    std::cout << "third : ";
    for (auto it = third.begin(); it != third.end(); it++)
        std::cout << (*it).first << ' ' << (*it).second << ' ';
    std::cout << '\n';
 
    std::cout << "fourth : ";
    for (auto it = fourth.begin(); it != fourth.end(); it++)
        std::cout << (*it).first << ' ' << (*it).second << ' ';
    std::cout << '\n';
 
    return 0;
}
 
cs


실행 결과


멤버 함수 사용 예제

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
#include <iostream>
#include <map>
 
int main ()
{
  std::multimap<char,int> mymultimap;
  std::multimap<char,int>::iterator it;
 
  // first insert function version (single parameter):
  mymultimap.insert ( std::pair<char,int>('a',100) );
  mymultimap.insert ( std::pair<char,int>('z',150) );
  it=mymultimap.insert ( std::pair<char,int>('b',75) );
 
  // second insert function version (with hint position):
  mymultimap.insert (it, std::pair<char,int>('c',300));  // max efficiency inserting
  mymultimap.insert (it, std::pair<char,int>('z',400));  // no max efficiency inserting
 
  // third insert function version (range insertion):
  std::multimap<char,int> anothermultimap;
  anothermultimap.insert(mymultimap.begin(),mymultimap.find('c'));
 
  // showing contents:
  std::cout << "mymultimap contains:\n";
  for (it=mymultimap.begin(); it!=mymultimap.end(); ++it)
    std::cout << (*it).first << " => " << (*it).second << '\n';
 
  std::cout << "anothermultimap contains:\n";
  for (it=anothermultimap.begin(); it!=anothermultimap.end(); ++it)
    std::cout << (*it).first << " => " << (*it).second << '\n';
 
  return 0;
}
cs


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
#include <iostream>
#include <map>
 
int main ()
{
  std::multimap<char,int> mymultimap;
 
  // insert some values:
  mymultimap.insert(std::pair<char,int>('a',10));
  mymultimap.insert(std::pair<char,int>('b',20));
  mymultimap.insert(std::pair<char,int>('b',30));
  mymultimap.insert(std::pair<char,int>('c',40));
  mymultimap.insert(std::pair<char,int>('d',50));
  mymultimap.insert(std::pair<char,int>('d',60));
  mymultimap.insert(std::pair<char,int>('e',70));
  mymultimap.insert(std::pair<char,int>('f',80));
 
  std::multimap<char,int>::iterator it = mymultimap.find('b');
 
  mymultimap.erase (it);                     // erasing by iterator (1 element)
 
  mymultimap.erase ('d');                    // erasing by key (2 elements)
 
  it=mymultimap.find ('e');
  mymultimap.erase ( it, mymultimap.end() ); // erasing by range
 
  // show content:
  for (it=mymultimap.begin(); it!=mymultimap.end(); ++it)
    std::cout << (*it).first << " => " << (*it).second << '\n';
 
  return 0;
}
cs


count()

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
#include <iostream>
#include <map>
 
int main ()
{
  std::multimap<char,int> mymm;
 
  mymm.insert(std::make_pair('x',50));
  mymm.insert(std::make_pair('y',100));
  mymm.insert(std::make_pair('y',150));
  mymm.insert(std::make_pair('y',200));
  mymm.insert(std::make_pair('z',250));
  mymm.insert(std::make_pair('z',300));
 
  for (char c='x'; c<='z'; c++)
  {
    std::cout << "There are " << mymm.count(c) << " elements with key " << c << ":";
    std::multimap<char,int>::iterator it;
    for (it=mymm.equal_range(c).first; it!=mymm.equal_range(c).second; ++it)
      std::cout << ' ' << (*it).second;
    std::cout << '\n';
  }
 
  return 0;
}
cs



참조: http://www.cplusplus.com/reference/map/multimap/

참고문헌: 뇌를 자극하는 C++ STL

'컴퓨터공학 > STL' 카테고리의 다른 글

[STL] C++ STL algorithm2  (0) 2018.07.30
[STL] C++ STL algorithm1  (0) 2018.07.30
[STL] C++ STL map  (0) 2018.07.22
[STL] C++ STL multiset  (0) 2018.07.22
[STL] C++ STL set  (0) 2018.07.22

C++ map


map을 사용하기 위해서는 <map 헤더를 인클루드 해야한다.


key와 value를 쌍으로 저장한다.


set과 마찬가지로 key를 중복으로 저장할 수 없으며, 중복된 key를 이용하려면 multimap을 이용하면 된다.


map은 []연산자를 이용하여 key에 접근할 수 있다.


map은 pair객체로 원소를 저장하기 때문에, 첫번째 key는 first로 두번째 value는 second로 접근할 수 있다.


생성자 사용 예제

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 <map>
#include <functional>
 
int main()
{
    std::map<char, int> first;
 
    first['a'] = 10;
    first['b'] = 30;
    first['c'] = 50;
    first['d'] = 70;
 
    std::map<char, int> second(first.begin(), first.end());
 
    std::map<char, int> third(second);
 
    std::map<char, int, std::greater<int> > fourth = { {'a', 10}, {'b', 30}, {'c', 50}, {'d', 70} }; 
 
    std::cout << "first : ";
    for (auto it = first.begin(); it != first.end(); it++)
        std::cout << (*it).first << ' ' << (*it).second << ' ';
    std::cout << '\n';
 
    std::cout << "second : ";
    for (auto it = second.begin(); it != second.end(); it++)
        std::cout << (*it).first << ' ' << (*it).second << ' ';
    std::cout << '\n';
 
    std::cout << "third : ";
    for (auto it = third.begin(); it != third.end(); it++)
        std::cout << (*it).first << ' ' << (*it).second << ' ';
    std::cout << '\n';
 
    std::cout << "fourth : ";
    for (auto it = fourth.begin(); it != fourth.end(); it++)
        std::cout << (*it).first << ' ' << (*it).second << ' ';
    std::cout << '\n';
 
    return 0;
}
cs


실행 결과


멤버함수 사용 예제

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
#include <iostream>
#include <map>
 
int main()
{
    std::map<char, int> mymap;
 
    // first insert function version (single parameter):
    mymap.insert(std::pair<char, int>('a', 100));
    mymap.insert(std::pair<char, int>('z', 200));
 
    std::pair<std::map<char, int>::iterator, bool> ret;
    ret = mymap.insert(std::pair<char, int>('z', 500));
    if (ret.second == false) {
        std::cout << "element 'z' already existed";
        std::cout << " with a value of " << ret.first->second << '\n';
    }
 
    // second insert function version (with hint position):
    std::map<char, int>::iterator it = mymap.begin();
    mymap.insert(it, std::pair<char, int>('b', 300));  // max efficiency inserting
    mymap.insert(it, std::pair<char, int>('c', 400));  // no max efficiency inserting
 
                                                       // third insert function version (range insertion):
    std::map<char, int> anothermap;
    anothermap.insert(mymap.begin(), mymap.find('c'));
 
    // showing contents:
    std::cout << "mymap contains:\n";
    for (it = mymap.begin(); it != mymap.end(); ++it)
        std::cout << it->first << " => " << it->second << '\n';
 
    std::cout << "anothermap contains:\n";
    for (it = anothermap.begin(); it != anothermap.end(); ++it)
        std::cout << it->first << " => " << it->second << '\n';
 
    return 0;
}
cs


find(), 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
#include <iostream>
#include <map>
 
int main ()
{
  std::map<char,int> mymap;
  std::map<char,int>::iterator it;
 
  // insert some values:
  mymap['a']=10;
  mymap['b']=20;
  mymap['c']=30;
  mymap['d']=40;
  mymap['e']=50;
  mymap['f']=60;
 
  it=mymap.find('b');
  mymap.erase (it);                   // erasing by iterator
 
  mymap.erase ('c');                  // erasing by key
 
  it=mymap.find ('e');
  mymap.erase ( it, mymap.end() );    // erasing by range
 
  // show content:
  for (it=mymap.begin(); it!=mymap.end(); ++it)
    std::cout << it->first << " => " << it->second << '\n';
 
  return 0;
}
cs


count()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <map>
 
int main ()
{
  std::map<char,int> mymap;
  char c;
 
  mymap ['a']=101;
  mymap ['c']=202;
  mymap ['f']=303;
 
  for (c='a'; c<'h'; c++)
  {
    std::cout << c;
    if (mymap.count(c)>0)
      std::cout << " is an element of mymap.\n";
    else 
      std::cout << " is not an element of mymap.\n";
  }
 
  return 0;
}
cs


참조: http://www.cplusplus.com/reference/map/map/

참고문헌: 뇌를 자극하는 C++ STL

'컴퓨터공학 > STL' 카테고리의 다른 글

[STL] C++ STL algorithm1  (0) 2018.07.30
[STL] C++ STL multimap  (0) 2018.07.22
[STL] C++ STL multiset  (0) 2018.07.22
[STL] C++ STL set  (0) 2018.07.22
[STL] C++ STL string to int/float/double/long long  (0) 2018.07.19

C++ multiset


multiset을 사용하기 위해서는 <set> 헤더를 인클루드 해야한다.


중복된 데이터를 사용할 수 있는 것 외에는 set과 모두 같다.




 생성자

 

 set s

 빈 컨테이너 셋 s 생성

 set s(pred)

 s는 빈 컨테이너 이며, 정렬 기준은 pred 조건자를 사용

 set s(s2)

 셋 s는 셋 s2의 복사본

 set s(b, e)

 셋 s는 반복자 구간 [b, e)로 초기화된 원소를 가짐

 set s(b, e, pred)

 셋 s는 반복자 구간 [b, e)로 초기화된 원소를 가지며, 정렬 기준은 pred 조건자를 사용


생성자 사용 예제



#include <iostream>
#include <set>
#include <functional>
int main()
{
    std::multiset<int> first;                           // empty set of ints
 
    int myints[] = { 10, 20, 30, 40, 50, 20, 30, 40, 50, 60 };
    std::multiset<int> second(myints, myints + 10);        // range
 
    std::multiset<int> third(second);                  // a copy of second
 
    std::multiset<int> fourth(second.begin(), second.end());  // iterator ctor.
 
    std::multiset<int, std::greater<int> > fifth = { 10, 20, 30, 40, 50, 20, 30, 40, 50, 60 };
 
    std::cout << "first : ";
    for (auto it = first.begin(); it != first.end(); it++)
        std::cout << *it << ' ';
    std::cout << '\n';
 
    std::cout << "second : ";
    for (auto it = second.begin(); it != second.end(); it++)
        std::cout << *it << ' ';
    std::cout << '\n';
 
    std::cout << "third : ";
    for (auto it = third.begin(); it != third.end(); it++)
        std::cout << *it << ' ';
    std::cout << '\n';
 
    std::cout << "fourth : ";
    for (auto it = fourth.begin(); it != fourth.end(); it++)
        std::cout << *it << ' ';
    std::cout << '\n';
 
    std::cout << "fifth : ";
    for (auto it = fifth.begin(); it != fifth.end(); it++)
        std::cout << *it << ' ';
    std::cout << '\n';
 
    return 0;
}
cs


실행 결과




주요 멤버 함수

insert() 

 셋에 데이터 삽입

 erase()

 셋에서 원소 제거

 find()

 셋에서 원소의 위치 검색

 count()

 셋에서 원소의 개수 검색

 clear()

 셋의 모든 원소 제거


사용예제

insert()


#include <iostream>
#include <set>
 
int main()
{
    std::multiset<int> mymultiset;
    std::multiset<int>::iterator it;
 
    // set some initial values:
    for (int i = 1; i <= 5; i++) mymultiset.insert(i * 10);  // 10 20 30 40 50
 
    it = mymultiset.insert(25);
 
    it = mymultiset.insert(it, 27);    // max efficiency inserting
    it = mymultiset.insert(it, 29);    // max efficiency inserting
    it = mymultiset.insert(it, 24);    // no max efficiency inserting (24<29)
 
    int myints[] = { 5,10,15 };
    mymultiset.insert(myints, myints + 3);
 
    std::cout << "mymultiset contains:";
    for (it = mymultiset.begin(); it != mymultiset.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';
 
    return 0;
}
cs



erase(), find()


#include <iostream>
#include <set>
 
int main ()
{
  std::multiset<int> mymultiset;
  std::multiset<int>::iterator it;
 
  // insert some values:
  mymultiset.insert (40);                            // 40
  for (int i=1; i<7; i++) mymultiset.insert(i*10);   // 10 20 30 40 40 50 60
 
  it=mymultiset.begin();
  it++;                                              //    ^
 
  mymultiset.erase (it);                             // 10 30 40 40 50 60
 
  mymultiset.erase (40);                             // 10 30 50 60
 
  it=mymultiset.find (50);
  mymultiset.erase ( it, mymultiset.end() );         // 10 30
 
  std::cout << "mymultiset contains:";
  for (it=mymultiset.begin(); it!=mymultiset.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';
 
  return 0;
}
cs


count()


#include <iostream>
#include <set>
 
int main ()
{
  int myints[]={10,73,12,22,73,73,12};
  std::multiset<int> mymultiset (myints,myints+7);
 
  std::cout << "73 appears " << mymultiset.count(73) << " times in mymultiset.\n";
 
  return 0;
}
cs



참조: http://www.cplusplus.com/reference/set/multiset/

참고문헌: 뇌를 자극하는 C++ STL

'컴퓨터공학 > STL' 카테고리의 다른 글

[STL] C++ STL multimap  (0) 2018.07.22
[STL] C++ STL map  (0) 2018.07.22
[STL] C++ STL set  (0) 2018.07.22
[STL] C++ STL string to int/float/double/long long  (0) 2018.07.19
[STL] C++ STL list  (0) 2018.07.19

+ Recent posts

티스토리툴바