std::list (데이터 순차적 저장 및 접근, 데이터 중복 O)

- 중간에 데이터 삽입 및 삭제가 자주 일어날 때 사용한다.
- <list> header를 include 해준 뒤에, std::list를 사용할 수 있다.
- 데이터에 Random Access 하는 경우가 적을 때, 사용하는 것이 좋다. (리스트는 순차적 접근만 가능하므로)
- 저장할 데이터 개수가 많거나, 검색을 자주하는 경우에는 사용하지 않는 것이 좋다.
- 가변적인 길이를 가질 수 있으며, 중간에 비어있는 데이터가 존재하지 않는다.

- list 코드 예시

#include <iostream>
#include <list>

using namespace std;

int main(){
  list<int> lt;
  lt.push_back(2); // lt = {2}
  lt.push_back(3); // lt = {2, 3}
  lt.push_back(4); // lt = {2, 3, 4}
  lt.push_back(4); // lt = {2, 3, 4, 4}
  
  lt.push_front(1); // lt = {1, 2, 3, 4, 4}
  lt.push_front(0); // lt = {0, 1, 2, 3, 4, 4}

  lt.pop_front();   // lt = {1, 2, 3, 4, 4}
  lt.pop_back();    // lt = {1, 2, 3, 4}
  
  lt.push_back(1);  // lt = {1, 2, 3, 4, 1}
  lt.remove(1);     // lt = {2, 3, 4} (특정값 원소 모두 제거)

  // 'list iterator'를 이용하여 list에 접근할 수 있음.
  list<int>::iterator lt_iter;
  for (lt_iter = lt.begin(); lt_iter != lt.end(); lt_iter++) 
      cout << *lt_iter << " ";
  printf("\n");

  // 특정값들로 list 선언하는 법
  list<int> lt2 = {5, 7, 6, 8};

  // 오름차순으로 정렬
  lt2.sort();  // lt2 = {5, 6, 7, 8}

  // lt와 lt2를 merge sort로 합침 (lt2에 lt 원소들을 추가)
  lt2.merge(lt); // lt2 = {2, 3, 4, 5, 6, 7, 8}

  list<int>::iterator lt2_iter;
  for (lt2_iter = lt2.begin(); lt2_iter != lt2.end(); lt2_iter++)
	  cout << *lt2_iter << " ";
  printf("\n");

  return 0;
}

 


std::map (Key 중복 X, Value 중복 O)

- 많은 자료들 사이에서 검색이 용이해야 할 때 사용한다.
- <map> header를 include 해준 뒤에, std::map를 사용할 수 있다.
- Key와 Value는 pair 형태이다.
- C++의 std::map의 경우, key를 기준으로 오름차순 정렬을 자동으로 수행한다.
- 많은 데이터를 저장해야 하고, 검색이 빨라야 할 때 사용하면 좋다.
- 인덱스를 사용하지 않고, iterator를 사용한다.
- 중복 Key value는 사용이 불가능하다. (= 각 Key value는 unique 해야 한다.)

- map 코드 예시

#include <iostream>
#include <string>
#include <map>

using namespace std;

int main(){
  // <key, value>의 pair 형태로 map을 선언함.
  map<string, int> m;

  // map에 데이터 삽입 (key는 중복불가, value는 중복가능)
  m.insert({"ABC", 123});
  m.insert({"BCD", 456});
  m.insert({"CDE", 123});
  // m.insert({"ABC", 789}); 는 key 중복으로 데이터 삽입이 되지 않음.

  // 'map iterator'를 이용하여 map에 접근할 수 있음.
  map<string, int>::iterator m_iter;
  for(m_iter = m.begin(); m_iter != m.end(); m_iter++)
    cout << "key: " <<  m_iter->first << ", value: " << m_iter->second << endl;

  // map에서 데이터 검색 (iterator를 반환하고, 못찾을 시 m.end()를 반환)
  map<string, int>::iterator find_iter;
  find_iter = m.find("ABC");
  
  if(find_iter != m.end())
    cout << "found key: " << find_iter->first << ", found value: " << find_iter->second << endl;
  else
    cout << "can't find data in map!" << endl;

  // map에서 데이터 변경
  m["ABC"] = 789;
  m["BCD"] = 101112;
  
  return 0;
}


