STL

• 迭代器
• priority_queue
• vector
• pair
• map
• set
• multiset
• bitset

迭代器

详情

priority_queue

基于二插堆的实现的优先队列

手写堆

struct num{
    int id;
    int val;
}queue[1000001];
int tail=1;
void shift_up(int x){
    while(x/2>=1){
        if(queue[x].val<queue[x/2].val){
            swap(queue[x],queue[x/2]);
            x/=2;
        }else{
            break;
        } 
    }
    return ;
}
void shift_down(int x,int n){
    while(x*2<=n){
        int t=x*2;
        if(t+1<=n&&queue[t+1].val<queue[t].val){
            t++;
        }
        if(queue[x].val>queue[t].val){
            swap(queue[x],queue[t]);
            x=t;
        }else{
            break;
        }
    }
    return ;
}
void push(num x){
    queue[tail++]=x;
    shift_up(tail-1);
    return ;
}
void pop(){
    swap(queue[1],queue[tail-1]);
    tail--;
    shift_down(1,tail-1);
}

头文件

#include<queue>

运算符重载

内部使用了小于号，默认是大根堆

重载小于号为小根堆

struct node{
  int dis;
  int x;
  bool operator < (const node &x )const {
    return dis>x.dis;
  };
};
priority_queue<node > q;

相关函数操作

变量名.empty();//判断优先队列中是否为空，为空则返回假，非空则为真
变量名.top();//返回堆顶元素，大根堆为最大的，小根堆为最小的
变量名.push(x);//将元素 x 放入优先队列中
变量名.pop();//将堆顶元素弹出
变量名.size();//返回堆中的元素个数

时间复杂度

插入删除$O(logn)$

vector

是封装动态数组的顺序容器

$vector$存储是自动管理的，按需自动扩张

头文件

#include<vector>

相关函数

vector<T1> x; //定义一个变量名为x的vector数组
变量名.begin();//返回容器的起始迭代器
变量名.end();//返回容器的末尾迭代器
变量名.front();//访问第一个元素
变量名.back();//访问最后一个元素
变量名.empty();//判断容器是否为空，为空则为真，非空则为假
变量名.size();//返回容器的元素数
变量名.clear();//清除容器
变量名.insert();//插入元素
变量名.erase();//擦除元素
变量名.push_back();//在容器末尾添加元素
//比较
< <= == >= > != ;//可以执行正常的值的比较

定义

$vector$的空间是动态变化的

vector<int > q(K,1);//d定义一个名为q长度为k的vector数组，并将其前K个赋值为1
int a[10]={0,2,1,3,2,3,1,2,2};
vector<int > q(a,a+5);//将a数组的前5项赋值给q
vector<T1 > x(&n,&m);//可以将顺序存储数据结构的先后地址传给vector 进行赋值操作

初始化

#include<iostream>
#include<vector>
#include<cstdio>
using namespace std;
int main()
{
  vector<int > q(10,1);
  for(int i=0;i<=20;++i){
    cout<<i<<' '<<q[i]<<endl;
  }
  return 0;
}

在定义$vector$数组时进行初始化时，此时$vector$中已经有预定义的大小，即$push\_back$时只能在定义的大小之后插入

可以发现，未被初始化的$vecotr$的值是不确定的

当我们对未存在的索引进行赋值操作时，会出现错误，但访问时只是值不确定

访问

$vector$可以想正常数组一样进行索引访问与修改

$vector$可以进行迭代器的顺序访问，访问方式为指针的间接访问$*$

vector<int > q;
vector<int >::iterator t;
for(t=q.begin;t!=q.end();t++){
   	cout<<i<<' '<<*t<<endl;
}

插入与删除

变量名$.insert()$;变量名$.erase()$

【时间复杂度】$O(n)$暴力

vector<int > q;
insert(q.begin(),100);//在begin前插入元素100
insert(q.begin(),2,100);//在begin前插入数量为2的元素100
vector<int > a(5,100);
insert(q.begin(),a.begin(),a.end());//将a整个vector插入q前
int arr[10]={100,232,231};
insert(q.begin(),a,a+2);//将a开头的3个数插入q前

栗子：

