Hoit Studio

map과 multimap은 '연관 컨테이너'입니다. 모든 연관 컨테이너(set, multiset, map, multimap)는 '노드 기반 컨테이너'입니다. 또 모든 연관 컨테이너는 균형 2진 트리로 구현됩니다. 균형 2진 트리는 보통 레드-블랙 트리를 사용합니다. map은 key와 value의 쌍으로 구성된 데이터 셋의 집합입니다. 여기서 key는 유니크합니다. multiset도 map과 같이 key와 value의 쌍으로 구성된 데이터 셋의 집합입니다. 단, multiset은 map과 달리 중복된 key가 존재할 수 있습니다.

set과 map은 데이터의 key가 유니크합니다.

multiset과 multimap은 같은 key값의 데이터를 컨테이너에 저장할 수 있습니다.

map, multimap의 주요 특징과 함수

 map도 set처럼 데이터를 추가하는 push_? 류의 함수를 가지고 있지 않습니다. 삽입(insert)한다는 의미에서 insert() 함수를 가지고 있습니다.

map의 특징은 key와 value의 쌍으로 데이터를 저장합니다. 그리고 key값을 이용하여 빠르게 value값을 찾을 수 있습니다. 연관 컨테이너에서 유일하게 [] 연산자 중복을 제공합니다.

기본적인 map 예제

1. 100
   50
   80
   100
   100

map은 key와 value의 쌍으로 구성된 데이터들의 집합입니다. []연산자의 인덱스는 key이며 인덱스가 가리키는 메모리 값이 value입니다.

주의할 점은 m[5] = 100 연산에서 5라는 key가 없으면 노드 '추가'가되며 5라는 key가 있으면 '갱신'이 됩니다. 아래에서 공부합니다.

map의 key값 5로 value를 접근

 map은 key와 value의 쌍을 pair 객체로 저장합니다. STL의 쌍을 이루는 모든 요소는 pair 객체를 사용합니다.

위 예제는 insert()함수를 사용하여 아래 예제로 바꿀 수 있습니다.

1. 100
   50
   80
   100
   100

 map은 key, value를 pair 객체로 각각 first와 second에 저장합니다.

반복자를 사용한 모든 key, value 출력 예제

1. m[2]: 100
   m[3]: 50
   m[4]: 100
   m[5]: 100
   m[7]: 80
   ==============
   m[2]: 100
   m[3]: 50
   m[4]: 100
   m[5]: 100
   m[7]: 80

 map도 양방향 반복자를 제공합니다.

연관 컨테이너는 모두 동일한 함수군을 가지며 동작 방식도 같습니다.

map의 검색 함수들입니다.

1. m[5]: 100
   m[5]: 100
   m[7]: 80
   m[5]: 100 ~ m[7]: 80

 동작은 set에서 설명했으므로 패스~!

마지막으로 multimap 예제입니다.

map과 다른 점은 [] 연산자가 없으며 key 값이 중복될 수 있습니다.

1. m[7]: 80 m[7]: 200 m[7]: 300

 설명은 multiset과 같습니다.

InIt find(InIt first, InIt last, const T& val);

ex)

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

void main()

{

     string names[]={"김정수","구홍녀","문병대",

          "김영주","임재임","박미영","박윤자"}

;

     vector<string> as(&names[0],&names[7]);

     vector<string>::iterator it;

     it=find(as.begin(),as.end(),"안순자");

     if (it==as.end()) {

          cout << "없다" << endl;

     } else {

          cout << "있다" << endl;

     }

}

InIt find_if(InIt first, InIt last, UniPred F);

ex)

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

bool HasYoung(string who)

{

     return (who.find("영") != string::npos);

}

void main()

{

     string names[]={"김정수","구홍녀","문병대",

          "김영주","임재임","박미영","박윤자"};

     vector<string> as(&names[0],&names[7]);

     vector<string>::iterator it;

     for (it=as.begin();;it++) {

          it=find_if(it,as.end(),HasYoung);

          if (it==as.end()) break;

          cout << *it << "이(가) 있다." << endl;

     }

}

FwdIt adjacent_find(FwdIt first, FwdIt last [, BinPred F]);

ex)

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

void main()

