【C++】数据结构与算法_c++数据结构与算法

string字符串

头文件：<string>
string的定义与初始化

string str="test";
1

字符串长度
返回当前字符串长度有 size() 和 length() 两个函数。

string str="test"
int n1=str.size();
int n2=str.length();
cout<<n1<<" "<<n2<<endl;
1
2
3
4

string访问元素
方法一：直接使用下标访问，比如使用str[2]访问string中第三个字符，下标从0到size()-1。
方法二：使用迭代器进行访问，类似指针：

string str="test";
string::iterator it;
for(it=str.begin();it!=str.end();it++){
	cout<< *it <<" ";
}
1
2
3
4
5

string中的元素操作

• insert(int idx,string str)：在idx位置前插入字符串str
• erase(int idx1,int idx2)：删除从[idx1,idx2)的元素
• erase(int idx)：删除[idx,str.size() )的元素，即删除从idx开始的（包括idx）后面的所有元素
• clear()：将字符串清空
• replace(int pos,int len,string str)：从pos开始（包括pos）往后数len个字符，将其替换成str
  string运算符
  和Java和python差不多。都可以使用“+”连接两个字符串。
  常用函数
• find(string str)：在字符串中寻找特定的字符或字符串的函数，如找到匹配的字符或者字符串则返回对应的开始元素的下标，找不到则返回-1，可以用来代替KMP算法。
• substr(int idx1,int num)：返回从idx下标开始（包括第idx个），往后数num个字符组成的子字符串。

sort()函数

头文件：<algorithm>
sort()用于对已知序列进行排序。默认从小到大排序。但是可以自定义对比函数，从而实现自己的排序。

用法一：
sort(first ,last,comp)函数有三个参数：first和last为待排序序列的起始地址和结束地址；comp为排序方式，可自定义一个对比函数作为回调函数传入，也可以不填写。如果不传入comp，这种方式只能对基本数据类型中int和char数组进行排序。
注意：last应为想要排序序列中最后一位的后一位地址，比如说sort(a+m,a+n)表示对a[m]到a[n-1]的元素进行排序。

用法二：
sort(begin,end,comp)，其中begin是迭代器开始位置，end是迭代器结束位置，comp同样为排序方式。这种方法可以对所有具有迭代器的数据结构进行排序，比如说string，vector，set等。

对于对比函数的设计，我们遵循这样一个法则：当比较函数的返回值为true时，表示的是比较函数的第一个参数将会排在第二个参数前面；返回false的时候，交换两个参数的值，最后使任意两个相邻的元素输入对比函数都返回true，这样就达到的排序的目的。比如说设计一个从大到小排序的对比函数：

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