#include <iostream>
#include <vector>
using namespace std;
void print_vec(vector<int> &vec)
{
  vector<int >::iterator iter;
  for (iter=vec.begin();iter!=vec.end();++iter) {
    cout << ' ' << (*iter);
  }
  cout << '\n';
  return ;
}
 
int main ()
{
    vector<int> vec(3,100);
    print_vec(vec);
 
    vector<int >::iterator  it = vec.begin();
    it = vec.insert(it, 200);
    print_vec(vec);
 
    vec.insert(it,2,300);
    print_vec(vec);
 
    it = vec.begin();
 
    vector<int> vec2(2,400);
    vec.insert(it, vec2.begin(), vec2.end());
    print_vec(vec);
 
    int arr[] = { 501,502,503 };
    print_vec(vec);
}

pair

类模版，提供一个单元存储两个相异类型的途径

其内部封装为一个结构体

• 第一个值称为$first$
• 第二个值称为$second$

头文件

#include<utility>

相关函数

pair<T1,T2>x(n,m);//创建一个first类型是T1,second类型是T2的pair对象x
//并分别用n,m对first,second 赋值
x.first;//引用第一个成员值first 
x.second;//引用第二个成员值second 
make_pair(x,y);//创建一个first=x,second=y的pair对象
operator = ;// 赋值操作
< <= == >= > != ;//比较操作，依次对first，second 按字典序比较
tie(x,y)=函数；//当pair作为返回值时，可以用tie来进行接受

#include<iostream>
#include<utility>
#define N 100010
using namespace std;
pair<int ,string >q[N];
int main()
{
  int n;
  cin>>n;
  for(int i=1;i<=n;++i){
    int x;
    string s;
    cin>>x>>s;
    q[i]=make_pair(x,s);
    cout<<q[i].first<<' '<<q[i].second<<'*'<<endl;
  }
  for(int i=1;i<=n;++i){
    for(int j=i+1;j<=n;++j){
      if(q[i]==q[j]){
        cout<<i<<' '<<j<<endl;
      }
    }
  }
  cout<<(q[1]<q[2])<<' '<<(q[2]>q[3])<<endl;
  return 0;
}
/*
10 
1 hasdiuhas
2 adifos
3 hiofidos
4 nsdija
3 hiofidos
6 asidja
7 ashdihas
8 hsda
1 hasdiuhas
4 nsdija
*/

map

$map$是一个有序键值容器

$map$的内部实现是一颗红黑树，可以实现对数据的排序功能，建立$key-value$的映射关系

根据键值来引用而不是索引

• 第一个我们称为关键字（键），每个关键字在$map$中只能出现一次

• 第二个我们称为该关键字的键值

$map$中插入的元素默认是按关键字升序排列

对于$map$与$multimap$的迭代器，可以这样进行访问:

map<int ,string > q1;
multimap<int ,string >q2;
q1>first,q1->second;
q2->first,q2->second;
(*q1).first,(*q1).second;
(*q2).first,(*q2).second;

头文件

#include<map>

相关函数

变量名.begin();//返回指向起始的迭代器
变量名.end();//返回指向末尾的迭代器（最后一个元素的后一个位置）
变量名.operator =; //给容器赋值
变量名.operator[];//访问或者插入指定的元素
变量名.empty();//检查容器是否为空，为空则返回假，非空则为真
变量名.size();//返回容器中的元素个数
变量名.clear();//清空容器
变量名.inser();//插入元素
变量名.erase();//删除元素
变量名.lower_bound();//指向首个大于等于给定键的元素的迭代器
变量名.upper_bound();//指向首个大于给定键的元素的迭代器
变量名.equal_range();//返回特定键值的取值范围
变量名.find();//查找特定键的元素
变量民.count();//返回特键的元素的数量

变量名$.operator[]$

【时间复杂度】$logn$

变量名.【键】=值

当键存在时，会覆盖当前键的键值；当键不存在时，插入一对如此的键对

变量名$.insert()$

【时间复杂度】$logn$

插入键对，如果键已经存在，则插入失败，即不插入，保持原来的键对

插入时需要配合$pair$

$insert()$的返回值是$pair<iterator,bool>$,当插入的键值已经存在时，$bool$值为$false$

当插入的键值未存在，$bool$值为$true$

