偷学来的c++函数

偷学来的c++函数,第1张

偷学来的c 函数

upper_bound、lower_bound

一般升序使用

sort unique

deque 也可以 sort

sort 不单纯是快排,内部很复杂。

STL的sort算法,数据量大时采用快排算法,分段归并排序。一旦分段后的数据量小于某个门槛,就改用插入排序。如果递归层次过深,还会改用堆排序。详见 《STL源码剖析》 P389

所以,可能某些特殊情况下,手写快排会快,再加入一些奇怪的优化等会更快,例如随机化一下打乱有序列,小范围冒泡。

vector<int>a;
sort(a.begin(),a.end());
a.erase(unique(a.begin(),a.end()),a.end());

partial_sort()

stl_algo.h 4672-4691

  template<typename _RandomAccessIterator>
    inline void
    partial_sort(_RandomAccessIterator __first,
		 _RandomAccessIterator __middle,
		 _RandomAccessIterator __last)
    {
      // concept requirements
      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
	    _RandomAccessIterator>)
      __glibcxx_function_requires(_LessThanComparableConcept<
	    typename iterator_traits<_RandomAccessIterator>::value_type>)
      __glibcxx_requires_valid_range(__first, __middle);
      __glibcxx_requires_valid_range(__middle, __last);
      __glibcxx_requires_irreflexive(__first, __last);

      std::__partial_sort(__first, __middle, __last,
			  __gnu_cxx::__ops::__iter_less_iter());
    }

实现排序的平均时间复杂度为\(O(NlogM)\),其中 N 指的是 [first, last) 范围的长度,M 指的是 [first, middle) 范围的长度。

vector<int>a;
dec(i,10,1)a.push_back(i);
partial_sort(a.begin(),a.begin() 3,a.end());
for(auto it:a)cout<<it<<" ";
1 2 3 10 9 8 7 6 5 4

可以像 sort 那样带上自定义函数

vector<int>a;
rep(i,1,10)a.push_back(i);
partial_sort(a.begin(),a.begin() 3,a.end(),greater<int>());
for(auto it:a)cout<<it<<" ";
10 9 8 1 2 3 4 5 6 7	 

is_sorted()

is_sorted() 函数有 2 种语法格式,分别是:

//判断 [first, last) 区域内的数据是否符合 std::less<T> 排序规则,即是否为升序序列
bool is_sorted (ForwardIterator first, ForwardIterator last);
//判断 [first, last) 区域内的数据是否符合 comp 排序规则  
bool is_sorted (ForwardIterator first, ForwardIterator last, Compare comp);

其中,first 和 last 都为正向迭代器(这意味着该函数适用于大部分容器),[first, last) 用于指定要检测的序列;comp 用于指定自定义的排序规则。

注意,如果使用默认的升序排序规则,则 [first, last) 指定区域内的元素必须支持使用 < 小于运算符做比较;同样,如果指定排序规则为 comp,也要保证 [first, last) 区域内的元素支持该规则内部使用的比较运算符。

另外,该函数会返回一个 bool 类型值,即如果 [first, last) 范围内的序列符合我们指定的排序规则,则返回 true;反之,函数返回 false。值得一提得是,如果 [first, last) 指定范围内只有 1 个元素,则该函数始终返回 true。

nth_element

与上面用法类似,复杂度 \(O(n)\),建议记 partial_sort

注意,最后 \(n\)-th 元素在 a.begin() n 的位置,下标从 0 开始

srand(time(NULL));
vector<int>a;
rep(i,1,10)a.push_back(i);
random_shuffle(a.begin(),a.end());
nth_element(a.begin(),a.begin() 4,a.end(),greater<int>());
cout<<a[4]<<endl;

rbegin,back

vector<int>a;
rep(i,1,10)a.push_back(i);
cout<<a.front()<<endl;
cout<<a.back()<<endl;
cout<<*a.begin()<<endl;
cout<<*a.rbegin()<<endl;

set<int>b;
rep(i,1,10)b.insert(i);
cout<<*b.begin()<<endl;
cout<<*b.rbegin()<<endl;

min max

min(a,min(b,c))
min({a,b,c})

C 11,编译器会将其推导为initializer_list类型,产生一个initializer_list的临时对象。

max_element min_element

查找最大值、最小值对应的地址

int a[]={1,4,3,2};
int main()
{
    cout<<max_element(a,a 4)-a<<endl;
    return 0;
}

prev_permutation next_permutation

这个大家应该很熟悉了

值得强调的是时间复杂度,全遍历 \(O(n!)\),单次最坏 \(O(n)\)

