STL(一)vector、set/multiset、listVectorSetmultisetlist

Vector

动态数据,可以随机访问。末尾添加和删除的效率高。元素的顺序和推入的顺序一致。

基本函数

  • push_back 数组最后添加一个元素。如果是对象会执行对象的拷贝构造函数
  • pop_back 去掉数组最后一个元素
  • at 根据下标得到数据的引用,可以当左值。越界会抛异常
  • [] 可以使用[]操作符,得到结果可以当左值。越界不会抛异常
  • begin 得到数组头的指针iterator
  • end 得到数组的最后一个单元+1的指针 iterator
  • front 数组首元素的引用
  • back 数组尾元素的引用
  • size 数组大小
  • earse 删除参数为iterator
  • insert 指定位置插入元素
  • empty 判断空 ​

遍历

迭代器方式

void printV(vector<int>& v) {
    for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
        cout << *it << "  ";
    }
    cout << endl;
}

删除

vector<int>::iterator it = v.begin();
v.erase(v.begin(), v.end() - 1);

案例

void test() {
    vector<Student> v;
    Student stu1(1, "first");
    Student stu2(2, "second");
    Student stu3(3, "third");
    v.push_back(stu1);
    cout << "------------" << endl;
    v.push_back(stu2);
    cout << "------------" << endl;
    vector<Student>::iterator it = v.begin();
    v.insert(it, stu3);
    cout << "------------" << endl;
    printStud(v);
}

运行结果:

insert.png

Set

vector封装数组,list封装了链表,map和set封装了二叉树等。set关联式容器。set作为一个容器也是用来存储同一数据类型的数据类型,并且能从一个数据集合中取出数据,在set中每个元素的值都唯一,而且系统能根据元素的值自动进行排序。应该注意的是set中数元素的值不能直接被改变。C++ STL中标准关联容器set, multiset, map, multimap内部采用的就是一种非常高效的平衡检索二叉树:红黑树,也成为RB树(Red-Black Tree)。RB树的统计性能要好于一般平衡二叉树,所以被STL选择作为了关联容器的内部结构。set插入是按照一定规则排序,默认是由小到大。

  • 为何map和set的插入删除效率比用其他序列容器高? 对于关联容器来说,不需要做内存拷贝和内存移动。说对了,确实如此。set容器内所有元素都是以节点的方式来存储,其节点结构和链表差不多,指向父节点和子节点。
  • 为何每次insert之后,以前保存的iterator不会失效? iterator这里就相当于指向元素的指针,元素的内存没有变,指向内存的指针当然也不会失效,当然这里排除元素被删除的情况。相对于vector,每一次删除和插入,指针都可能失效。所以一定要记住,不要使用过期的iterator set<int> s; s.insert(3); set<int>::iterator it1 = s.begin(); cout << *it1 << endl; s.insert(1); //虽然插入1后,1在3的前面。但是it1指向的元素的内存。而set内所有的元素以节点 //方式存储,节点结构合链表差不多,插入和删除元素不需要做内存的移动,只需节点做 //变换即可 //牢记这个原则:不要使用过期的iterator。 cout << *it1 << endl; s.insert(2); 这里档次打印的it1结果都是3.
  • 当数据元素增多时,set的插入和搜索速度变化如何? set中查找是使用二分查找,也就是说,如果有16个元素,最多需要比较4次就能找到结果,有32个元素,最多比较5次。

相关函数

  • equal_range() 返回>=制定元素的第一个元素指针和>制定元素的第一个元素的指针。返回的是pair类型,如果哪个返回失败,就会等于end()的值。 pair<set<int>::iterator, set<int>::iterator> p1=s.equal_range(4); if (p1.first != s.end()) { cout <<">=4 is "<< *p1.first << endl; } if (p1.second != s.end()) { cout << ">4 is " << *p1.second << endl; }
  • insert
    • insert(key_value) 将key_value插入到set中 ,返回值是pair<set<int>::iterator,bool>bool标志着插入是否成功,而iterator代表插入的元素的定位器。 pair<set<int>::iterator, bool> p2=s.insert(7); if (p2.second) { cout <<"insert success"<< *p2.first << endl; }
    • inset(first,second) 将定位器first到second之间的元素插入到set中,返回值是void
  • lower_bound(key_value) 是>=值的第一个元素指针
  • upper_bound(key_value) upper_bound是>值的第一个元素指针 cout << *s.lower_bound(5) << " " << *s.upper_bound(5) << endl;

测试案例一