#include<iostream>
#include<map>
using namespace std;
map<int ,string >s;
int main()
{
  int n;
  cin>>n;

  for(int i=1;i<=n;++i){
    int n;string x;
    cin>>n>>x;
    if(i%2==1)
      s[n]=x;//operator []
    else
      s.insert(pair<int ,string>(n,x));//insert
  }

  pair<map<int,string >::iterator,bool> t;//return pair<iterator,int >
  t=s.insert(make_pair(2,"dbaushsahdua"));
  cout<<t.first->first<<' '<<t.second<<endl;
  t=s.insert(make_pair(11,"adasdasdaf"));
  cout<<t.first->first<<' '<<t.second<<endl;

  cout<<s.empty()<<endl;//.empty()
  cout<<s.size()<<endl;//.size()
  map<int,string >::iterator iter;
  for(iter=s.begin();iter!=s.end();++iter){
    cout<<iter->first<<' '<<iter->second<<endl;
  }
  s.erase(s.begin(),s.end());
  cout<<s.empty()<<endl;
  return 0;
}
/*
10
4 hasidhas
2 jofos
3 josdja
8 iosajhda
1 ansdkna
9 klahsdia
5 jhdsfkjhsd
6 jhsidja
7 hdioaoi
10 sdahioasjh
*/

变量名$.find()$

【时间复杂度】$logn$

当键值存在时，返回其迭代器，当不存在时，返回与$.end()$的值相同

即存在可以判断是否存在键值的方法

//查找是否存在键值为(x)的set
map<int,string> q;
map<int,string>::iterator iter;//定义迭代器
iter=find(x);//.find()
if(iter==q.end()){
    cout<"no"<<endl;
}

变量名$.count()$

【时间复杂度】$logn$

由于$map$不允许存在重复的关键字，所以返回值为$1$或者$0$

可以用来判断是否存在需要查询的键

map<int ,string > q;
if(q.count(x)==1){ return 1;} 
else return 0;

变量名$.erase()$

可以删除给出的迭代器的元素

可以传出给定的迭代器的范围内的元素

可以删除给定的键值的元素

map<int ,string > s;
map<int ,string >::iterator iter;
......
s.earse(1);//删除特定键值的元素
s.erase(iter);//删除迭代器指定的元素
s.erase(s.begin(),s.end());
//遍历容器中的元素
for(iter=s.begin();iter!=s.end();++iter){
    输出；
	erase(iter)
}
..上为错误写法
在stl中，已经被删除的迭代器便失去了作用
正确写法：
for(iter=s.begin();iter!=s.end();){
    输出；
   	iter=s.erase(iter);//删除之后会返回后一个元素的迭代器
    erase(itera++);//可能会有锅
}
#include <iostream>
#include <map>
using namespace std;
int main ()
{
  std::map<char,int> mymap;
  std::map<char,int>::iterator it;

  // insert some values:
  mymap['a']=10;
  mymap['b']=20;
  mymap['c']=30;
  mymap['d']=40;
  mymap['e']=50;
  mymap['f']=60;

  it=mymap.find('b');
  mymap.erase (it);                   // erasing by iterator

  mymap.erase ('c');                  // erasing by key

  it=mymap.find ('e');
  mymap.erase ( it, mymap.end() );    // erasing by range

  // show content:
  for (it=mymap.begin(); it!=mymap.end(); ++it)
    cout << it->first << " => " << it->second << '\n';

  return 0;
}

变量名$.lower\_bound()\qquad\&\&\qquad$ 变量名 $.uppper\_bound()$

【时间复杂度】$logn$

$lower\_bound:$返回首个大于或者等于键的元素的迭代器,找不到则返回尾后迭代器$.end()$

$upper\_bound:$返回首个大于键的元素的迭代器,找不到则返回尾后迭代器$.end()$

#include<iostream>
#include<cstdio>
#include<utility>
#include<map>
using namespace std;
map<int,string > q;
int n;
int main()
{
  scanf("%d",&n);
  for(int i=1;i<=n;++i){
    int x;string s;
    cin>>x>>s;
    q[x]=s;
  }
  map<int ,string >::iterator iter;
  iter=q.lower_bound(4);
  cout<<iter->first<<' '<<iter->second<<endl;
  iter=q.upper_bound(4);
  cout<<iter->first<<' '<<iter->second<<endl;
  return 0;
}
/*
10
1 ansdkna
2 jofos
3 josdja
4 hasidhas
5 jhdsfkjhsd
6 jhsidja
7 hdioaoi
8 iosajhda
9 klahsdia
10 sdahioasjh
*/