do
{
  
}while(next_permutation(a 1,a n 1));

__int128

128位整数

输入输出要手写快读快写

如果有些题中间数据爆了 long long,可以强制转化成 __int128 进行处理

to_string

C 11,将逐个数字转化为字符串,支持double等,详见 basic_string.h 6413-6473

减少手写的时候,忘记特判 0 的尴尬

stoi

将字符串转化为数字,返回一个int类型的数组,如果超出int则会 RE

emplace_back

减少常数的写法

struct TSY
{
    int age;
    TSY(int x)
    {
        age=x;
    }
};
int main()
{
    vector<TSY>save;
    save.emplace_back(21);
    save.push_back(TSY{21});
    return 0;
}

__gcd

看内部实现,如果传__m, __n 的时候其中一个为 0,那么会返回另一个非 0 数

  template<typename _EuclideanRingElement>
    _EuclideanRingElement
    __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
    {
      while (__n != 0)
	{
	  _EuclideanRingElement __t = __m % __n;
	  __m = __n;
	  __n = __t;
	}
      return __m;
    }

__lg

当前数有几位,或者可以说最高位是第几位,如 \(12=(1100)_2\), __lg(12)=3

stl_algobase.h 997-1021

  inline _GLIBCXX_CONSTEXPR int
  __lg(int __n)
  { return sizeof(int) * __CHAR_BIT__  - 1 - __builtin_clz(__n); }

(clz表示Count Leading Zeros,统计前导零个数)

使用注意:__builtin_clz 当参数为0,结果未定义,所以 __lg(0)也会未定义

这个方法可以认为是O(1)的,而且效率比log2 高很多

详细说明:https://www.zhihu.com/question/35361094

另:log(x) e位底返回double类型;log2(x)返回double类型注意精度问题,如:log2((2 ^ 59) - 1) = 59)。

rotate

vector<int>a;
rep(i,1,10)a.push_back(i);
rotate(a.begin(),a.begin() 2,a.end());
for(auto it:a)cout<<it<<" ";

效果

1 2 3 4 5 6 7 8 9 10
3 4 5 6 7 8 9 10 1 2

复杂度 \(O(n)\)

reverse

写字符串常用

string s;
cin>>s;
reverse(s.begin(),s.end());
cout<<s<<endl;

__builtin_popcount

__builtin 内建函数常数小的离谱

统计有多少个位为 1。它使用一张类似基于表的方法来进行位搜索。

shuffle

第 45 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(南京)E.Evil Coordinate

https://ac.nowcoder.com/acm/contest/10272/E

一般比较多的写法:

srand(time(NULL));
random_shuffle(a 1,a n 1);

复杂度 \(O(n)\)

也可以,random库里的:

unsigned seed=chrono::system_clock::now().time_since_epoch().count();
shuffle(save.begin(),save.end(),default_random_engine(seed));

memset fill

极其容易犯错~

这个东西估计很多人不知道怎么用,就知道 memset(a,0,sizeof(a)),想把数组a 中元素全设置成 1,写了个memset(a,1,sizeof(a))

我们要理解一下,memset是将某一块内存中的内容全部设置为指定的值是以字节为单位进行赋值的

int 32位 4字节

填充的时候,每个字节是 0x01,即\([00000001]_2\)

所以不建议这么写,建议使用fill

int arr[maxn];
int main()
{
    fill(arr,arr maxn,1);
    return 0;
}

iota

[arr,arr n-1] 的元素赋值连续递增的值,这个 iotaGO 里也有类似含义,但是用法很不同

iota(arr,arr n,0); // 0 1 2 3 4 5...

next prev

移动迭代器

大部分容器时间复杂度 O(n)

set<int>s;

int main()
{
    rep(i,1,3e5)s.insert(i);
    auto it=s.begin();
    auto newit=next(it,3e5-1);
    cout<<*newit<<endl;
    return 0;
}

isalpha isalnum isdigit

判断字符是否是字母,数字或字母,数字

random库

random库提供了均匀分布、伯努利分布、泊松分布、正态分布等多种分布类型,有兴趣可以自己查一下,不展开讲了

bit库

有很多处理二进制东西比较方便的函数,不过大多数环境跟不上,不展开讲了

https://www.apiref.com/cpp-zh/cpp/header/bit.html

一些不知道怎么描述的技巧

  • cout << a[i][j] << " \n"[j == i]; // " \n"看作char数组。

文章来源:https://www.cnblogs.com/lucius7/p/16350323.html

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复