#include "iostream"
using namespace std;
#include "set"
#include "vector"
//迭代器遍历
void print(set<int>& s) {
    for (set<int>::iterator it = s.begin(); it != s.end(); it++) {
        cout << *it <<" ";
    }
    cout << endl;
}
int main()
{
    cout << "---------插入----------" << endl;
    set<int> s;
    s.insert(3);
    set<int>::iterator it1 = s.begin();
    cout << *it1 << endl;
    s.insert(1);
    //虽然插入1后,1在3的前面。但是it1指向的元素的内存。而set内所有的元素以节点
    //方式存储,节点结构合链表差不多,插入和删除元素不需要做内存的移动,只需节点做
    //变换即可
    //牢记这个原则:不要使用过期的iterator。
    cout << *it1 << endl;
    s.insert(2);
    s.insert(5);
    s.insert(6);
    print(s);
    cout << "---------equal_range----------" << endl;
    pair<set<int>::iterator, set<int>::iterator> p1=s.equal_range(4);
    if (p1.first != s.end()) {
        cout <<">=4 is "<< *p1.first << endl;
    }
    if (p1.second != s.end()) {
        cout << ">4 is " << *p1.second << endl;
    }
    set<int>::iterator it = s.begin();
    //不可以随机访问,关联型数据结构。红黑二叉树
    //it=it+4;
    cout << "---------erase----------" << endl;
    s.erase(it);
    print(s);
    cout << "---------insert及其返回值----------" << endl;
    pair<set<int>::iterator, bool> p2=s.insert(7);
    if (p2.second) {
        cout <<"insert success"<< *p2.first << endl;
    }
    print(s);
    cout << "---------lower_bound、upper_bound----------" << endl;
    //lower_bound是>=值的最小指针  upper_bound是>值的最小指针
    cout << *s.lower_bound(5) << " " << *s.upper_bound(5) << endl;
    return 0;
}

结果:

set_test1.png

测试案例二

#include "string"
#include "iostream"
#include "set"
using namespace std;
class Student {
private:
    string name;
    int number;
public:
    Student(int number, string name) {
        cout << "构造" << number << endl;
        this->number = number;
        this->name = name;
    }
    Student(const Student& student) {
        this->number = student.getNumber();
        this->name = student.getName();
    }

    void print()const {
        cout << this->number << " "<<this->name << endl;
    }

    string getName()const {
        return this->name;
    }

    int getNumber()const  {
        return this->number;
    }
};
//函数对象
struct StuCmp{
    bool operator()(const Student &first,const Student& second) {
        return first.getNumber() > second.getNumber();
    }
};

//遍历
void print(set<Student, StuCmp>& s) {
    for (set<Student, StuCmp>::iterator it = s.begin(); it != s.end(); it++) {
        it->print();
    }
}
int main()
{
    set<Student, StuCmp> set;
    Student stu1(3, "third");
    Student stu2(1, "first");
    Student stu3(2, "second");
    set.insert(stu1);
    set.insert(stu2);
    set.insert(stu3);
    print(set);
    return 0;
}

结果:

set_test2.png

multiset

set集合中一个值只能出现一次,而multiset集合中一个值可以出现多次。

  • set::insert(key)的返回值是一个pair<iterator, bool>,其中pair中的bool成员表明了key被插入之前,set中是否已存在相同的key。根据我在VS2010上的实验结果,如果set中已经存在相同key的元素,那么插入操作是会失败的,新的元素不会被插进去。而multiset::insert的返回值只是一个iterator,插入操作总是会成功的。
  • multiset::count(key)的返回值可能大于1。
  • multiset::size()的返回值是多重集合的势(cardinality),即multiset中元素的个数,而不是值的个数。比如,{1, 1, 2}的size是3,而不是2。
  • multiset::erase(key)会将对应的key全部删掉,所以对{1, 1, 2}调用erase(1)之后,它就变成了{2}。
  • 只要key存在于集合中,set::equal_range(key)的返回值pair<iterator1, iterator2>总是会有++iterator1 == iterator2。但是对multiset来说就不一定了。
  • 如果使用自定义类型,则需要在构造时候传入函数对象或者在自定义类型中重载<操作符。注意:函数要加const限定符。

什么时候需要用multiset?当然是需要用set,但是又允许重复key存在的时候了。什么时候用set?我的答案是:需要随时往容器中插入元素,随时对元素进行快速查找,又需要按某种顺序对元素进行遍历的时候

示例

int main() {
    multiset<Student, StuCmp> s;
    Student stu1(3, "third");
    Student stu2(1, "first");
    Student stu3(2, "second");
    Student stu4(2, "second_2");
    s.insert(stu1);
    s.insert(stu2);
    multiset<Student,StuCmp>::iterator res= s.insert(stu3);
    cout << "--------插入结果---------" << endl;
    res->print();
    res= s.insert(stu4);
    cout << "--------插入结果---------" << endl;
    res->print();
    cout << "--------遍历---------" << endl;
    print(s);
    Student stu5(2, "second_3");
    cout << "--------count方法---------" << endl;
    cout << "count(5)=" << s.count(stu5) << endl;;
    return 0;
}