变量名$.equal\_range()$

返回特定键值的取值范围

其返回值为$pair$,$.first$可由$lower\_bound$得到，$.second$可由$upper\_bound$得到

// map::equal_range
#include <iostream>
#include <map>
using namespace std;
int main ()
{
  map<char,int> mymap;

  mymap['a']=10;
  mymap['b']=20;
  mymap['c']=30;

  pair<map<char,int>::iterator,map<char,int>::iterator> ret;
  ret = mymap.equal_range('b');

  cout << "lower bound points to: ";
  cout << ret.first->first << " => " << ret.first->second << '\n';

  cout << "upper bound points to: ";
  cout << ret.second->first << " => " << ret.second->second << '\n';

  return 0;
}

multimap

一个有序键值容器，允许含有相同键值的键对、

内部默认按第一关键字排序，但是对第二关键字并不排序，即按输入稳定

头文件

#include<map>

相关函数

变量名.begin();//返回指向起始的迭代器
变量名.end();//返回指向末尾的迭代器（最后一个元素的后一个位置）
变量名.operator =; //给容器赋值
变量名.empty();//检查容器是否为空，为空则返回假，非空则为真
变量名.size();//返回容器中的元素个数
变量名.clear();//清空容器
变量名.inser();//插入元素
变量名.erase();//删除元素
变量名.lower_bound();//指向首个大于等于给定键的元素的迭代器
变量名.upper_bound();//指向首个大于给定键的元素的迭代器
变量名.equal_range();//返回特定键值的取值范围
变量名.find();//查找特定键的元素
变量民.count();//返回特键的元素的数量

相对于$map$而言，没有$operator []$的操作，因为可能存在相同键值的键对

变量名$.insert()$

$multiset$的返回值是一个迭代器，返回的是插入的键对的迭代器

不同于$map$的是，$map$返回的是一个$pair$

#include<iostream>
#include<map>
using namespace std;
multimap<int ,string >s;
int main()
{
  int n;
  cin>>n;

  for(int i=1;i<=n;++i){
    int n;string x;
    cin>>n>>x;
    s.insert(pair<int ,string>(n,x));//insert
  }

  multimap<int,string >::iterator t;//return iterator
  t=s.insert(make_pair(2,"dbaushsahdua"));
  cout<<t->first<<' '<<t->second<<endl;
  t=s.insert(make_pair(11,"adasdasdaf"));
  cout<<t->first<<' '<<t->second<<endl;

  cout<<s.empty()<<endl;//.empty()
  cout<<s.size()<<endl;//.size()
  multimap<int,string >::iterator iter;
  for(iter=s.begin();iter!=s.end();++iter){
    cout<<iter->first<<' '<<iter->second<<endl;
  }
  s.erase(s.begin(),s.end());
  cout<<s.empty()<<endl;
  return 0;
}
/*
10
4 hasidhas
2 jofos
3 josdja
8 iosajhda
1 ansdkna
9 klahsdia
5 jhdsfkjhsd
6 jhsidja
7 hdioaoi
10 sdahioasjh
*/

变量名$.erase()$

可以实现键值，迭代器以及迭代器范围的删除

有所不同的是

对与键值的删除，会将所有的相同键值的键对删除；对于迭代器只会删除一个，即指定的迭代器不会影响与其相同键值的其它键对

// erasing from multimap
#include <iostream>
#include <map>
using namespace std;
int main ()
{
  multimap<char,int> mymultimap;

  // insert some values:
  mymultimap.insert(pair<char,int>('a',10));
  mymultimap.insert(pair<char,int>('b',20));
  mymultimap.insert(pair<char,int>('b',30));
  mymultimap.insert(pair<char,int>('c',40));
  mymultimap.insert(pair<char,int>('d',50));
  mymultimap.insert(pair<char,int>('d',60));
  mymultimap.insert(pair<char,int>('e',70));
  mymultimap.insert(pair<char,int>('e',90));
  mymultimap.insert(pair<char,int>('f',80));

  multimap<char,int>::iterator it = mymultimap.find('b');

  mymultimap.erase (it);                     // erasing by iterator (1 element)

  mymultimap.erase ('d');                    // erasing by key (2 elements)

  it=mymultimap.find ('e');
  mymultimap.erase ( it, mymultimap.end() ); // erasing by range

  // show content:
  for (it=mymultimap.begin(); it!=mymultimap.end(); ++it)
    cout << (*it).first << " => " << (*it).second << '\n';

  return 0;
}

