文档章节

极客班C++ STL(容器)第二周笔记

NILYANG
 NILYANG
发布于 2016/04/15 07:30
字数 1207
阅读 117
收藏 2

极客班 C++ STL (容器算法)第二周笔记

标签(空格分隔): C++


1. 容器(下)

1.1 Stack

a. 概述

Stack 是一种先进先后出(First In Last Out)的数据结构,只有一个出口。 特点:

  • 支持的操作有
      • push , pop , top
  • 只能访问顶端元素,不允许便利
  • 要使用Stack,必须引入<stack> 头文件(标准库)

#include<stack>
int main()
{
   std::stack<int> s; //必须提供泛化参数
   s.push(1); //将1压栈
   s.pop();   //弹出栈顶元素
   s.size();  //获取栈大小
   return 0;     
}

b. Stack的底层数据结构(1)

查看标准库头文件,我们可以知道,STL stack是以deque作为默认底层结构的:

     // TEMPLATE CLASS stack
template<class _Ty,
	class _Container = deque<_Ty> >
	class stack
	{	// LIFO queue implemented with a container
           //...
        }

联系我们在C++ OOP面向对象设计接触到的方法,这种设计就是一种对既有接口的包装,适配,即采用了adapter模式。该模式在这里是包装了deque,并给出了push/pop/top等栈特有的接口。

由于stack不允许遍历,所以没有iterator。

c. Stack的底层数据结构(2)

在 1.1小节中,我们看到了stack的底层定义,发现在模板参数里的容器选项中,是传入了一个deque<_Ty>作为默认参数。 所以,我们除了deque<T>,list<T>其实也是可以拿来作为底层的数据结构的。

//e.g.

std::stack<int, std::list<int>> s;
s.push(1);
s.pop();
s.top();
s.size();


1.2 Queue

a. 概述

Queue呢,就是一种先进先出的数据结构, 有两个出口。 - 支持四种操作:push(增加元素),移除元素(pop),获取最前面的元素(front),获取最后面的元素(back) - 只能访问最前或者最后的元素 - 需要引入标准库<queue>才可以使用


#include<queue>
int main()
{
    std::queue<int> q;//初始化一个存放int型别的队列
    q.push(1); //插入元素
    q.pop();   //移除元素
    q.back();  //获取最后一个元素
    q.front(); //获取最前面的元素
}

b. queue的底层数据结构(1)

查看标准库,我们可知,与stack一样,queue也是包装了deque<T>


	    	// TEMPLATE CLASS queue
template<class _Ty,
	class _Container = deque<_Ty> >
	class queue
	{	    // FIFO queue implemented with a container
            //...
        }

有了这一层的认识,我们可以知道,由于不允许遍历,和stack一样所以queue也没有迭代器(iterator)。

c. queue的底层数据结构(2)

stack类似,queue也是可以以list作为底层数据结构的。具体示例暂时不给出了(接口不变,只是换了底层实现)。

1.3 Map and Multimap

1.3.1 Map 概述

Map的特性

  • 是一种关联容器,存储的是key/value pair
  • 不允许key重复
  • map存储的对象必须是具有可排序性的
		// TEMPLATE CLASS map
template<class _Kty,
	class _Ty,
	class _Pr = less<_Kty>,
	class _Alloc = allocator<pair<const _Kty, _Ty> > >
	class map
		: public _Tree<_Tmap_traits<_Kty, _Ty, _Pr, _Alloc, false> >
	{	// ordered red-black tree of {key, mapped} values, unique keys
           //...
        }

其中,

  • _Kty 就是对应的键key
  • _Ty 就是对应的值value
  • _Pr 对应的排序算法,默认是less<T>算法,即按_Kty排序,那么,_Kty必须要实现比较操作符operator <
    • 我们也可以自定义算法(通过仿函数来实现)
  • _Alloc 内存分配算法(针对这个键值对的)

1.3.2 例子

//STL_test.h

//map value
struct Employee {
    Employee(){}
    Employee(const std::wstring& wszName):Name(wszName){}
    std::wstring Name;
    void print() const
    {
        std::wcout << Name << "\n";
    }
};

//仿函数,定义比较大小
struct ReversId :public std::binary_function<int, int, bool>
{
    bool operator()(const int& key1, const int &key2)
    {
        return (key1 <= key2) ? false : true;
    }
};

//for_each 打印
struct FunctorPrintMapValue{
    void operator()(const std::pair<int, Employee> pair)
    {
        pair.second.print();
    }
};


//STL_test.cpp

int main()
{
    const int size = 3;
    std::pair<int, Employee> items[size] = {
        std::make_pair(1, Employee(L"Tom")),
        std::make_pair(2, Employee(L"Jerry")),
        std::make_pair(3, Employee(L"Alice"))
    };

    std::map<int, Employee, ReversId> m(items, items + size);
    std::for_each(m.begin(), m.end(), FunctorPrintMapValue());

    system("pause");

    return 0;
}

结果:

打印上面的映射结果

