map

map 은 기본적으로 레드블랙 트리(Red-Black Tree 이하 RB Tree) 기반으로 되어있습니다.

때문에 모든 데이터는 정렬되어 저장됩니다.

 

RB Tree는 검색속도가 빠른 Binary Search Tree(BST)에 Self-Balancing 기능을 추가한 것으로 AVL Tree만큼 엄격하진 않지만

O(logN)을 보장하는 수준으로 Balancing 되어지는 특징을 갖고 있습니다. 

 

이러한 특성 때문에 입력되는 키 값의 분포가 고르지 못할 경우 balancing(node rotation)에 대한 비용이 들기 때문에

Insert / Delete 성능이 저하될 수 있습니다. (물론 최악의 경우에도 O(logN)의 성능은 보장됩니다)

 


unordered_map

unordered_map은 hash_table 기반의 hash container입니다. 

 

hash_table을 통해 참조를 하기 때문에 각 node들을 정렬할 필요가 없습니다. 

따라서 충분한 hash_table의 크기만 주어진다면 데이터 양이 많아지더라도

Search / Insert / Delete 의 O(1) 성능을 꾸준하게 보장할 수 있습니다. 

 

 

 

 



출처: https://gracefulprograming.tistory.com/3 [Peter의 우아한 프로그래밍]

'STL > map' 카테고리의 다른 글

map 자주 쓰는 멤버함수 정리  (0) 2019.09.28

#include <list>

1. 기본형

  • list<data type> : 저장할 원소의 type 선언

2. 반복자(iterator)

  • begin() : beginning iterator를 반환
  • end() : end iterator를 반환

3. 추가 / 삭제

  • push_front(element) : 리스트 제일 앞에 원소 추가
  • push_back(element) : 리스트 제일 뒤에 원소 추가
  • pop_front() : 리스트 제일 앞에 원소 삭제
  • pop_back() : 리스트 제일 뒤에 원소 삭제
  • insert(iterator, element) : iterator가 가리키는 부분 "앞"에 원소 추가
  • erase(iterator) : iterator가 "가리키는 부분"의 원소 삭제

4. 조회

  • *iterator : iterator가 가리키는 원소에 접근
  • front() : 첫번째 원소 반환
  • back() : 마지막 원소 반환

5. 기타

  • empty() : 리스트가 비어있으면 true 아니면 false를 반환
  • size() : 리스트 원소들의 수를 반환

 

#include <iostream>
#include <list>
using namespace std;
 
int main()
{
 
    list<int> l;
 
 
    // push_back
    l.push_back(5);
    l.push_back(6);
    l.push_back(7);
    l.push_back(8);
    l.push_back(9);
    l.push_back(10);
 
 
    // pop_back
    l.pop_back();
 
 
    // push_front
    l.push_front(4);
    l.push_front(3);
    l.push_front(1);
    l.push_front(0);
 
 
    // pop_front
    l.pop_front();
 
 
    // back and front
    cout << "list front value : " << l.front() << '\n';
    cout << "list end value : " << l.back() << '\n';
 
 
    // size
    cout << "list size : " << l.size() << '\n';
 
 
    // empty
    cout << "Is it empty? : " << (l.empty() ? "Yes" : "No"<< '\n';
 
 
    // iterator
    list<int>::iterator begin_iter = l.begin(); // auto begin_iter = l.begin()도 가능
    list<int>::iterator end_iter = l.end(); // auto end_iter = l.end()도 가능
 
 
    // insert
    begin_iter++// 2번째를 가리키는 iterator
    l.insert(begin_iter, 2);
 
 
    // erase
    // end_iter이 l.end()를 가리키고 있기때문에 "--" 연산을 꼭 해야 마지막 원소를 가리킬수 있음 
    end_iter--// 마지막 원소를 가리키는 iterator
    l.erase(end_iter);
 
 
    // *iterator : 원소 접근
    cout << "element list : ";
    for(auto i = l.begin(); i != l.end(); i++)
    {
        cout << *<< " ";
    }
 
    return 0;
 
}
cs

 

출처 :

https://twpower.github.io/78-how-to-use-list-in-cpp

차이점

  1. 'cin'은 'white space' 전까지만, 'getline'은 'white space' 까지 입력을 받는다. (둘다 '\n(엔터)' 만나면 종료)
  2. 'cin'은 처음으로 들어오는 'white space' 입력은 무시하고, 이후의 입력을 받는다.
  3. 'getline'은 처음으로 들어오는 'white space' 입력을 받는다. (입력을 받지만 '\n'(엔터) 같은 경우에는 저장 X)

 

Ex)