变量名$.find()$

$find()$返回的是第一个与输入键值相同的元素的迭代器，与插入的顺序相关

#include <iostream>
#include <map>
using namespace std;
int main ()
{
  multimap<char,int> mymm;

  mymm.insert (make_pair('x',10));
  mymm.insert (make_pair('y',20));
  mymm.insert (make_pair('z',1000));
  mymm.insert (make_pair('z',200));
  mymm.insert (make_pair('z',12230));
  // print content:
  cout << "elements in mymm:" << '\n';
  cout << "y => " << mymm.find('y')->second << '\n';
  cout << "z => " << mymm.find('z')->second << '\n';

  multimap<char ,int >::iterator iter;
  for(iter=mymm.begin();iter!=mymm.end();++iter){
    cout<<iter->first<<' '<<iter->second<<endl;
  }
  return 0;
}

可以发现其内部对第二关键字并没有排序

变量名$.count()$

对$multimap$而言，其返回值可能大于$1$,而$map$只能为$1$或者$0$

// multimap::count
#include <iostream>
#include <map>
using namespace std;
int main ()
{
  multimap<char,int> mymm;

  mymm.insert(make_pair('x',50));
  mymm.insert(make_pair('y',100));
  mymm.insert(make_pair('y',150));
  mymm.insert(make_pair('y',200));
  mymm.insert(make_pair('z',250));
  mymm.insert(make_pair('z',300));

  for (char c='x'; c<='z'; c++)
  {
    cout << "There are " << mymm.count(c) << " elements with key " << c << ":";
    multimap<char,int>::iterator it;
    for (it=mymm.equal_range(c).first; it!=mymm.equal_range(c).second; ++it)
      cout << ' ' << (*it).second;
    cout << '\n';
  }

  return 0;
}

变量名$.equal\_range()$

返回特定键值的取值范围

对于$map$而言，$map$取值范围最多为$2$,而$multimap$则不一定

// map::equal_range
#include <iostream>
#include <map>
using namespace std;
int main ()
{
  map<char,int> mymap;

  mymap['a']=10;
  mymap['b']=20;
  mymap['c']=30;

  pair<map<char,int>::iterator,map<char,int>::iterator> ret;
  ret = mymap.equal_range('b');

  cout << "lower bound points to: ";
  cout << ret.first->first << " => " << ret.first->second << '\n';

  cout << "upper bound points to: ";
  cout << ret.second->first << " => " << ret.second->second << '\n';

  return 0;
}

set

$set$ 的内部实现为红黑树,可以实现对数级别的高效检索

$set$ 中每个元素只包含一个关键字：$set$ 支持高效的关键字查询操作,检查一个给定关键字是否在$set$中

$set$ 中每个元素的值都唯一，而且系统能根据元素的值自动进行排序

$set$ 中数元素的值不能直接被改变,因为$set$中只有键，键即为值，值即为键

头文件

#includ<set>

相关函数

operator = ;//容器间复制操作
变量名.begin();//返回起始元素的迭代器
变量名.end();//返回末尾元素的迭代器
变量名.empty();//判断容器是否为空，为空则为真，非空则为假
变量名.size();//返回容器中的元素个数
变量名.clear();//清空容器
变量名.insert();//插入元素
变量名.erase();//删除元素
变量名.count();//返回特定键的数量
变量名.find();//查找特定键的元素
变量名.lower_bound();//返回首个大于或者等于特定键的元素的迭代器
变量名.upper_bound();//返回首个大于特定键的元素的迭代器
变量名.equal_range();//返回特定键值的取值范围
//按字典序比较set中的值
< <= == >= > != ;//返回bool值

操作实现基本与$map$相同

