-
Notifications
You must be signed in to change notification settings - Fork 0
/
C++ STL
140 lines (95 loc) · 7.98 KB
/
C++ STL
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include<algorithms>
1.Sort (TC - N*logN)
For Array
sort(arr,arr+n,mycompare);
For Vector and String
Accending order - sort(vector.begin(),vector.end());
Descending order - sort(vector.begin(),vector.end(),mycompare)
bool mycompare(T a,T b)
{ return a>b; }
Partial sort of array and Vector can be done using -
partial_sort(first pos iter, till pos sort,last pos
For Linked List
Accending order - ListName.sort();
Desceding order - ListName.sort(mycompare);
2. Search
Binary Search -
int binary_search(start address,end address,key);
return 1 = key found
return 0 = key not found
int lower_bound(start address,end address,key)
case 1: if key not exist in array/vector
Returns the pointer to position of next higher number then key .
If key is greater the (n-1)th num then it returns n
case 2: If key exist exactly ones
Return the ptr to position of key
in vector pos=return value-vector.begin()
case 3: If key exist multiple times
Returns the ptr to position of first occurence of key
int upper_bound(start address,end address,key)
case 1: if key not exist in array/vector
Returns the position of next higher number then key .
If key is greater the (n-1)th num then it returns n
case 2: If key exist exactly ones
Return the position of next higher number then key
in vector pos=return value-vector.begin()
case 3: If key exist multiple times
Return pointer to first position of next higher number after last occurrence of num
3. Non Manupulating Algorithms ( This algo will not make any change in actual vector or data structure )
I. sort(first pos iterator,last pos iterator)
II. reverse(first_iterator,last_iterator) - For Array , Vector mylist.reverse() - For linked list
III.max_element(first_iterator,last_iterator) - For Array , vector
return the pointer to the maximum element of the array/Vector .
IV.min_element(first_iterator,last_iterator)
return the pointer to the minimum element of the array/vector .
V.accumulate(first_iterator,last_iterator,Initial Sum) - for array and vector
return the sum of elements added with Initial Sum
VI.count(first_iterator,last_iterator,value)
returns the number of times value stored in array / vector
VII. find(first_iterator,last_iterator,value) Array or Vector
return the pointer to the location where element is found
if element is not found in vector it points to vecotr.end() i.e. out of vector
if element is not found in array it points to n'th location i.e. out of array
mapname.find(value) for Map
returns pointer to the pair of data
4. Manupulative Algorithms ( This algo. will make some changes in array or vector )
I.vector.erase(position) only works for vector. Delete element at pos 1 = vector.erase(vector.begin()+1);
II. vector.erase(position 1,position 2) - Delete from pos 1 to pos 2
III. vector.erase(unique(v.begin(),v.end(),v.end())
This removes the duplicate element given that the vector is sorted . Here unique gives the distinct element
but does not resize the vector. resize is done by erase call .
IV. next_permutation(first_iterator,last_iterator) For finding n! permutation of vector or String .
V. Prev_permutation(first_iterator,last_iterator) Can be used to print permutation in reverse .
vI . distance(first_iterator, Iterator to location) Can be used to find position of value while function return
pointer like in max_element,min_element,find.
5. Some new function which can be used for Array , Vector and String
I. all_of(first_iterator,last_iterator,comparator) This function check if every element in array is following some
condition like greater then 0 or not .
Return True - If every element follow perticular functionality given in comparator
else False
comparator example - [](int a){ return a<0; }
II. any_of(first_iterator,last_iterator,comparator)
III. none_of(firsr_iterator,last_iterator,comparator)
IV. copy_n(first_iterator of ar1(array you want to copy), n (no. of element) , first_iterator of ar2(array to which
copy data
This function is used to copy data of one array to another array
V. iota(first_iterator,last_iterator,starting value)
This function initializes the array from staring value in continues like 1,2,3,4,5,6 .
6. valarray is same as vector but the mathematical operations are faster on valarray as compaired to vector
1. apply = apply same functionality to whole vector like increament .
myvector.apply(comparator)
2. sum = To find sum of all element
myvector.sum()
3. min = Returns the min value not pointer
myvector.min()
4. max = Returns the max value
myvector.max()
5. shift = Shift the vector to left or right based on value and it replace deleted value with 0
myvector.shift(2) 2 postion vector will shift to left side
myvector.shift(-2) 2 position vector will shift to right side
This will not make any change in original vector we have to create new vector to store shifted vector
6. cshift = circular shift
myvector.cshift(2) : left side
myvector.cshift(-2) : Right side
7. swap = this can be used to swap two arrays/vectors
vector1.swap(vector2);