这里的Student和StuCmp沿用Set中的定义。编译后发现出错:

multi_set_error.png

发现是StuCmp的问题,函数的const修饰符漏了。修改后

struct StuCmp{
    bool operator()(const Student &first,const Student& second) const{
        return first.getNumber() > second.getNumber();
    }
};

运行结果:

multi_set_test3.png

list

list是一个线性双向链表结构,它的数据由若干个节点构成,每一个节点都包括一个信息块(即实际存储的数据)、一个前驱指针和一个后驱指针。它无需分配指定的内存大小且可以任意伸缩,这是因为它存储在非连续的内存空间中,并且由指针将有序的元素链接起来。由于其结构的原因,list 随机检索的性能非常的不好,因为它不像vector 那样直接找到元素的地址,而是要从头一个一个的顺序查找,这样目标元素越靠后,它的检索时间就越长。检索时间与目标元素的位置成正比。虽然随机检索的速度不够快,但是它可以迅速地在任何节点进行插入和删除操作。因为list 的每个节点保存着它在链表中的位置,插入或删除一个元素仅对最多三个元素有所影响,不像vector 会对操作点之后的所有元素的存储地址都有所影响,这一点是vector 不可比拟的。

  • 不使用连续的内存空间这样可以随意地进行动态操作
  • 可以在内部任何位置快速地插入或删除,当然也可以在两端进行push 和pop
  • 不能进行内部的随机访问,即不支持[ ] 操作符和vector.at()
  • 相对于verctor 占用更多的内存

示例

void print(list<Student> l) {
    for (list<Student>::iterator it = l.begin(); it != l.end(); it++) {
        it->print();
    }
}
struct PrintStu{
    bool operator()(const Student& stu)const  {
        stu.print();
        return true;
    }
};
int main()
{
    list<Student> l;
    Student stu1(1, "first");
    Student stu2(2, "second");
    Student stu3(3, "third");
    Student stu4(4, "fourth");
    l.push_back(stu1);
    l.push_front(stu2);
    l.push_back(stu3);
    l.push_front(stu4);
    print(l);
    cout << "---pop_back、pop_front-------" << endl;
    Student s=l.back();
    s.print();
    l.pop_back();
    s = l.front();
    s.print();
    l.pop_front();
    cout << "----for_each------" << endl;
    for_each(l.begin(), l.end(), PrintStu());
    return 0;
}

结果:

list.png

这里使用了for_each函数算法。需要引入#include<algorithm>头文件

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习算法与Python学习

python: 函数详解

def square(x): return x**2 >>> square <function square at 0x031AA230> >>> dir(sq...

4947
来自专栏Java帮帮-微信公众号-技术文章全总结

【选择题】Java基础测试二(15道)

【选择题】Java基础测试二(15道) 11.对于构造方法,下列叙述正确的是:(AC) A. 构造方法的方法名必须与类名相同; B. 构造方法必须用void...

39710
来自专栏python3

python 内置函数

基本的数据操作基本都是一些数学运算(当然除了加减乘除)、逻辑操作、集合操作、基本IO操作,然后就是对于语言自身的反射操作,还有就是字符串操作。

1042
来自专栏python学习之旅

Python笔记(十):正则表达式

正则表达式对比工具 https://pan.baidu.com/s/1XIPyF1vFSj5PACPx9zW8_g (一)      正则表达式符号和特殊字符 ...

3455
来自专栏Python小屋

Python中表达式int(&#39;0x10, 36)的值是。。。

在Python中,int()可用来把实数转换为整数,或者把数字字符串按指定进制转换为十进制数,详见文末的相关阅读。 然而,下面的代码又应该如何解释呢? >>> ...

2996
来自专栏python成长之路

列表常用操作

1744
来自专栏JavaEE

redis学习之redis基本数据类型前言:数据类型详解:

1102
来自专栏佳爷的后花媛

数组(更新...)

在学习语言时,我们都会遇到数组.大学期间学过C,C++,Java,C#.这些语言中都学了数组,那时候用的不多,概念比较模糊,现在又学了php,里面也有数组,就打...

1133
来自专栏猿人谷

数组与指针

一、数组        数组是由类型名、标识符和维数组成的复合数据类型,类型名规定了存放在数组中的元素类型,维数则指定数组中包含的元素个数。        数组...

2088
来自专栏程序员互动联盟

【编程基础】Java初始化有何玄机?

对于Java的初始化顺序大家应该清楚,之前在网站上面有专门的讲解,大家可以通过文章下面的“查看原文”来阅读。 初始化顺序总结起来就是: 1、无继承情况的初始化顺...

3649

扫码关注云+社区

领取腾讯云代金券