stl学习-1

STL学习—侯捷 - STL和泛型编程

可能是因为我的基础比较差，所以感觉课程不是很明了，又在笔记里面加了一些自己的理解和搜索到的其他博主的文章内容。

1 认识headers、版本、重要资源

2 STL体系结构基础介绍

STL六大部件

• 容器 Containers
• 分配器 Allocators
• 算法 Algorithms
• 迭代器 Iterators
• 适配器 Adapters
• 仿函式 Functors

• 容器存放数据，算法通过迭代器(桥梁)对数据进行操作
• 分配器给容器分配内存

vector：

1.什么是vector？

• 向量（Vector）是一个封装了动态大小数组的顺序容器（Sequence Container）。跟任意其它类型容器一样，它能够存放各种类型的对象。可以简单的认为，向量是一个能够存放任意类型的动态数组。
• vector 是向量类型，它可以容纳许多类型的数据，如若干个整数，所以称其为容器。它相当于一个动态的数组,当程序员无法知道自己需要的数组的规模多大时,用其来解决问题可以达到最大节约空间的目的。

2.容器特性

• 顺序序列。顺序容器中的元素按照严格的线性顺序排序。可以通过元素在序列中的位置访问对应的元素。
• 动态数组。支持对序列中的任意元素进行快速直接访问，甚至可以通过指针算述进行该操作。提供了在序列末尾相对快速地添加/删除元素的操作。
• 能够感知内存分配器的(Allocator-aware)。容器使用一个内存分配器对象来动态地处理它的存储需求。

函数实现、用法介绍及使用实例阅读C++ vector使用方法。
用法总结

count_if:

• algorithm下的count_if用于查找满足条件的元素的出现次数，对象包括数组，vector,list,map，等等。
  格式如下：

  count_if(begin,end,cmp);

  其中cmp函数应是一个返回值类型为bool的函数,需要我们自己书写，以此确定我们需要元素的返回条件 p 。如:

  bool cmp(int x)
  {
      if(x满足条件p) return 1;
      else return 0;
  }

部件功能示例

• <>：模板
• container：行11，vector
• allocator：行11，容器vector需要有分配器allocator帮他分配内存
• count_if：行13，algorithm，计算符合条件的元素个数
• adapter：行14，适配器binder — bind2nd()，绑定第二参数，便于与“40”进行比较；适配器negator — not1()，否定第一参数。

前闭后开区间

• begin：指向第一个区间
• end：指向最后一个元素的下一个位置
• interator：泛化的指针

遍历容器元素的新写法：range-based for statement(2011年后，替代上面代码的写法)

使用auto，可直接阅读本标题结尾参考文章

1. auto
   auto 即 for(auto x: range) 这样会拷贝一份 range 元素，而不会改变 range 中元素;

2. auto&
   当需要修改range中元素，用 for(auto& x: range);

3. const auto&
   当只想读取 range 中元素时，使用 const auto&，如：for(const auto&x:range)，它不会进行拷贝，也不会修改range;

4. const auto
   当需要拷贝元素，但不可修改拷贝出来的值时，使用 for(const auto x:range)，避免拷贝开销。

• 形式：

  for(decl : coll){                            //声明 : 集合体(容器)
  	statement
  }

• for(int i : {2, 3, 5, 6, 10, 11}){
      std::cout << i << endl;                 //输出容器的全部元素
  }
  - ```cpp
    for(auto elem : vec){						//auto即for(auto x: range)，拷贝一份range元素											   到x，不会改变range中元素内容。
    	std::cout << elem << std::endl
    }
  

• 示例1：

  #include <iostream>
  #include <vector>
  using namespace std;
  int main() {
      int a[] = { 1,2,3,5,2,0 };
      vector<int>counts(a,a+6);
      for (auto count : counts)
          cout<< count<< " ";
      cout << endl;
      return 0;
  }
  //输出：1 2 3 5 2 0

• 示例2

reference：
https://blog.csdn.net/qq_28087491/article/details/108171017
https://blog.csdn.net/qq_36268040/article/details/107292201

3 容器之分类与各种测试(一)

容器分类

三类：序列式容器(Sequence Containers)、关联式容器(Association Containers)、不定序容器(Unordered Containers)

• 序列式容器：强调值的排序，序列式容器中的每个元素均有固定的位置。 分类：

  • 数组(Array)：array<T,N>表示可以存储 N 个 T 类型的元素。

    注：一旦建立，其长度就是固定不变的，这意味着不能增加或删除元素，只能改变某个元素的值。

    

  • 单端数组，也叫向量(Vector)：vector用来存放 T 类型的元素，是一个长度可变的序列容器，即在存储空间不足时，会自动申请更多的内存。

    注：在尾部增加或删除元素的效率最高（时间复杂度为 O(1) 常数阶），在其它位置插入或删除元素效率较差（时间复杂度为 O(n) 线性阶，其中n为容器中元素的个数）。

    

  • 双端数组(Deque)：deque和 vector相似，但限定插入和删除操作在数组的两端进行的容器。

    注：该容器不仅尾部插入和删除元素高效，在头部插入或删除元素也同样高效，时间复杂度都是 O(1) 常数阶，但是在容器中某一位置处插入或删除元素，时间复杂度为 O(n) 线性阶。

    

  • 链表(List)：：list是一个长度可变的由 T 类型元素组成的序列，一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的，由一系列存储数据元素的数据域和存储下一个结点地址的指针域的节点组成的双向循环链表。

    注：在这个序列的任何地方都可以高效地增加或删除元素（时间复杂度都为常数阶O(1)），但访问容器中任意元素的速度要比前三种容器慢，这是因为 list必须从第一个元素或最后一个元素开始访问，需要沿着链表移动，直到到达想要的元素。

    

  • 栈(Stack)

• 关联式容器：二叉树结构，各元素之间没有严格的物理上的顺序关系。

  multi表示可允许有重复的关键字。

  • set/multiset

    注：set插入数据的同时会返回插入结果，表示插入是否成功；set不可以插入重复数据，而multiset可以。

  

  • map/multimap

    注：map中所有元素都是pair，pair中第一个元素为key（键值），起到索引作用，第二个元素为value（实值）；map不允许容器中有重复key值元素，multimap允许容器中有重复key值元素。

• Unordered Containers
  • Unordered set：不以键值对的形式存储数据，而是直接存储数据元素本身，该容器存储的元素不能重复，且容器内部存储的元素也是无序的。
  • Unordered multiset：和 unordered_set 唯一的区别在于，该容器允许存储值相同的元素。
  • Unordered map：存储键值对 <key, value> 类型的元素，其中各个键值对键的值不允许重复，且该容器中存储的键值对是无序的。
  • Unordered multimap：和 unordered_map 唯一的区别在于，该容器允许存储多个键相同的键值对。

测试：

#include<stdexcept>
#include<string>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<ctime>
#include<map>
using namespace std;
long get_a_target_long()
{
    long target = 0;
    cout<<"target(0~"<<RAND_MAX<<"):";
    cin>>target;
    return target;
}
string get_a_target_string()
{
    long target = 0;
    char buf[10];
    cout<<"target(0~"<<RAND_MAX<<"):";
    cin>>target;
    snprintf(buf, 10, "%ld", target);
    return string(buf);
}
int compareLongs(const void* a, const void* b)
{
    return (*(long*)a - *(long*)b);
}
 
int compareStrings(const void *a, const void *b)
{
    if(*(string*)a > *(string*)b)
        return 1;
    else if(*(string*)a < *(string*)b)
        return -1;
    else
        return 0;
}