입력이  a  b  c  d  '\n'  e  f  '\n'  g  '\n'  이라고 하면,

 

cin >> first;       

// first에  a  b  c d 저장  ->  '\n'  e  f  '\n'  g  '\n' 남음 -> 1번 조건에 의해서 '\n' 입력 무시

 

cin >> second;   

// second에  e  f 저장  ->  '\n'  g  '\n' 남음  ->  2번 조건에 의해서 맨 앞의 '\n' 입력 무시

 

getline(cin, third); 

// third가  '\n'  입력 받지만 저장 X  ->  g  '\n' 남음  ->  3번 조건에 의해서 맨 앞의 '\n' 입력 받음

 

해결법

  1. 'cin'과 'getline' 사이에 cin.ignore()를 선언하여 \n 제거
  2. 'cin'과 'getline' 사이에 string buffer, getline(cin, buffer) 를 선언하여 \n 제거

 

#include<algorithm> sort

https://blockdmask.tistory.com/178

 

[C++] sort algorithm 정리 및 예시

안녕하세요 BlockDMask 입니다. 오늘은 C++ STL 에서 제공하는 알고리즘 중에 sort 알고리즘에 대해 알아보겠습니다. 0. sort algorithm sort 알고리즘은 헤더파일에 속해있습니다. sort(start, end)..

blockdmask.tistory.com

https://hongku.tistory.com/153

 

C++ :: STL sort() 함수 다루기, 오름차순 내림차순, 학생 점수 순서대로 나열하기

STL sort() 함수 정렬을 만들어서 사용할 수 는 있지만, 매번 만들어서 사용하기는 번거롭다. 이럴때, 'alforithm' 을 include해서 그안에 있는 sort() 함수를 사용하면 된다. 1. sort() 함수를 이용한 오름차순과..

hongku.tistory.com

 

#include<queue> sort (priority_queue)

https://koosaga.com/9

 

STL priority queue 활용법

모든 nlgn들의 영웅(?) 같은 priority_queue 존재 그 자체로 멋지지만 정말 멋지게 쓰기 위해서는 제대로 활용할 줄 알아야 할 것이다. 1. Colored By Color Scripter™ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1..

koosaga.com

 

차이점

1.

  • #include <algorithm> : sort에서는 greater가 내림차순
  • #include <queue> : priority_queue의 sort에서는 greater가 오름차순

2.

  • #include <algorithm> : sort에서는 1번의 greater를 사용시에 greater<int>()와 같이 사용
  • #include <queue> : priority_queue의 sort에서는 1번의 greater를 사용시에 gerater<int>와 같이 사용

3. 

  • #include <algorithm> : sort에서는 cmp 함수를 만들때 인자의 왼쪽이 기준
  • #include <queue> : priority_queue의 sort에서는 cmp 함수를 만들때 인자의 오른쪽이 기준

 

추천방법

1. #include <algorithm> : 비교함수 cmp를 만들어서 사용

2. #include <algorithm> : greater<type>() 사용 -> 구조체는 1번, 어떤 원소를 비교할지 몰라 에러 발생

 

bool cmp(pair<intstring> v1, pair<intstring> v2)
{
    if(v1.first == v2.first)
    {
         sort는 왼쪽이 기준이기 때문에 second 오름차순 정렬 
        return v1.second < v2.second;
    }
    else
    {
         sort는 왼쪽이 기준이기 때문에 first 오름차순 정렬     
        return v1.first < v2.first;    
    }
}
vector<pair<intstring>> v;
sort(v.begin(), v.end(), cmp); 
 
 
sort(v.begin(), v.end()); // 오름차순
sort(v.begin(), v.end(), greater<int>()); // 내림차순
cs

 

3. #include <queue> : 클래스 cmp에 oeprator()를 만들어서 사용

4. #include <queue> : less<type>, greater<type> 사용

 

//struct cmp 
class cmp
{
    public:
        bool operator()(pair<intint> pq1, pair<intint> pq2)
        {
            if(pq1.first == pq2.first)
            {
                // priority_queue는 오른쪽이 기준이기 때문에 second 오름차순 정렬 
                return pq1.second > pq2.second;
            }
            else
            {
                // priority_queue는 오른쪽이 기준이기 때문에 first 오름차순 정렬     
                return pq1.first > pq2.first;   
            }
        }
};    
priority_queue<pair<intint>vector<pair<intint>>, cmp> pq;
 
 
// 일반적인 사용법도 추천
priority_queue<pair<intint>vector<pair<intint>>, less<pair<intint>>> pq;
priority_queue<pair<intint>vector<pair<intint>>, greater<pair<intint>>> pq;
cs

 

 

 

