map && set的区别和实现原理

//以下用到的make_heap(),push_heap(),pop_heap()都是泛型算法

//任何一个构造函数都可以立即在底层产生一个heap template<class InputIterator>

priority_queue(InputIterator first, InputIterator last const Compare &x)

:c(first, last), comp(x) { make_heap(c.begin(), c.end(), comp); }

template<class InputIterator> priority_queue(InputIterator first, InputIterator last const Compare &x)

:c(first, last) { make_heap(c.begin(), c.end(), comp); }

bool empty() const { return c.empty(); } size_type size() const { return c.size(); }

const_reference top() const { return c.front(); } void push(const value_type &x) {

_STL_TRy { c.push_back(X);

push_heap(c.begin(), c.end(), comp);

} _STL_UNWIND{c.clear()};

}

void pop() { _STL_TRY {

pop_heap(c.begin(), c.end(), comp);

c.pop_back();

} _STL_UNWEIND{c.clear()};

} };

// priority_queue无迭代器

map && set的区别和实现原理

map内部实现了一个红黑树（红黑树是非严格平衡的二叉搜索树，而AVL是严格平衡二叉搜索树），红黑树有自动排序的功能，因此map内部所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素。因此，对于map

进行的查找、删除、添加等一系列的操作都相当于是对红黑树进行的操作。map中的元素是按照二叉树（又名二叉查找树、二叉排序树）存储的，特点就是左子树上所有节点的键值都小于根节点的键值，右子树所有节点的键值都

大于根节点的键值。使用中序遍历可将键值按照从小到大遍历出来。

共同点：

都是C++的关联容器,只是通过它提供的接口对里面的元素进行访问，底层都是采用红黑树实现。

不同点：