STL常用数据结构总结

2019-11-08 02:26:49

字体：大中小

来源：转载

供稿：网友

数据结构机考的你，想不想偷懒？快来看一看c++的STL吧。 STL（standard template library）标准模板库提供了一些列数据结构和算法，帮你更高效地解决问题。下面列出一些常用的(STL的一小部分)数据结构和算法接口，标准采用sgi stl，参考自The annotated STL Sources （所有容器采用泛型设计，可采用泛型方式调用，头文件为容器名）一、vector 向量容器 vector与array相比，其差异在于vector动态分配空间（线性连续地址），并且集成了一系列操作函数。 public接口：(构造函数与析构函数不列出且有省略) iterator begin(); //返回首元素 inerator end(); //返回末尾元素的下一个位置指针，注意不是最后一个元素 size_type size() const; //返回vector长度 size_type capacity() const; //返回容器容量 bool empty() const; //返回向量是否为空 reference Operator[]; //可用[]符号进行同数组一样的下标访问 void push_back(const T& x); //将x元素添加到最后 void pop_back(); //将最后一个元素取出 iterator erase(iterator position); //删除position位置的元素，并返回操作后position位置的元素 void resize(size_type new_size); //改变向量长度 void clear(); //清空向量遍历：迭代器方法、直接线性遍历方法二、 stack 栈 stack没有迭代器，不可遍历。 stack底层采用list实现。 public接口：(构造函数与析构函数不列出且有省略) bool empty() const; size_type size() cosnt; reference top(); //返回栈顶元素 void push(const value_type& x); //元素入栈 void pop(); //栈顶元素弹栈三、queue 队列 queue没有迭代器，不可遍历。 queue底层采用list实现。 public接口：(构造函数与析构函数不列出且有省略) bool empty() const; size_type size() const; reference front(); //返回队首元素 reference back(); //返回队尾元素 void push(const value_type& x); //元素入队 void pop(); //元素出队四、 set 集合 set中所有元素会根据键值自动排序，set中不允许有相同键值元素。set是非线性排列的，其底层采用红黑树，采用平衡二叉搜索机制，set的迭代器是const类型，不能写入修改值。（默认升序）set的遍历采用迭代器，迭代器重载过操作符对平衡树进行中序遍历。 public接口：(构造函数与析构函数不列出且有省略) iterator begin() const; iterator end() const; bool empty() const; size_type size() const; void swap(set<Key, Compare, Alloc>& x); //交换两个集合中元素 pair<iterator, bool> insert(cosnt value_type& x); //插入x元素 void insert(InputIterator first, InputIterator last); //插入first到last区间(前闭后开)内的所有元素 void erase(iterator position); //删除position位置迭代器的元素 size_type erase(const key_type& x); //删除key为x的元素 void erase(iterator first, iterator last); //删除集合中等于first到last区间内的所有元素 void clear(); iterator find(const key_type& x); //查找key等于x的元素，查找成功返回x的迭代指针，失败返回end() 在algorithm里提供了一些列对set操作的算法： OutputIterator set_union(InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2, OutputIterator result); //函数求两个集合的并集并返回结果 OutputIterator set_intersection(InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2, OutputIterator result); //函数求两个集合的交集并返回结果 OutputIterator set_difference(InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2, OutputIterator result); //函数求两个集合的差集，出现在[first1, last1)但不出现在[first2, last2)的元素五、map 键值对容器所有元素会根据键值排序（默认升序），map中的所有元素都是pair，同时拥有实值和键值，pair的第一元素为键值，第二元素为实值。map不允许有两个相同键值的元素。map底层实现依靠红黑树机制。map的迭代器不能修改键值，但可以修改实值，遍历采用迭代器方式，自动对平衡树进行中序遍历。 public接口：(构造函数与析构函数不列出且有省略) iterator begin(); iterator end(); iterator rbegin(); bool empty() const; size_type size() const; T& operator[] (const key_type& k); //根据key值，通过下边方式取得实值 pair<iterator, bool> insert(const value_type& x); iterator insert(iterator position, const value_type& x); void insert(InputIterator first, InputIterator last); void erase(iterator position); size_type erase(const key_type& x); void erase(iterator first, iterator last); //删除集合中等于first到last区间内的所有元素 iterator find(const key_type& x); //查找key等于x的元素，查找成功返回x的迭代指针，失败返回end() 键值对的构造，可以采用make_pair的方式，也可以采用map::value_type(k, T())的类型转换。

上一篇：Kmeans++

下一篇：常用排序算法小结