#include <map>

1. 기본형

  • map<key,value> : key와 value를 pair 형태로 선언, 각 key와 value에 사용할 type 선언

2. 반복자(iterator)

  • begin() : beginning iterator를 반환
  • end() : end iterator를 반환

3. 추가 / 삭제

  • insert(make_pair(key,value)) : 맵에 원소를 pair 형태로 추가
  • erase(key) : 맵에서 key(키값)에 해당하는 원소 삭제
  • clear() : 맵의 원소들 모두 삭제

4. 조회

  • find(key) : key(키값)에 해당하는 iterator 반환, iterator의 first, second 통해 key, value에 접근 -> 없으면 end() 반환
  • count(key) : key(키값)에 해당하는 원소들(value들)의 개수를 반환

5. 기타

  • empty() : 맵이 비어있으면 true 아니면 false를 반환
  • size() : 맵 원소들의 수를 반환

 

#include <iostream>
#include <map>
#include <string>
using namespace std;
 
int main()
{
    // 기본형 선언 
    map<stringint> m;
    
    // iterator 선언 
    map<stringint>::iterator it;
 
 
 
    // insert(key,value)
    m.insert(make_pair("a"1));
    m.insert(make_pair("b"2));
    m.insert(make_pair("c"3));
    m.insert({"d"4});
    m.insert({"e"5});
 
    // 주로 사용하는 형태
    m["f"= 6;
 
 
 
    // erase(key)
    m.erase("d");
    m.erase("e");
    m.erase(m.find("f")); 
 
 
 
    // empty(), size()
    if(!m.empty()) cout << "m size : " << m.size() << "\n";
 
 
 
    // find(key)
    cout << "a : " << m.find("a")->second << "\n";
    cout << "b : " << m.find("b")->second << "\n";
    // it = m.find("a");
    // cout << "a : " << (*it).second << "\n";
    // if(m.find("a") != m.end())을 통해 키값 유무 확인
 
 
    // count(key)
    cout << "a count : " << m.count("a"<< "\n";
    cout << "b count : " << m.count("b"<< "\n";
    // if(m.count("a") != 0)을 통해 키값 유무 확인
 
 
 
    // begin(), end()
    cout << "traverse" << "\n";
    
    // for(auto it = m.begin(); it != m.end(); it++)
    for(it = m.begin(); it != m.end(); it++)
    {
        cout << "key : " << it->first << " " << "value : " << it->second << "\n";
    }
 
    return 0;
}
  cs

 

출처 :

https://twpower.github.io/91-how-to-use-map-in-cpp

 

'STL > map' 카테고리의 다른 글

<map> vs <unordered_map> 차이  (0) 2020.03.31

우선순위 큐는 priority_queue<자료형, 구현체, 비교연산자>로 정의한다.

 

구현체는 기본적으로 vector<자료형> 형태로 정의한다.

비교연산자는 functional 라이브러리 추가를 통해 greater<int> 오름차순으로 정렬 가능하다.

 

#include <stdio.h>
#include <queue>
#include <functional>
using namespace std;
 
int main()
{
    priority_queue<intvector<int>, less<int>> pq;
    
    pq.push(3);
    pq.push(1);
    pq.push(4);
    pq.push(1);
    pq.push(5);
    pq.push(9);
    
    while (!pq.empty()) 
    {
        printf("%d",pq.top());
        pq.pop();
    }
}
cs

 

추가 참고자료 :

https://koosaga.com/9

 

string은 문자열을 메모리에 저장할 때 실제론 '\0' 을 포함하지만, 개념상 \0 에 대한 접근을 허용하지 않는다.

 

string s = "LOVE YOU", 문자열을 단어 단위로 저장하려고 할때 이를 사용할 수 있다.

 

string s = "I LOVE YOU BABY";
string temp;
vector<string> v;
 
for(int i = 0; s[i] != '\0'; i++)
{
    if(s[i] == ' ')
    {
        v.push_back(temp);
        temp.clear();
    }
 
    temp += s[i];
}
v.push_back(temp);
cs

 

출처 :
https://hashcode.co.kr/questions/5777/c-string-클래스에-문자열을-저장할-때는-널문자가-없나요

 

 

 

#include <string>

1. compare : 문자열 비교

#include <iostream>
#include <string>
using namespace std;
 
string s1 = "LOVE";
string s2 = "ABC";
 
int result = s1.compare(s2);   // 양수 반환
cs
  • s1 = s2 : 0 반환
  • s1 > s2 : 양수 반환(1)
  • s1 < s2 : 음수 반환(-1)

 

2. find : 문자열 검색 -> STL의 find함수랑 다름

#include <iostream>
#include <string>
using namespace std;
 
string s = "LOVE";
 
int idx1 = s.find("LO");      // 0 반환 
int idx2 = s.find("VE"1);   // 2 반환
 
if(s.find("AC"== string::npos)
{
   "AC" 문자열을 못찾으면 TRUE
}
 
if(s.find("LO") != string::npos)
{
   "LO" 문자열을 찾으면 TRUE
}
cs
  • s.find("문자열") : 찾은 문자열의 인덱스 반환
  • s.find("문자열", 시작 인덱스) : 시작 인덱스부터 찾은 문자열의 인덱스 반환

 

3. erase : 문자열 삭제

#include <iostream>
#include <string>
using namespace std;
 
string s = "LOVE";
 
s.erase(12);                           // "OV" 삭제 -> s = "LE"
s.erase(find(s.begin(), s.end(), "L"));   // "L" 삭제 -> s = "E"
cs
  • s.erase(시작 인덱스) : 시작 인덱스부터 끝까지 삭제
  • s.erase(시작 인덱스, 개수) : 시작 인덱스부터 개수만큼 삭제
  • s.erase(반복자) : 반복자가 가르키는 인덱스부터 1만큼 삭제

 

4. substr : 문자열 나누기

#include <iostream>
#include <string>
using namespace std;
 
string s = "LOVE";
 
string s2 = s.substr(2);      // s = "VE"
string s3 = s.substr(13);   // s = "OVE"
cs
  • s.substr(시작 인덱스) : 시작 인덱스부터 끝까지 나눈 문자열 반환
  • s.substr(시작 인덱스, 개수) : 시작 인덱스부터 개수만큼 나눈 문자열 반환

 

5. replace : 문자열 변경

#include <iostream>
#include <string>
using namespace std;
 
string s = "LOVE";
 
s.replace(12"AA");   // s = "LAAE"
cs
  • s.replace(시작 인덱스, 개수, "문자열") : 시작 인덱스부터 개수만큼 문자열 변경

 

6. insert : 문자열 삽입

#include <iostream>
#include <string>
using namespace std;
 
string s = "LOVE";
 
s.insert(2"aa"); // s = "LOaaVE"
cs
  • s.insert(시작 인덱스, "문자열") : 시작 인덱스에 문자열 삽입

 

7. push_back / pop_back : 문자 삽입 / 삭제

#include <iostream>
#include <string>
using namespace std;
 
string s = "LOVE";
 
s.pop_back();        // s = "LOV";
s.push_back('E');    // s = "LOVE";
cs
  • s.push_back('문자') : 문자열 맨 끝에 문자 1개 삽입
  • s.pop_back() : 문자열 맨 끝에 문자 1개 삭제

 

8. to_string : int, float, long 등 -> string 변환

#include <iostream>
#include <string>
using namespace std;
 
int a = 524;
string s = to_string(a);   // s = "524"
cs

 

9. stoi : string -> int 변환 (C++11 이상)

10. atoi(s.c_str()) : string -> int 변환 (C++11 이하)

#include <iostream>
#include <string>
using namespace std;
 
string s = "524";
int a = stoi(s);   // a = 524
 
 
string s = "524";
int a = atoi(s.c_str());   // a = 524
cs

 

 

 

#include <algorithm>

1. find : 원소 검색 in <vector>

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
 
1) array and pointer
int a[5= {12345};
int *ap = find(a, a+54);      // 찾으면 a+3 반환, 못찾으면 a+5 반환
 
char b[5= "LOVE";
char *bp = find(b, b+5'O');   // 찾으면 b+1 반환, 못찾으면 b+5 반환
 
2) vector and iterator
vector<string> v;
v.push_back("LOVE");
v.push_back("YOU"); 
v.push_back("ME"); 
v.push_back("COOL");
 
vector<string>:: iterator it;
it = find(v.begin(), v.end(), "YOU");   // 찾으면 "YOU" 가르키는 반복자 반환, 못찾으면 v.end() 반환
cs
  • find(시작, 종료, 원소) : 찾으면 원소를 가르키는 반복자 반환, 못찾으면 종료 반환

 

2. reverse : 역순

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
 
int a[5= {12345};
char a[5= "LOVE";
string s = "LOVE";
 
reverse(a+1, a+5);             // (a+1)~(a+5)까지 역순 a[5] = {1, 5, 4, 3, 2}
reverse(a, a+4);               // 널문자 제외
reverse(s.begin(), s.end());   // s = "EVOL"
cs
 

 

+ Recent posts