我们可以看出,按照自定义的less算法,确实实现了按key倒排序。

1.4 Set and Multset

set 跟map略有不一样,感觉上像是map的特殊版本,因为,在set中,

  • 存储的对象本身,既是key,又是value
  • 不允许有重复的key
  • set存储的对象,必须是具有可排序性
    • 要达到这个目标,那么存储的对象必须实现了operator <操作符
    • 支持自定义排序行为(通过仿函数实现)
  • 必须是引入<set>标准库,通过std::set 访问

下面是一个示例,接着Employee示例来:

//STL_test.h

//set 按名字比较排序仿函数
struct FunctorEmployeeNameComparer:public std::binary_function<Employee,Employee,bool>
{
    bool operator()(const Employee& EmpLeft, const Employee& EmpRight) 
    {
        return EmpLeft.getName() < EmpRight.getName();
    }
};

//for_each 打印set
struct FunctorPrintSetValue
{
    void operator()(const Employee& emp)
    {
        emp.print();
    }
};

//STL_test.cpp
   
    //2. set
    const int nSize = 4;
    Employee person[] = {
        Employee(L"Tom"),
        Employee(L"Jerry"),
        Employee(L"Alice"),
        Employee(L"Tony")
    };
    std::set<Employee, FunctorEmployeeNameComparer> epSet(person, person + nSize);
    
    std::for_each(epSet.begin(), epSet.end(), FunctorPrintSetValue());
    

结果:

上述set打印出的结果

2. STL整体结构,仿函数(仿函数适配器),binder1st

3. binder2nd, mem_fun, mem_fun_ref,一些注意的问题

4. 泛型算法_非变异算法

© 著作权归作者所有

NILYANG
粉丝 14
博文 100
码字总数 19038
作品 0
杭州
高级程序员
私信 提问
C++ STL编程轻松入门 5

2.2.3 第三版:唯美主义的杰作   事态的发展有时候总会趋向极端,这在那些唯美主义者当中犹是如此。首先声明,我并不是一个唯美主义者,提供第二版程序的改进版,完全是为了让你更深刻的感...

暖冰
2015/11/21
61
0
C++ STL编程轻松入门 4

 2.2.2 第二版:工业时代--组件化大生产   我们应该庆幸自己所生活的年代。工业时代,科技的发展所带来的巨大便利已经影响到了我们生活中的每个细节。如果你还在以原始人类的方式生活着,...

暖冰
2015/11/21
76
0
泛型编程与设计新思维

作者: 徐景周 转帖: http://www.vckbase.com/document/viewdoc/?id=955 前言 永远记住,编写代码的宗旨在于简单明了,不要使用语言中的冷僻特性,耍小聪明,重要的是编写你理解的代码,理解...

ValueError
2011/01/12
360
1
STL list链表的用法详解

------------------------------------------------------------------------------- 原来... STL list链表的用法详解 本文以List容器为例子,介绍了STL的基本内容,从容器到迭代器,再到普通...

nao
2014/04/10
289
0
Boost简介

本博客(http://blog.csdn.net/livelylittlefish )贴出作 者(三二一@小鱼)相关研究、学习内容所做的笔记,欢迎广大朋友指正! Boost简介 是什么? Boost是一个功能强大、构造精巧、跨平台...

晨曦之光
2012/03/09
476
0

没有更多内容

加载失败,请刷新页面

加载更多

一套基于SpringBoot+Vue+Shiro 前后端分离 开发的代码生成器

一、前言 最近花了一个月时间完成了一套基于Spring Boot+Vue+Shiro前后端分离的代码生成器,目前项目代码已基本完成 止步传统CRUD,进阶代码优化: 该项目可根据数据库字段动态生成 controll...

郑清
51分钟前
7
0
javascript-十六进制随机颜色

<script> // 编写一个函数,获得一个十六进制的随机颜色的字符串(如#20CD4F) // function randomColor(){ // var r = random(0,255).toString(16); // var g = random(0,255).toString(16......

ACKo
52分钟前
3
0
springBoot +mybatis 出现sql 语句在数据库可以查询到,但是赋值到实体类上就没有的情况?

1.不要老是反复查看自己是否写错了,为啥有的能出来有的出不来? 可以查看配置文件中是否配置全: 如果在application.yml 文件中是如下配置: mybatis: mapper-locations: classpath:mapp...

kuchawyz
今天
3
0
正则表达式

一、RegExp对象 进行验证和查找的API 1、创建对象: (1)用/创建(直接量):var reg=/正则/ig,表达式固定不变时使用 (2)用new创建:var reg=new RegExp(‘正则’,‘ig’),表达式需要...

wytao1995
今天
3
0
实战限流(guava的RateLimiter)

关于限流 常用的限流算法有漏桶算法和令牌桶算法,guava的RateLimiter使用的是令牌桶算法,也就是以固定的频率向桶中放入令牌,例如一秒钟10枚令牌,实际业务在每次响应请求之前都从桶中获取...

程序员欣宸
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部