{

     int ari[]={1,9,3,6,7,5,5,8,1,4};

     vector<int> vi(&ari[0],&ari[9]);

     vector<int>::iterator it;

     it=adjacent_find(vi.begin(),vi.end());

     if (it != vi.end()) {

          printf("두 요소가 인접한 값은 %d입니다.\n",*it);

     }

}

ex)

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

void main()

{

     int ar1[]={3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4,3};

     int ar2[]={2,4,6,8,0};

     int *p=find_first_of(&ar1[0],&ar1[25],&ar2[0],&ar2[4]);

     if (p!=&ar1[25]) {

          printf("최초의 짝수는 %d번째의 %d입니다.\n",p-ar1,*p);

     }

/*****************************************************************************
*  ------------------------------- dlist.c --------------------------------  *
*****************************************************************************/
#include <stdlib.h>
#include <string.h>
#include "dlist.h"
/*****************************************************************************
*  ------------------------------ dlist_init ------------------------------  *
*****************************************************************************/
void dlist_init(DList *list, void (*destroy)(void *data)) {
 /*****************************************************************************
 *  Initialize the list.                                                      *
 *****************************************************************************/
 list->size = 0;
 list->destroy = destroy;
 list->head = NULL;
 list->tail = NULL;
 return;
}
/*****************************************************************************
*  ---------------------------- dlist_destroy -----------------------------  *
*****************************************************************************/
void dlist_destroy(DList *list) {
 void               *data;
 /*****************************************************************************
 *  Remove each element.                                                      *
 *****************************************************************************/
 while (dlist_size(list) > 0) {
  if (dlist_remove(list, dlist_tail(list), (void **)&data) == 0 && list->
   destroy != NULL) {
    /***********************************************************************
    *  Call a user-defined function to free dynamically allocated data.    *
    ***********************************************************************/
    list->destroy(data);
  }
 }
 /*****************************************************************************
 *  No operations are allowed now, but clear the structure as a precaution.   *
 *****************************************************************************/
 memset(list, 0, sizeof(DList));
 return;
}
/*****************************************************************************
*  ---------------------------- dlist_ins_next ----------------------------  *
*****************************************************************************/
int dlist_ins_next(DList *list, DListElmt *element, const void *data) {
 DListElmt          *new_element;
 /*****************************************************************************
 *  Do not allow a NULL element unless the list is empty.                     *
 *****************************************************************************/
 if (element == NULL && dlist_size(list) != 0)
  return -1;
 /*****************************************************************************
 *  Allocate storage for the element.                                         *
 *****************************************************************************/
 if ((new_element = (DListElmt *)malloc(sizeof(DListElmt))) == NULL)
  return -1;
 /*****************************************************************************
 *  Insert the new element into the list.                                     *
 *****************************************************************************/
 new_element->data = (void *)data;
 if (dlist_size(list) == 0) {
  /**************************************************************************
  *  Handle insertion when the list is empty.                               *
  **************************************************************************/
  list->head = new_element;
  list->head->prev = NULL;
  list->head->next = NULL;
  list->tail = new_element;
 }
 else {
  /**************************************************************************
  *  Handle insertion when the list is not empty.                           *
  **************************************************************************/
  new_element->next = element->next;
  new_element->prev = element;
  if (element->next == NULL)
   list->tail = new_element;
  else
   element->next->prev = new_element;
  element->next = new_element;
 }
 /*****************************************************************************
 *  Adjust the size of the list to account for the inserted element.          *
 *****************************************************************************/
 list->size++;
 return 0;
}
/*****************************************************************************
*  ---------------------------- dlist_ins_prev ----------------------------  *
*****************************************************************************/
int dlist_ins_prev(DList *list, DListElmt *element, const void *data) {
 DListElmt          *new_element;
 /*****************************************************************************
 *  Do not allow a NULL element unless the list is empty.                     *
 *****************************************************************************/
 if (element == NULL && dlist_size(list) != 0)
  return -1;
 /*****************************************************************************
 *  Allocate storage to be managed by the abstract data type.                 *
 *****************************************************************************/
 if ((new_element = (DListElmt *)malloc(sizeof(DListElmt))) == NULL)
  return -1;
 /*****************************************************************************
 *  Insert the new element into the list.                                     *
 *****************************************************************************/
 new_element->data = (void *)data;
 if (dlist_size(list) == 0) {
  /**************************************************************************
  *  Handle insertion when the list is empty.                               *
  **************************************************************************/
  list->head = new_element;
  list->head->prev = NULL;
  list->head->next = NULL;
  list->tail = new_element;
 }
 else {
  /**************************************************************************
  *  Handle insertion when the list is not empty.                           *
  **************************************************************************/
  new_element->next = element; 
  new_element->prev = element->prev;
  if (element->prev == NULL)
   list->head = new_element;
  else
   element->prev->next = new_element;
  element->prev = new_element;
 }
 /*****************************************************************************
 *  Adjust the size of the list to account for the new element.               *
 *****************************************************************************/
 list->size++;
 return 0;
}
/*****************************************************************************
*  ----------------------------- dlist_remove -----------------------------  *
*****************************************************************************/
int dlist_remove(DList *list, DListElmt *element, void **data) {
 /*****************************************************************************
 *  Do not allow a NULL element or removal from an empty list.                *
 *****************************************************************************/
 if (element == NULL || dlist_size(list) == 0)
  return -1;
 /*****************************************************************************
 *  Remove the element from the list.                                         *
 *****************************************************************************/
 *data = element->data;
 if (element == list->head) {
  /**************************************************************************
  *  Handle removal from the head of the list.                              *
  **************************************************************************/
  list->head = element->next;
  if (list->head == NULL)
   list->tail = NULL;
  else
   element->next->prev = NULL;
 }
 else {
  /**************************************************************************
  *  Handle removal from other than the head of the list.                   *
  **************************************************************************/
  element->prev->next = element->next;
  if (element->next == NULL)
   list->tail = element->prev;
  else
   element->next->prev = element->prev;
 }
 /*****************************************************************************
 *  Free the storage allocated by the abstract data type.                     *
 *****************************************************************************/
 free(element);
 /*****************************************************************************
 *  Adjust the size of the list to account for the removed element.           *
 *****************************************************************************/
 list->size--;
 return 0;
}

/*****************************************************************************
*  ------------------------------- dlist.h --------------------------------  *
*****************************************************************************/
#ifndef DLIST_H
#define DLIST_H
#include <stdlib.h>
/*****************************************************************************
*  Define a structure for doubly-linked list elements.                       *
*****************************************************************************/
typedef struct DListElmt_ {
 void               *data;
 struct DListElmt_  *prev;
 struct DListElmt_  *next;
} DListElmt;
/*****************************************************************************
*  Define a structure for doubly-linked lists.                               *
*****************************************************************************/
typedef struct DList_ {
 int                size;
 int                (*match)(const void *key1, const void *key2);
 void               (*destroy)(void *data);
 DListElmt          *head;
 DListElmt          *tail;
} DList;
/*****************************************************************************
*  --------------------------- Public Interface ---------------------------  *
*****************************************************************************/
void dlist_init(DList *list, void (*destroy)(void *data));
void dlist_destroy(DList *list);
int dlist_ins_next(DList *list, DListElmt *element, const void *data);
int dlist_ins_prev(DList *list, DListElmt *element, const void *data);
int dlist_remove(DList *list, DListElmt *element, void **data);
#define dlist_size(list) ((list)->size)
#define dlist_head(list) ((list)->head)
#define dlist_tail(list) ((list)->tail)
#define dlist_is_head(element) ((element)->prev == NULL ? 1 : 0)
#define dlist_is_tail(element) ((element)->next == NULL ? 1 : 0)
#define dlist_data(element) ((element)->data)
#define dlist_next(element) ((element)->next)
#define dlist_prev(element) ((element)->prev)
#endif

/*****************************************************************************
*  -------------------------------- list.c --------------------------------  *
*****************************************************************************/
#include <stdlib.h>
#include <string.h>
#include "list.h"
/*****************************************************************************
*  ------------------------------- list_init ------------------------------  *
****************************************************************************/
void list_init(List *list, void (*destroy)(void *data)) {
 /*****************************************************************************
 *  Initialize the list.                                                      *
 *****************************************************************************/
 list->size = 0;
 list->destroy = destroy;
 list->head = NULL;
 list->tail = NULL;
 return;
}
/*****************************************************************************
*  ----------------------------- list_destroy -----------------------------  *
*****************************************************************************/
void list_destroy(List *list) {
 void               *data;
 /*****************************************************************************
 *  Remove each element.                                                      *
 *****************************************************************************/
 while (list_size(list) > 0) {
  if (list_rem_next(list, NULL, (void **)&data) == 0 && list->destroy != NULL) {
   /***********************************************************************
   *  Call a user-defined function to free dynamically allocated data.    *
   ***********************************************************************/
   list->destroy(data);
  }
 }
 /*****************************************************************************
 *  No operations are allowed now, but clear the structure as a precaution.   *
 *****************************************************************************/
 memset(list, 0, sizeof(List));
 return;
}
/*****************************************************************************
*  ----------------------------- list_ins_next ----------------------------  *
*****************************************************************************/
int list_ins_next(List *list, ListElmt *element, const void *data) {
 ListElmt           *new_element;
 /*****************************************************************************
 *  Allocate storage for the element.                                         *
 *****************************************************************************/
 if ((new_element = (ListElmt *)malloc(sizeof(ListElmt))) == NULL)
  return -1;
 /*****************************************************************************
 *  Insert the element into the list.                                         *
 *****************************************************************************/
 new_element->data = (void *)data;
 if (element == NULL) {
  /**************************************************************************
  *  Handle insertion at the head of the list.                              *
  **************************************************************************/
  if (list_size(list) == 0)
   list->tail = new_element;
  new_element->next = list->head;
  list->head = new_element;
 }
 else {
  /**************************************************************************
  *  Handle insertion somewhere other than at the head.                     *
  **************************************************************************/
  if (element->next == NULL)
   list->tail = new_element;
  new_element->next = element->next;
  element->next = new_element;
 }
 /*****************************************************************************
 *  Adjust the size of the list to account for the inserted element.          *
 *****************************************************************************/
 list->size++;
 return 0;
}
/*****************************************************************************
*  ----------------------------- list_rem_next ----------------------------  *
*****************************************************************************/
int list_rem_next(List *list, ListElmt *element, void **data) {
 ListElmt           *old_element;
 /*****************************************************************************
 *  Do not allow removal from an empty list.                                  *
 *****************************************************************************/
 if (list_size(list) == 0)
  return -1;
 /*****************************************************************************
 *  Remove the element from the list.                                         *
 *****************************************************************************/
 if (element == NULL) {
  /**************************************************************************
  *  Handle removal from the head of the list.                              *
  **************************************************************************/
  *data = list->head->data;
  old_element = list->head;
  list->head = list->head->next;
  if (list_size(list) == 1)
   list->tail = NULL;
 }
 else {
  /**************************************************************************
  *  Handle removal from somewhere other than the head.                     *
  **************************************************************************/
  if (element->next == NULL)
   return -1;
  *data = element->next->data;
  old_element = element->next;
  element->next = element->next->next;
  if (element->next == NULL)
   list->tail = element;
 }
 /*****************************************************************************
 *  Free the storage allocated by the abstract data type.                     *
 *****************************************************************************/
 free(old_element);
 /*****************************************************************************
 *  Adjust the size of the list to account for the removed element.           *
 *****************************************************************************/
 list->size--;
 return 0;
}

/*****************************************************************************
*  -------------------------------- list.h --------------------------------  *
*****************************************************************************/
#ifndef LIST_H
#define LIST_H
#include <stdlib.h>
/*****************************************************************************
*  Define a structure for linked list elements.                              *
*****************************************************************************/
typedef struct ListElmt_ {
 void               *data;
 struct ListElmt_   *next;
} ListElmt;
/*****************************************************************************
*  Define a structure for linked lists.                                      *
*****************************************************************************/
typedef struct List_ {
 int                size;
 int                (*match)(const void *key1, const void *key2);
 void               (*destroy)(void *data);
 ListElmt           *head;
 ListElmt           *tail;
} List;
/*****************************************************************************
*  --------------------------- Public Interface ---------------------------  *
*****************************************************************************/
void list_init(List *list, void (*destroy)(void *data));
void list_destroy(List *list);
int list_ins_next(List *list, ListElmt *element, const void *data);
int list_rem_next(List *list, ListElmt *element, void **data);
#define list_size(list) ((list)->size)
#define list_head(list) ((list)->head)
#define list_tail(list) ((list)->tail)
#define list_is_head(list, element) ((element) == (list)->head ? 1 : 0)
#define list_is_tail(element) ((element)->next == NULL ? 1 : 0)
#define list_data(element) ((element)->data)
#define list_next(element) ((element)->next)
#endif