变量名$.insert()$

【时间复杂度】$logn$

与$map$不同的是，$set$只能通过$insert$来进行插入

$insert()$的返回值是$pair<iterator,bool>$,当键值已经存在时,$bool$值为$false$，插入失败

键值不存在时，$bool$值为$true$，插入成功

#include<iostream>
#include<cstdio>
#include<set>
#include<utility>
#define N 100010
using namespace std;
set<int > q;
int main()
{
  int n;
  scanf("%d",&n);
  for(int i=1;i<=n;++i){
    int x;
    scanf("%d",&x);
    q.insert(x);
  }
  set<int >::iterator iter=q.begin();
  for(;iter!=q.end();iter++){
    cout<<(*iter)<<' ';
  }
  cout<<endl;
  pair< set<int >::iterator ,bool > kk;
  kk=q.insert(2);
  cout<<*kk.first<<' '<<kk.second<<endl;
  kk=q.insert(11);
  cout<<*kk.first<<' '<<kk.second<<endl;
  return 0;
}
/*
10 
10 9 8 7 6 5 4 3 2 1
*/

变量名$.count()$

【时间复杂度】$logn$

与$map$相同，因为不存在相同的键，即返回值为$1$或$0$

可以进行键值是否存在的判断

变量名$.erase()$

【时间复杂度】$logn$

可以进行特定键值的删除

可以进行特定迭代器删除

可以进行特定迭代器范围的删除

#include <iostream>
#include <set>
using namespace std;
int main ()
{
  set<int> myset;
  set<int>::iterator it;

  for (int i=1; i<10; i++) myset.insert(i*10);  
  // 10 20 30 40 50 60 70 80 90

  it = myset.begin();
  ++it;                                         
  // "it" points now to 20

  myset.erase (it);

  myset.erase (40);

  it = myset.find (60);
  myset.erase (it, myset.end());

  cout << "myset contains:";
  for (it=myset.begin(); it!=myset.end(); ++it)
    cout << ' ' << *it;
  cout << '\n';

  return 0;
}

multiset

含有$key$类型对象的有序容器，不同于$set$的是，它允许多个等价的键值

头文件

#include<set>

相关函数

operator = ;//容器间复制操作
变量名.begin();//返回起始元素的迭代器
变量名.end();//返回末尾元素的迭代器
变量名.empty();//判断容器是否为空，为空则为真，非空则为假
变量名.size();//返回容器中的元素个数
变量名.clear();//清空容器
变量名.insert();//插入元素
变量名.erase();//删除元素
变量名.count();//返回特定键的数量
变量名.find();//查找特定键的元素
变量名.lower_bound();//返回首个大于或者等于特定键的元素的迭代器
变量名.upper_bound();//返回首个大于特定键的元素的迭代器
变量名.equal_range();//返回特定键值的取值范围
//按字典序比较set中的值
< <= == >= > != ;//返回bool值

$multiset$与$set$的区别

$multiset$与$set$的区别与$multimap$与$map$的区别十分类似，可参见上述

$multiset$可以存放相同的键值

• $.insert()$

对于$set$而言，返回的$pair$的$second $有可能存在为$0$，即插入失败

对于$multiset$而言，返回的是一个$iterator$，即总会插入成功

• $count()$

对于$set$而言，其返回值只有可能为$1$或者$0$

对于$multiset$而言，可能存在多个相同的键值，即返回值可能大于$1$

• $erase()$

对于$set$而言，每次操作删除的元素最多为1

对于$multiset$指定键值而言，只要为相同的键值都会被删除

对于$multiset$指定迭代器而言，只会删除迭代器指定的元素

• $equal\_rang()$

对于$set$而言，其取值范围最多为2

对于$multiset$而言，取值范围则可能大于$2$

bitset

表示一个$N$位的固定大小序列，可以用标准的逻辑运算符操作$bitset$，并将它与字符串和整数相互转换

头文件

#include<bitset>

相关函数

bitset<N > x;//构造一个N位bit的bitset序列

operator [];//特定元下标的访问
变量名.test();