bool cmp(char a,char b){
    return a<b;
}
int main()
{
    string str="abcd";
    
    sort(str.begin(),str.end(),cmp);

    for(int i=0;i<4;i++){
        cout<<str[i];
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

我习惯记成：return后面为<号时，最终排序结束后的所有相邻元素都满足<号，所以是一个升序排列。return后面为>号时，最终排序结束后，所有相邻元素都满足>号，所以排序结果是一个降序排列。

vector向量

vector是可以根据元素个数自动改变大小的线性序列容器。
vector的定义
头文件是vector，定义一个向量vector的写法是vector<typename> name，其中typename是向量中元素的类型。这一点比较类似Java的泛型。
例子：

#include <vector>

//创建一个数组向量
vector<int> array;
1
2
3
4

vector的状态

• empty()：判断当前向量是否为空
• size()：返回当前向量元素个数

向vector尾部添加或者删除元素

• push_back(typename ele)：向vector尾部插入元素ele
• pop_back()：删除vector尾部最后一个元素

访问vector的元素
方法一：
像数组一样，通过元素的下标访问，下标从0到size()-1
方法二：
通过迭代器访问，迭代器类似指针。

vector元素操作

• insert(iterator iter,typename content)：在任意位置前(迭代器，不能用下标)插入元素content
• insert(iterator iter1,int num,typename content)：在任意位置前插入num个元素
• erase(iterator iter)：删除迭代器iter位置的元素
• erase(iterator iter1,iterator iter2)：删除从迭代器iter1到迭代器iter2前一个元素之间的所有元素，相当于左闭右开。
• clear()：清空向量

vector迭代器操作

• begin()：返回向量中首元素的迭代器
• end()：返回向量中最后一个位置的迭代器

vector的排序
可以使用sort()函数对vector排序，传入的是迭代器，同样可以自定义对比函数。

queue队列

队列是一种线性的序列结构，其存放的元素按照线性的逻辑次序排序。但是队列的操作只限于逻辑上的两端，即新元素值只能从队列的一端插入，并且只能从另一端删除已有的元素。允许队列插入的一端成为队列的尾部，允许队列删除的一端成为队列的头部。
因为对于元素来讲，插入与删除分别叫做出队和入队。队列中各个元素的操作次序必定遵守所谓的 先进先出（First-In First-Out, FIFO 规则，即越早入队的元素将会越早出队，越晚入队的元素将会越晚出队。

queue的定义
队列的头文件是#include<queue>；定义一个队列的写法是queue<typename> name，其中typename是队列元素的类型，它可以是任意数据类型，name是定义的队列的名字。

queue的状态

• empty()：判断一个队列是否为空
• size()：返回队列中元素的个数

添加和删除元素

• push(typename ele)：向定义好的队列尾部添加一个元素ele
• pop()：删除头部元素，并不会返回头部元素

元素的访问
因为只能从队列的头尾两端进行操作，获得头尾两端元素的函数分别是front()和back()。

stack栈

栈也是一种线性序列结构，和向量以及队列不同的是，栈的操作只限于逻辑上特定的一端，即新元素只能从栈的一端插入，也只能从这一端删除已有的元素。禁止操作的一端成为盲端。栈中允许元素插入和删除的一段成为栈顶，禁止操作的盲端称为栈底。元素的删除和插入分别称为 出栈、入栈。由于栈对插入和删除的位置进行了限制，可以看出，栈的各个元素操作次序必定遵守所谓的 后进先出（Last-In First-Out, LIFO） ，即越后入栈的元素将会越早出栈，越先入栈的元素将会越晚出栈。

stack的定义
头文件格式为#include<stack>。定义一个栈stack的写法是stack<typename> name，其中，typename是栈元素的类型，可以是任意数据类型，name是定义栈的名字。

stack的状态

• empty()：返回当前栈是否为空
• size()：返回当前栈中元素个数

stack元素的添加和删除

• push(typename name)：向栈顶部添加新元素
• pop()：删除栈顶元素

stack元素的访问
因为只能对栈顶进行操作，所以只用top()来访问栈顶元素。而队列queue能通过front()和back()访问队头和队尾。

自己写的数据类型：矩阵Matrix

用结构体定义一个矩阵：

struct Matrix{
    int matrix[10][10];
    int row,col;                        //行和列
    Matrix(int n,int o):row(n),col(o) {}//构造函数
};
1
2
3
4
5

初始化一个7*7的矩阵：

Matrix mat(7,7);
1

矩阵乘法：

Matrix Multiply(Matrix mat1,Matrix mat2){
    //根据输入的两个矩阵确定乘积后矩阵的size
    int row=mat1.row;
    int col=mat2.col;
    Matrix mat(row,col);

    //num是两个矩阵相乘时，得到新矩阵中一个数需要进行乘法的数量
    int num=mat1.col;

    for(int i=0;i<row;i++){
        for(int j=0;j<col;j++){
            mat.matrix[i][j]=0;
            for(int k=0;k<num;k++){
                mat.matrix[i][j]+=mat1.matrix[i][k]*mat2.matrix[k][j];
            }
        }
    }

    return mat;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

矩阵加法：

Matrix MatrixAddition(Matrix mat1,Matrix mat2){
    Matrix mat(mat1.row,mat1.col);

    for(int i=0;i<mat1.row;i++){
        for(int j=0;j<mat1.col;j++){
            mat.matrix[i][j]=0;
            //矩阵对应位置相加
            mat.matrix[i][j]+=mat1.matrix[i][j]+mat2.matrix[i][j];
        }
    }
    return mat;
}
1
2
3
4
5
6
7
8
9
10
11
12

打印矩阵：

void PrintMatrix(Matrix mat){
    for(int i=0;i<mat.row;i++){
        for(int j=0;j<mat.col;j++){
            printf("%d ",mat.matrix[i][j]);
        }
        printf("\n");
    }
}
1
2
3
4
5
6
7
8

Java中BigInteger类

初始化对象：

BigInteger number=new BigInteger("99999999999999999999999999999");
1

输出对象：

System.out.println(number);
1

常用方法：
public BigInteger add(BigInteger val) 返回当前大整数对象与参数指定的大整数对象的和

public BigInteger subtract(BigInteger val) 返回当前大整数对象与参数指定的大整数对象的差

public BigInteger multiply(BigInteger val) 返回当前大整数对象与参数指定的大整数对象的积

public BigInteger devide(BigInteger val) 返回当前大整数对象与参数指定的大整数对象的商

public BigInteger remainder(BigInteger val) 返回当前大整数对象与参数指定的大整数对象的余

public int compareTo(BigInteger val) 返回当前大整数对象与参数指定的大整数对象的比较结果，返回值是1、-1、0，分别表示当前大整数对象大于、小于或等于参数指定的大整数。

public BigInteger abs() 返回当前大整数对象的绝对值

public BigInteger pow(int exponent) 返回当前大整数对象的exponent次幂。

public String toString() 返回当前当前大整数对象十进制的字符串表示。

public String toString(int p) 返回当前大整数对象p进制的字符串表示。

二叉树

二叉树每个结点的定义如下：

struct TreeNode{
	ElementType data;	//数据
	TreeNode* leftChild;//左子树
	TreeNode* rightChild;//右子树
};
1
2
3
4
5

二叉树的遍历方式分为前序遍历、中序遍历和后序遍历：
前序遍历：

//先序遍历
void PreOrder(TreeNode* root){
    if(root==NULL){
        return ;
    }
    visit(root->data);
    PreOrder(root->leftChild);
    PreOrder(root->rightChild);
    return ;
}
1
2
3
4
5
6
7
8
9
10

中序遍历：

//中序遍历
void InOrder(TreeNode* root){
    if(root==NULL){
        return ;
    }
    InOrder(root->leftChild);
    visit(root->data);
    InOrder(root->rightChild);
    return ;
}
1
2
3
4
5
6
7
8
9
10

后序遍历：

//后序遍历
void PostOrder(TreeNode* root){
    if(root==NULL){
        return ;
    }
    PostOrder(root->leftChild);
    PostOrder(root->rightChild);
    visit(root->data);
    return ;
}
1
2
3
4
5
6
7
8
9
10

知识点：
1、前序遍历和中序遍历可以唯一确定一个字符串。在前序遍历中，第一个节点必定是二叉树的根节点；而在中序遍历中，该根节点毕竟可以将中序遍历的序列拆分成两个子序列，前一个子序列就是根节点左子树的中序遍历序列，后一个子序列是根节点右子树的中序遍历序列。我们设position为根节点在中序遍历中的位置，那么postion前的所有字符都是左子树的中序遍历，position后的都是右子树的中序遍历，而对于前序遍历来讲，除去前序遍历第一个字符，往后的position个字符是左子树的前序遍历，position+1后的子串是右子树的后序遍历。
例：

先序：abdgcefh--->a  bdg cefh
中序：dgbaechf---->dgb a echf
1
2

2、如果给的是中序遍历和后序遍历，那么也可以唯一确定一棵二叉树，后序遍历中最后一个节点必定是二叉树根节点。该根节点也可以将中序遍历序列分为两个部分，一部分是左子树的中序遍历，另一部分是右子树中序遍历。
3、如果题目中给的是前序遍历和后序遍历，那么无法唯一确定一棵二叉树，除非题目中说这是一个”满二叉树“，即每个节点都有零个或者两个子结点的二叉树，这样的二叉树可以通过前序遍历和后序遍历唯一确定二叉树。前序遍历的第一个节点一定和后序遍历的最后一个节点相同，那么这个节点就是根节点，现在来分离左右子树：如果根节点有左右子树，那么前序遍历第二个节点一定是左子树的根节点，在后序遍历中找到这个结点的位置，即可在后序遍历中分开左子树和右子树。后序遍历中倒数第二个节点一定是右子树的根节点，那么就可以在前序遍历中找到这个节点的位置，即可在前序遍历中分来左子树和右子树。由此递归，直到前序遍历字符串和后序遍历字符串同时为空时return。

二叉排序树

二叉排序树又称为二叉搜索树(Binary Search Tree)，是一种结构特殊的二叉树。一颗非空的二叉排序树有如下特征：
1、若左子树非空，则左子树上的所有结点关键字的值均小于根节点关键字的值。
1、若右子树非空，则右子树上的所有结点关键字的值均大于根节点关键字的值。
3、左右子树本身也是一颗二叉排序树。
如果各个数字的插入顺序不同，那么得到的二叉排序树的形态很可能不同，所以不同的插入顺序对二叉排序树的形态有很重要影响。因为在二叉排序树中，左子树结点值<根节点值<右子树节点值；因此，如果对二叉排序树进行中序遍历，则会得到一个升序序列。这也是二叉排序树名称的由来。通过建立一棵二叉排序树，即可对原本无序的序列进行排序，并实现序列的动态维护。

但是二叉排序树在实际中的应用并不是很多，因为它的最坏情况和线性链表一样，最坏查找时间复杂度是O(n)。所以大部分情况下都会使用它的升级版：平衡二叉树（AVL）和红黑树，这两种树都能把查找的时间复杂度降到O(log(n))。

平衡二叉树（AVL）：在二叉查找树的基础上增加了一条限制：每个结点的左右子树高度之差的绝对值最多为1。

建立二叉查找树：

//向树中插入新节点
TreeNode* Insert(TreeNode* root,int num){
    if(root==NULL){
        root=new TreeNode(num); //插入新节点
    }else if(root->data==num){  //如果有重复值，则直接返回已经存在的节点，不对新节点进行插入
        return root;
    }else if(num<root->data){   //num小于当前节点，则向左子树插入
        root->leftChild=Insert(root->leftChild,num);
    }else{                      //num大于当前节点，则向右子树插入
        root->rightChild=Insert(root->rightChild,num);
    }
    return root;
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF){
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
        }
        //建立二叉排序树
        TreeNode* root=NULL;
        for(int i=0;i<n;i++){
            root=Insert(root,a[i]);
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

优先队列

优先队列的定义：
为了使用标准模板库中的priority_queue，需要在代码中添加头文件，格式为#include <queue>，优先队列依然存在于队列头文件里。定义一个priority_queue的写法是：priority_queue<typename> name，其中typename是优先队列存储的元素类型，name为定义的优先队列的名字。

优先队列的状态：

• size()：返回当前优先队列中元素的个数。
• empty()：返回当前优先队列是否为空。

优先队列中元素的添加、删除与访问

• push()：向优先队列中添加新元素。
• pop()：删除优先队列中优先级最高的元素。
• top()：访问队列中优先级最高的元素。

注意，优先队列之所以叫做“优先队列”，是因为这个队列中的元素自动按照元素的大小优先级排序的，优先级最高的排在最前面，优先级最低的排在最后面，pop()和top()都是对队列首元素进行的操作。而当有新元素使用push()函数插入优先队列时，会根据新元素的优先级插入相应的位置，相当于自动排序，所以保证了队首的元素优先级永远最高。比如对于存储int类型的优先队列来讲，队首元素一定是值最大的int。

虽然看起来和stack栈很像，但是需要注意的是，使用push()函数向栈中添加新元素的时候，并不会按照优先级自动排序，而是按照插入顺序排序，即在栈中严格按照“先进后出”的原则，在优先队列中按照“优先级最高的先出”的元组。

大顶堆与小顶堆
当我们使用

priority_queue<typename> myQueue;
1

创建一个优先队列时，默认创建了一个优先级高先输出的队列，比较函数为less, 它会维持一个大顶堆，优先级最高的在堆顶，对应着队列首部，所以这个队列输出的元素大小顺序是从大到小。

创建小顶堆优先队列法一：
而有时候我们需要一个优先级低先输出的优先队列，那么意味这这个优先队列将维持一个小顶堆，优先级最小的在堆顶，对应着队列首部，所以我们应该这样创建一个小顶堆优先队列：

priority_queue<typename,vector<typename>,greater<typename>> name;
1

比较函数变成了greater，表示最终队列输出元素大小顺序是从小到大。

创建小顶堆优先队列法二：
创建小顶堆还有一种方式，就是在结构体中重载运算符<号。例子：

struct node{
    int data;
    node(int n):data(n){} //构造函数
    bool operator< (node n) const{ //重载<符号
        return data>n.data;
    }
};
1
2
3
4
5
6
7

重载<符号的思想：当节点n的优先级大于本节点时，意味着节点n的data小于本结点的data，即实现了优先级越高，结点值越小。

set集合

1 set特点
集合是一种特殊的数据结构，他和数组很像，确还有很多不同之处：
1、在set中每个元素的值都是唯一的。
2、向set插入数据时，能够根据元素的值自动进行排序。
3、set中数元素的值并不能直接被改变。

2 set的底层
优先队列的底层是二叉堆（大顶堆和小顶堆），而set的底层是红黑树。
1、set的底层是红黑树，属于红黑树中的K模型。
2、map的底层也是红黑树，属于红黑树中的KV模型。

K模型：只能存放同一种数据类型的红黑树
KV模型：能存放两种数据类型的红黑树
1
2

3、set插入重复数据时会忽略掉重复数据，而multiset允许插入重复数据，同样，multiset会将插入的元素自动排序。multiset与set类似，接口也基本一样。
3 set的定义
set模板如下：

template < class T,                        // 表示set里面存放的数据类型
           class Compare = less<T>,        // 仿函数，可以指定让set按照什么方式进行比较数据
           class Alloc = allocator<T>     // 空间配置器，默认是系统提供的
         >
1
2
3
4

需要注意的是第二个参数：仿函数。这个函数表示按照何种方式进行数据的比较，因为set进行遍历是有序的，默认仿函数的比较方式（less）让set遍历的序列是递增的序列。如果想要让set遍历的序列为递减序列，就可以将第二个模板参数改为greater；
另一方面如果set里面存放的是自定义类型，则必须自己实现一个仿函数用于支持两个自定义类型大小的比较，或者在自定义类型中重载运算符。
例子：

//建立一个元素是int类型，并且元素顺序是递增序列的set
set<int> mySet;

//建立一个元素是int类型，但是元素顺序是递减的set
set<int,greater<int>> RmySet;
1
2
3
4
5

4 set常用接口介绍

• insert(typename ele)：向set中插入元素
• begin()：返回set队首的迭代器
• end()：返回set队尾再往后一个位置的迭代器
• rbegin()：返回一个逆序迭代器，指向队尾那个元素的位置
• rend()：返回一个逆序迭代器，指向队首再往前一个位置
• find(typename ele)：找到元素ele所在的位置，返回这个位置的迭代器，如果没有这个元素，则返回end()指向的迭代器。
• erase (iterator position)：删除某个迭代器位置的元素，注意，参数为这个元素的迭代器，比如s.erase(s.find(5));，删除值为5的元素。
• erase (typename ele)：删除某个值。（当multiset删除某个值时，将里面与该值相等的所有数据全部删除）
• erase (iterator first, iterator last)：删除某个区间内所有的值，左开右闭。
• count (typename ele)：统计ele这个元素在set中出现的次数，set的返回值只有0和1。而 multiset的count函数返回该值出现的次数。

5 set遍历方式
可以使用正向迭代器和反向迭代器两种。
正向迭代器：

set<int>::iterator it1 = s.begin();
while (it1 != s.end()){
     cout << *it1 << " ";
     ++it1;
}
1
2
3
4
5

反向迭代器：
反向迭代器是一种反向遍历容器的迭代器。也就是，从最后一个元素到第一个元素遍历容器。
通过操作符重载，反向迭代器将自增（和自减）的含义反过来了：对于反向迭代器，++ 运算将访问前一个元素，而 - - 运算则访问后一个元素。
图源，侵删
那么代码如下：

set<int>::reverse_iterator it1 = s.rbegin();
while (it1 != s.rend()){
     cout << *it1 << " ";
     ++it1;
}
1
2
3
4
5

遍历时需要注意的地方：
1、红黑树的遍历是走的中序，则s.begin()是红黑树的最左结点；
2、s.end()是最后一个数据的下一个位置；
十分感谢STL–set介绍及set的使用的分享。

map映射

map是一个将关键字（key）和映射值（value）形成一对映射后进行绑定存储的容器。在set中已经提到，map的底层使用的是红黑树中的KV模型，所以向map中插入新元素时会按照key进行排序，其查找效率仍然是O(logn)。在STL中还有一个无序映射unordered_map，其底层使用散列表实现的，其期望的查找效率为O(1)。

unordered_map和map操作几乎一样，所以只需要了解map的用法，即可了解unordered_map。在数据量不大时，map的性能能够满足绝大多数的要求，当题目中对性能要求特别高时，只需要将map改成unordered_map。

1 map的定义
为了使用STL中的标准模板库中的map，需要添加头文件#include <map>。定义一个映射map的写法是map<typename T1,typename T2> name。其中typename T1是映射中关键字Key的数据类型，typename T2是映射值的数据类型，name是创建的映射的名字。
例如：map<int int> myMap;
2 map常用接口介绍

• empty()：判断当前映射是否为空
• size()：返回当前映射中元素的个数
• insert(pair<typename1,typename2>(ele1,ele2))：向map中添加一个新元素
• erase(typename1 ele)：删除map中关键字Key为ele的元素
• begin()：返回映射中首元素的迭代器
• end()：返回映射中为元素后一个位置的迭代器
• find(typename1 ele)：寻找关键字Key为ele的元素，如果找到则返回该元素的迭代器，如果没有则返回迭代器end()
• clear()：清空map

3 map元素的访问
1、map内部重载了[]运算符，因此可以通过[key]的方式访问
2、可以使用at(key)的方式访问
3、可以通过迭代器进行访问，iter->first指向key对应的值，iter->second指向value对应的值。

如何清空输入缓冲区

现在最安全的方式还是使用getchar清空输入缓冲区，否则在缓冲区内存残留的字符可能影响下一次输入。
getchar在stdin缓冲区为空时，等待输入，直到回车换行时函数返回。若stdin缓冲区不为空，getchar直接返回。getchar返回时从缓冲区中取出一个字符，并将其转换为int，返回此int值。
比如用getchar吸收scanf留下的空格：

#include <iostream>
#include <cstdio>

using namespace std;

int main()
{
    char a;
    char b;
    scanf("%c",&a);
    b=getchar();//吸收上面scanf留下的回车

    printf("%d %d\n",a,b);
    cout<<a<<" "<<b<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

输入：

a
1

输入如下：

97 10
a
1
2

10是’\n’换行符的ascii码。可以看到，getchar吸收了scanf留下的换行符。同时我们也可以在scanf中将\n加入格式字符串，从而吸收\n，比如scanf("%c\n",&a)。这样就能吸收最后一个换行符了。

万能的清除缓存区的方式：
我们可以在程序中使用while((ch = getchar()) != ‘\n’ && ch != EOF){}来清除缓存中残留的符号。这句话的含义是：当getchar得到缓冲区中第一个字符不是换行符，且这个字符不是文件末尾EOF时，继续去读下个字符，直到读到这个字符是换行符或者是文件末尾时跳出。

注意：读到这个字符是换行符时，已经在缓冲区中把这个换行符弹出来了。
例子：

#include <cstdio>

int main()
{
    char a;
    char b;
    scanf("%c",&a);
    char ch;
    while((ch=getchar())!='\n'&&ch!=EOF){}
    b=getchar();
    printf("%d %d\n",a,b);
    cout<<a<<" "<<b<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

输入：

abcdefg
z
1
2

输出：

97 122
a z
1
2

可以看到while语句将"bcdefg"以及他们后的换行符全部吸收掉了。

fill函数与memset函数的区别

memset函数
按照字节填充某字符，在头文件<cstring>里面。

extern void *memset(void *buffer, int c, int count)
1

buffer：为指针或是数组
c：赋给buffer中字节的值
count：buffer中需要被赋值的字节的数量

因为memset函数按照字节填充，所以一般memset只能用来填充char型数组，（因为只有char型占一个字节）。如果填充int型数组，除了0和-1会正常填充，其他的都不可以。原因如下：

当值为0的时候，因为int是4字节，所以：
二进制补码 00000000 00000000 00000000 00000000 = 十进制 0

当值为-1的时候，十进制-1用一个字节的二进制补码表示为11111111，那么用-1来填充int类型的数组就是：
二进制补码 11111111 11111111 11111111 11111111 = 十进制 -1

当值为1的时候，就不能正常填充了，十进制1用一个字节表示就是00000001，所以对于int的4字节来讲，最终填充完4个字节得到的int为：
二进制补码 00000001 00000001 00000001 00000001 = 十进制 16843009
可见，当填充值是1时，一个int最终的数值是16843009，不是正常填充。

tips：正数的原码符号位为0，负数的原码符号位为1。正数的补码还是原码，即它本身不变。而负数转化为补码的规则是：符号位不变，其他位取反，然后加1。所以二进制补码 11111111 11111111 11111111 11111111的原码是 10000000 00000000 00000000 00000001，也就是十进制的-1。

memset用法示例：

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
int main()
{
    int a[10];
    memset(a,0,sizeof(a));
    for(int i=0;i<10;i++){
        printf("%d ",a[i]);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

输出

0 0 0 0 0 0 0 0 0 0
1

fill函数
fill函数按照单元赋值，将一个区间的元素都赋同一个值。在头文件<algorithm>里面（也有的编辑器可以直接使用，不需要引用头文件）

而fill函数使用方法特别简便：
法一：使用地址，将地址区间中的元素赋同一个值，格式为fill(arr, arr + n, 要填入的内容);。
例子：

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;
int main()
{
    int arr[10];
    fill(arr,arr+10,100);
    for(int i=0;i<10;i++){
        printf("%d ",arr[i]);
    }
    printf("\n");
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

输出：

100 100 100 100 100 100 100 100 100 100
1

法二：使用迭代器，将两个迭代器中间的所有元素赋同一个值，格式为fill(v.begin(), v.end(), 要填入的内容);。
例子：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;
int main()
{
    vector<int> myVector{0,1,2,3,4,5,6,7,8,9};
    fill(myVector.begin(),myVector.end(),100);
    for(int i=0;i<myVector.size();i++){
        printf("%d ",myVector[i]);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

输出：

100 100 100 100 100 100 100 100 100 100
1

参考链接：【C++】fill函数，fill与memset函数的区别