std::unordered_map (hash_map) (Key 중복 X, Value 중복 O)

- 많은 자료들 사이에서 검색이 용이해야 할 때 사용한다.
- <unordered_map> header를 include 해준 뒤에, std::unordered_map를 사용할 수 있다.
- Key와 Value는 pair 형태이다.
- c++ std::map과 다르게, hash_map은 자동으로 정렬을 수행하지 않는다. (넣은 순서대로 데이터를 유지)
- 많은 데이터를 저장해야 하고, 검색이 빨라야 할 때 사용하면 좋다.
- 인덱스를 사용하지 않고, iterator를 사용한다.
- 중복 Key value는 사용이 불가능하다. (= 각 Key value는 unique 해야 한다.)

- unordered_map (hash_map) 코드 예시

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

int main(){
  // <key, value>의 pair 형태로 unordered_map을 선언함.
  unordered_map<string, int> um;

  // unordered_map에 데이터 삽입 (key는 중복불가, value는 중복가능)
  um.insert({"ABC", 123});
  um.insert({"BCD", 456});
  um.insert({"CDE", 789});
  // um.insert({"ABC", 789}); 는 key 중복으로 데이터 삽입이 되지 않음.

  // 'unordered_map iterator'를 이용하여 unordered_map에 접근할 수 있음.
  unordered_map<string, int>::iterator um_iter;
  for (um_iter = um.begin(); um_iter != um.end(); um_iter++)
	  cout << "key: " << um_iter->first << ", value: " << um_iter->second << endl;

  // unordered_map에서 데이터 검색 (iterator를 반환하고, 못찾을 시 m.end()를 반환)
  unordered_map<string, int>::iterator find_iter;
  find_iter = um.find("ABC");

  if (find_iter != um.end())
	  cout << "found key: " << find_iter->first << ", found value: " << find_iter->second << endl;
  else
	  cout << "can't find data in unordered_map!" << endl;

  // unordered_map에서 데이터 삭제
  um.erase(find_iter); // <"ABC", 123> pair 삭제

  // unordered_map에서 데이터 변경
  um["BCD"] = 888;
  um["CDE"] = 999;

  return 0;
}

 


std::set (데이터 중복 X, 순서보장 X)

- 많은 자료들 사이에서 검색이 용이해야 할 때 사용한다.
- 인덱스를 사용하지 않고, iterator를 사용한다.
- 중복 Key value는 사용이 불가능하다. (= 각 Key value는 unique 해야 한다.)
- 이진 균형트리로 자료구조가 구성되어 있다.

- set 코드 예시

#include <iostream>
#include <string>
#include <set>

using namespace std;

int main(){
  // int type의 데이터를 담는 set 선언
  set<int> s;

  // set에 데이터 삽입 (key는 중복불가, value는 중복가능)
  s.insert(1); // s = {1}
  s.insert(2); // s = {1, 2}
  s.insert(3); // s = {1, 2, 3}
  s.insert(4); // s = {1, 2, 3, 4}
  //s.insert(1); 는 key 중복으로 데이터 삽입이 되지 않음.

  // 'set iterator'를 이용하여 set에 접근할 수 있음.
  set<int>::iterator s_iter;
  for (s_iter = s.begin(); s_iter != s.end(); s_iter++)
	  cout << "value: " << *s_iter << endl;

  // set에서 데이터 검색 (iterator를 반환하고, 못찾을 시 s.end()를 반환)
  set<int>::iterator find_iter;
  find_iter = s.find(1);

  if (find_iter != s.end())
	  cout << "found value: " << *find_iter << endl;
  else
	  cout << "can't find data in set!" << endl;

  // set에서 데이터 삭제
  s.erase(find_iter); // '1' value 삭제

  return 0;
}

 


* 참고자료

1. https://gamdekong.tistory.com/94
2. https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=psd0217&logNo=220308769007
3. https://velog.io/@esun1903/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-List-Map-Set%EC%9D%98-%ED%8A%B9%EC%A7%95%EA%B3%BC-%EC%B0%A8%EC%9D%B4%EC%A0%90
4. https://blockdmask.tistory.com/79