变量名.all();//检查是否全都为1，是则返回1，否则返回0 -------(C++11)
变量名.any();//检查是否有位被设为1，有则返回1，否则返回0
变量名.none();//检查是否所有位都为0，是则返回1，否则返回0
bitset  all     any     none
0000    0       0       1
0101    0       1       0
1111    1       1       0
变量名.count();//返回设为1的位数
变量名.size();//返回bitset的位数

位操作: 按位或"|"  按位与"&"  按位异或"^"
"|=" "&=" "^="

变量名.set();//设置所有位或指定位为1
变量名.reset();//设置所有位或指定位为0
变量名.flip();//翻转所有位或者指定位

变量名.to_ulong();//返回它转换为unsigned long的结果，如果超出范围则报错

变量名.to_ullong();//返回它转换为unsigned long long的结果，如果超出范围则报错
----(C++11)

变量名.to_string();//返回它转换为string的结果

构造$\&$定义

$bitset$可以进行有参构造，参数可以为整数，字符串，或者$bitset$

$1.$当有参构造时，若参数的二进制表示比$bitset$定义的小，则在$\color{red}{前面}$补$0$

$2.$当有参构造时，若参数的二进制表示比$bitset$大，整数则取$\color{red}{后面}$部分，字符串则取$\color{red}{前面}$部分

• 字符串中的字符只能是$0$或者$1$，否则运行时会抛出异常

$3.$当有参构造时，若参数为$bitset$,只能为同位数的$bitset$进行赋值操作，否则编译不通过

#include<iostream>
#include<cstdio>
#include<bitset>
#include<cstring>
using namespace std;
int main()
{
    int x=10;
    int b=5;
    bitset<5> bit1=(x);
    bitset<10> bit2=(b);
    cout<<bit1<<endl;
    cout<<bit2<<endl;
    cout<<"***********"<<endl;
     // 整数位数比bitset小，前面补0
    b=1003;
    bit1=b;
    bit2=b;
    cout<<bit1<<endl;
    cout<<bit2<<endl;
    cout<<"***********"<<endl;
    //整数位数比bitset大，截取后面
    string s1="101101";
    char s2[100010]="110010";
    bitset<10> bit3(s1);
    bitset<5> bit4(s2);
    cout<<bit3<<endl;
    cout<<bit4<<endl;
    cout<<"***********"<<endl;
    // 字符串位数比bitset小，前面补0
    // 字符串位数比bitset大，截取前面
    // 字符串中只能为0，1字符
    // bit3=s1; 此操作会报错，字符串只能初始化，不能赋值
    bit1=bit4;
    cout<<bit1<<endl;
    cout<<bit4<<endl;
    //同位数的bitset可以相互赋值
    // bit1=bit2; 此操作会报错，两bitset 位数不相同
    return 0;
}
/*
01010
0000000101
***********
01011
1111101011
***********
0000101101
11001
***********
11001
11001
*/

$operator[\ ]\&$变量名$.test()$

下标从右至左，下标从$0$开始

• $operator[\ ]$可以访问特定元素的下标，可以对下标元素进行修改

#include <iostream>
#include <bitset>
using namespace std;
int main()
{
    bitset<8> b1(42);
    cout<<b1<<endl;
    for (int i = 0;i<b1.size();++i) {
        cout<<"b1["<< i <<"]: "<<b1[i]<<'\n';
    }
    b1[0] = true; // 通过 bitset::reference 修改首位
    cout << "After setting bit 0, the bitset holds " << b1 << '\n';
}
/*
00101010
b1[0]: 0
b1[1]: 1
b1[2]: 0
b1[3]: 1
b1[4]: 0
b1[5]: 1
b1[6]: 0
b1[7]: 0
After setting bit 0, the bitset holds 00101011
*/

• $.test(pos)$可以访问位置$pos$，返回$1$或$0$

$.test()$不同于$operator[\ ]$的是，$.test()$可以进行边界的检查

如果访问越界，会抛出异常$std::out\_of\_range$

位操作

• 进行两个$bitset$之间的二进制与，或及异或

**| & ^ 按位或 ，按位与 ，按位异或 **

只限于对拥有相同大小$N$的$bitset$定义

