std::map的简要实现介绍

std::map以红黑树作为实现，树的节点是Node，Node之间用指针链接，map存了一个指向根节点的指针。

std::pair

std::pair基本上就是一个容器，而且不涉及堆上的内存分配:

template<typename Ty1, typename Ty2>
struct pair {
    pair(Ty1 val1, Ty2 val2) : first(val1), second(val2) {}
    Ty1 first;
    Ty2 second;
};

insert

每次insert时，会new一个Node对象，并传入insert的参数。而std::pair正是insert的参数，所以当调用:

a_map.insert(std::make_pair("a", 1));

会导致:

new Node(pair)

然后插入到树中，相当于栈上的pair对象被复制了一份到堆上。所以:

    std::map<int, TestStruct*> int_2_struct_p_;
    std::map<int, TestStruct> int_2_struct;

前者需要自己管理TestStruct的内存（分配和释放），后者会先在栈上分配，然后复制构造到堆中，但后续释放就不用自己操心了，毕竟erase时当然会调用delete Node，而这会触发pair的析构，自然也就把你的struct析构了。

迭代器

struct __TreeIterator
{
    Node* _node;
    __TreeIterator(Node* node)
    :_node(node)
    {}
    Ref operator*()
    {
    return _node->_data;
    }
    Ptr operator->()
    {
    return &_node->_data;
    }
}

所以:

iter->first

实际上是

(&_node->_data)->first，

如果传的是结构体，想修改的话那就使用引用:

TestStruct &t = iter->second;

而

*iter

实际上是:

_node->_data

也就是返回pair对象，所以可以

*iter.first.