STL系列

STL系列的相关文章

《STL系列》之map原理及实现

上一篇文章<STL系列>之vector原理及实现,介绍了vector的原理及实现,这篇文章介绍map的原理及实现.STL实现源码下载.STL中map的实现是基于RBTree的,我在实现的时候没有采用RBTree,觉得这东西有点复杂,我的map采用的是排序数组(CSortVector).map中的Key存在排序数据中,通过二分查找判断某个Key是否在map中,时间复杂度为O(logN).在用一个CVector存Key和Value,为了方便拿到Key和Value,这里有点冗余,Key被存了两次.现

[STL系列]开篇简单介绍

开篇: 为了应付上机考,现在需要总结下关于STL的基础知识.由于以前各种代码都喜欢从头搭起,像这种现成的牛逼的STL就没怎么看,真是作死.现在来突击啦. 开始之前,简单看一段代码,功能很简单,就是要实现对一组数字的排序,以窥STL的一斑. 1 #include "iostream" 2 #include <algorithm> 3 #include <vector> 4 using namespace std; 5 6 int main() 7 { 8 vect

白话经典算法系列之七 堆与堆排序

堆排序与高速排序,归并排序一样都是时间复杂度为O(N*logN)的几种常见排序方法.学习堆排序前,先解说下什么是数据结构中的二叉堆. 二叉堆的定义 二叉堆是全然二叉树或者是近似全然二叉树. 二叉堆满足二个特性: 1.父结点的键值总是大于或等于(小于或等于)不论什么一个子节点的键值. 2.每一个结点的左子树和右子树都是一个二叉堆(都是最大堆或最小堆). 当父结点的键值总是大于或等于不论什么一个子节点的键值时为最大堆.当父结点的键值总是小于或等于不论什么一个子节点的键值时为最小堆.下图展示一个最小堆

priority_queue 优先队列

优先队列是单向队列的一种,可以按照默认或自定义的一种方式来对队列中的数据进行动态排序 template<class _Ty, class _Container = vector<_Ty>, class _Pr = less<typename _Container::value_type> > //默认以vector为容器的 class priority_queue { // priority queue implemented with a _Container pub

[Z]修炼成C++高手必看的C++书单

增添于网上的一些书单: C++/OPP/OOD系列: 层级一:语法/语意(C++)[Lippman2000] Essential C++ Essential C++,by Stanley B. Lippman Addison Wesley Longman 2000,276 pages Essential C++ 中文版 ,侯俊杰 译,282页 Desc: 这本书概要性的介绍了C++核心的东西,但讲得较浅显,适合刚入门的人阅读. [Andrew Koeing & Barbara MOO] Acce

利用堆实现堆排序&amp;优先队列

数据结构之(二叉)堆 一文末尾提到"利用堆可以实现:堆排序.优先队列".本文代码实现之. 1.堆排序 假设要将无序数组按非递减(递增)排序,则应使用大(小)顶堆.这里涉及到大堆排序涉及到三种操作:(1).MaxHeapify操作(自顶向下即SiftDown操作):(2).BuildMaxHeap操作(线性时间内将无序数组构造成一个最大堆):(3)将堆顶元素和堆的最后一个元素交换,并将堆元素大小减去1,对堆顶元素调用MaxHeapify操作重新调整为大顶堆,重复直到数组有序.下面是详细的

priority_queue 优先级队列

priority_queue 优先级队列是一个拥有权值概念的单向队列queue,在这个队列中,所有元素是按优先级排列的(也可以认为queue是个按进入队列的先后做为优先级的优先级队列——先进入队列的元素优先权要高于后进入队列的元素).在计算机操作系统中,优先级队列的使用是相当频繁的,进线程调度都会用到.在STL的具体实现中,priority_queue也是以别的容器作为底部结构,再根据堆的处理规则来调整元素之间的位置.下面给出priority_queue的函数列表和VS2008中priority

堆与堆排序

原文:http://blog.csdn.net/morewindows/article/details/6709644 堆排序与快速排序,归并排序一样都是时间复杂度为O(N*logN)的几种常见排序方法.学习堆排序前,先讲解下什么是数据结构中的二叉堆. 二叉堆的定义 二叉堆是完全二叉树或者是近似完全二叉树. 二叉堆满足二个特性: 1.父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值. 2.每个结点的左子树和右子树都是一个二叉堆(都是最大堆或最小堆). 当父结点的键值总是大于或等于任何

BZOJ 1095 ZJOI2007 Hide 捉迷藏 动态树分治+堆

题目大意:给定一棵树,一开始每个点都是黑点,多次改变某个点的状态或询问距离最远的两个黑点的距离 <珍爱生命远离STL可是我还是可耻地用了STL系列> 传说中的动态树分治...其实并没有那么神嘛= = ↑别听这傻瓜瞎说这货被STL卡了一天QAQ 我们把分治过程中遍历过的重心都连起来 上一层的重心链接下一层的重心 可以得到一棵新的树 下面我们开始讨论这棵新树 显然这棵树的高度不会超过O(logn) 然后我们每个节点开两个堆 第一个堆记录子树中所有节点到父亲节点的距离 第二个堆记录所有子节点的堆顶