#include <bitset>
#include <iostream>
using namespace std; 
int main()
{
    bitset<4> b1("0110");
    bitset<4> b2("0011");
    cout << "b1 & b2: " << (b1 & b2) << '\n';
    cout << "b1 | b2: " << (b1 | b2) << '\n';
    cout << "b1 ^ b2: " << (b1 ^ b2) << '\n';
    return 0;
}
/*
b1 & b2: 0010
b1 | b2: 0111
b1 ^ b2: 0101
*/

• 进行二进制或，与，异或，左移，右移赋值

|= &= ^= 只限于对拥有相同大小$N$的$bitset$定义

#include <iostream>
#include <bitset>
using namespace std;
int main()
{
    bitset<8> b("01110010");
    cout << "initial value: " << b << '\n'; 
    while (b.any()) {
        while (!b.test(0)) {
            b >>= 1;
        }
        cout << b << '\n';
        b >>= 1;
    }
    return 0;
}
/*
initial value: 01110010
00111001
00000111
00000011
00000001
*/

变量名$.set()$

$.set(pos)$设置所有位，或者指定位为$1$

$1.$当$pos$为空时，将所有位设置为$1$

$2.$当$pos$存在时，设置$pos$位为$1$

• 当$pos$不合法时，抛出异常$std::out\_of\_range$

#include <iostream>
#include <bitset>
using namespace std;
int main()
{
    bitset<8> b;
    for (size_t i = 1; i < b.size(); i += 2) {
        b.set(i);
    }
    cout<<b<<endl;
    b.set();
    cout<<b<<endl;
    return 0;
}
/*
10101010
11111111
*/

变量名$.reset()$

$.reset(pos)$设置所有位，或者指定位为$0$

**类似于$.set(pos)$ **

#include <iostream>
#include <bitset>
using namespace std; 
int main()
{
    bitset<8> b(42);
    cout << "Bitset is         " << b << '\n';
    b.reset(1);
    cout << "After b.reset(1): " << b << '\n';
    b.reset();
    cout << "After b.reset():  " << b << '\n';
    return 0;
}
/*
Bitset is         00101010
After b.reset(1): 00101000
After b.reset():  00000000
*/

变量名$.flip()$

$.flip(pos)$翻转所有位，或者翻转指定位

翻转位，即更改$true$值为$false$并更改$false$值为$true$

等价于在$bitset$一部分或全体上的逻辑非。

$1.$当$pos$为空时，将所有位翻转

$2.$当$pos$存在时，翻转当前$pos$位

• 当$pos$不合法时，抛出异常$std::out\_of\_range$

#include <iostream>
#include <bitset>
using namespace std;
int main()
{
    bitset<4> b;
    cout<<b<<endl;
    cout<<b.flip(0)<<endl;
    cout<<b.flip(2)<<endl;
    cout<<b.flip()<<endl;
    return 0;
}
/*
0000
0001
0101
1010
*/

变量名$.to\_string()$

转换$bitset$ 的内容为$string$

产生的字符串含$N$个字符，其首字符对应最末第$N-1$位而其尾字符对应首位。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<bitset>
using namespace std;
int main()
{
    bitset<10> bit("1010101110");
    string s;
    s=bit.to_string();
    cout<<bit<<endl;
    for(int i=0;i<s.size();++i){
        cout<<i<<' '<<s[i]<<endl;
    }
    return 0;
}
/*
1010101110
0 1
1 0
2 1
3 0
4 1
5 0
6 1
7 1
8 1
9 0
*/

变量名$.to\_ulong()$

转换$bitset$的内容为$unsigned\ long$ 整数

$bitset$的首位对应数的最低位，而尾位对应最高位

#include <iostream>
#include <bitset>
using namespace std;
int main()
{
    for (unsigned int i = 0; i < 10; ++i) {
        bitset<5> b(i);
        bitset<5> b_inverted = ~b;
        cout<<i<<'\t';
        cout<<b<<'\t';
        cout<<b.to_ulong()<<'\t';
        cout<<b_inverted<<'\t';
        cout<<b_inverted.to_ulong()<<endl; 
    }    
    return 0;
}
/*
0	00000	0	11111	31
1	00001	1	11110	30
2	00010	2	11101	29
3	00011	3	11100	28
4	00100	4	11011	27
5	00101	5	11010	26
6	00110	6	11001	25
7	00111	7	11000	24
8	01000	8	10111	23
9	01001	9	10110	22
*/