Map 메모리

김동현·2024년 3월 27일

Question

목록 보기

14/15

의문

🤔 맵, 딕셔너리 자료구조는 key:value 형식의 자료구조 형식을 갖게 되는 데, 어떻게 Key로 바로 접근 할 수 있는 지 궁금해 졌다.
🤔 해시테이블로 생각 했나보다..

#include<bits/stdc++.h>
using namespace std;
int main() {

    // 맵 선언
    std::map<int, int> mp;
    cout << "맵 자료구조 주소: " << &mp << "\n";
    cout << "맵 자료구조 주소(10진수): " << reinterpret_cast<uintptr_t>(&mp) << "\n";
    cout << "\n";
    
    // 맵에 요소 추가
    mp[1] = 10;
    mp[2] = 20;
    mp[3] = 30;
    mp[4] = 40;

    // 맵의 각 요소의 키, 값, 그리고 해당 키와 값의 주소 출력
    cout << "키\t값\t키 주소\t\t\t키 주소(10진수)\t\t값 주소\t\t\t값 주소(10진수)" << "\n";
    for (const auto& pair : mp) {
        std::cout << pair.first << "\t" << pair.second << "\t" 
                  << &pair.first << "\t\t"
                  << reinterpret_cast<uintptr_t>(&pair.first) << "\t\t" 
                  << &pair.second << "\t\t"
                  << reinterpret_cast<uintptr_t>(&pair.second) << "\n";
    }

    auto it = mp.find(3);
    
    if (it != mp.end()) {
        cout << "키 3에 해당하는 값은 " << it->second << "입니다." << endl;
    } else {
        cout << "키 3에 해당하는 값이 맵에 없습니다." << endl;
    };

    return 0;
}

위 이미지를 보면 아래와 같은 특징을 볼 수 있다.

맵이 선언된 주소의 값이 키, 값의 주소 보다 크다.
- 스택이 힙보다 더 높은 메모리 주소를 할당 받기 때문이다.
Key와 value 사이에는 4바이트 차이가 난다.
- map의 자료구조가 <int, int>이기 때문이다.
키, 값과 다음 키, 값의 차이는 48바이트만큼 차이가 난다.
- 해당 이유는 잘 모르겠다 😅

find 메서드

find 메서드를 들어가보면 tree 자료구조의 find 메서드를 사용하는 것을 볼 수 있다.

tree.find 메서드를 들어가보면 __lower_bound 함수를 호출하는 것을 볼 수 있다.

__lower_bound 함수를 들어가보면 아래와 같은데 lower_bound함수의 경우 오른쪽 원소 중 기준 원소와 같거나 큰 값 중 가장 왼쪽에 있는 원소의 iterator값을 리턴하는 함수이다.

__tree<_Tp, _Compare, _Allocator>::find(const _Key& __v)
{
    iterator __p = __lower_bound(__v, __root(), __end_node());
    if (__p != end() && !value_comp()(__v, *__p))
        return __p;
    return end();
}

즉 순회한 결과가 찾고자 하는 값과 같으면 해당 iterator를 반환하고 아니면 마지막 다음 위치를 반환해 주는 것이다.

🧐

map 자료구조는 pair 자료구조가 연속적으로 힙 메모리에 할당되고,
first -> key, second -> value로 간주하고 레드, 블랙 트리 자료구조를 활용하여 이진 탐색을 통해 데이터를 찾아나가는 것 아닐까 싶다.

key와 value가 어떤 자료형인지 알고 있으니 두 자료 구조의 크기의 합을 간격으로 데이터를 찾아가는 것 아닐까

배열 자료구조에서 탐색과 비교하여 Map탐색이 왜 더 빠른지 확인하다보니 여기까지 왔다

스텍오버 플로우의 답변 하나를 가져왔다. 읽어보면 좋을 거 같다.

Basicaly std::map is implimented using red-black tree. In red-black tree insert ans delete operation take O(LogN) time,
so in std::map time complexity is O(LogN) of every element.

std::unodered_map is implememted using hashing ,where every operation take O(1) time.