STL具有高性能,高移植性和代码重用性高的优点.

Sorting

sort(startaddress, endaddress)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream> 
#include <algorithm> 

using namespace std; 

void show(int a[]) 
{ 
	for(int i = 0; i < 10; ++i) 
		cout << a[i] << " "; 
} 
int main() 
{ 
	int a[10]= {1, 5, 8, 9, 6, 7, 3, 4, 2, 0}; 
	cout << "\n The array before sorting is : "; 
	show(a); 

	sort(a, a+10); 

	cout << "\n\n The array after sorting is : "; 
	show(a); 

	return 0; 

}

Refer std::sort() for more details.

Searching

binary_search(startaddress, endaddress, valuetofind)

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
// CPP program to implement 
// Binary Search in 
// Standard Template Library (STL) 
#include <algorithm> 
#include <iostream> 

using namespace std; 

void show(int a[], int arraysize) 
{ 
	for (int i = 0; i < arraysize; ++i) 
		cout << a[i] << " "; 
} 

int main() 
{ 
	int a[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 }; 
	int asize = sizeof(a) / sizeof(a[0]); 
	cout << "\n The array is : "; 
	show(a, asize); 

	cout << "\n\nLet's say we want to search for 2 in the array"; 
	cout << "\n So, we first sort the array"; 
	sort(a, a + asize); 
	cout << "\n\n The array after sorting is : "; 
	show(a, asize); 
	cout << "\n\nNow, we do the binary search"; 
	if (binary_search(a, a + 10, 2)) 
		cout << "\nElement found in the array"; 
	else
		cout << "\nElement not found in the array"; 

	cout << "\n\nNow, say we want to search for 10"; 
	if (binary_search(a, a + 10, 10)) 
		cout << "\nElement found in the array"; 
	else
		cout << "\nElement not found in the array"; 

	return 0; 
}

std::bsearch in C++

Important STL Algorithms

C++ Magicians STL

Library in c++ STL

  1. sort(first_iterator, last_iterator) – To sort the given vector.

  2. reverse(first_iterator, last_iterator) – To reverse a vector.

  3. *max_element (first_iterator, last_iterator) – To find the maximum element of a vector.

  4. *min_element (first_iterator, last_iterator) – To find the minimum element of a vector.

  5. accumulate(first_iterator, last_iterator, initial value of sum) – Does the summation of vector elements

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
// A C++ program to demonstrate working of sort(), 
// reverse() 
#include <algorithm> 
#include <iostream> 
#include <vector> 
#include <numeric> //For accumulate operation 
using namespace std; 

int main() 
{ 
	// Initializing vector with array values 
	int arr[] = {10, 20, 5, 23 ,42 , 15}; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	vector<int> vect(arr, arr+n); 

	cout << "Vector is: "; 
	for (int i=0; i<n; i++) 
		cout << vect[i] << " "; 

	// Sorting the Vector in Ascending order 
	sort(vect.begin(), vect.end()); 

	cout << "\nVector after sorting is: "; 
	for (int i=0; i<n; i++) 
	cout << vect[i] << " "; 

	// Reversing the Vector 
	reverse(vect.begin(), vect.end()); 

	cout << "\nVector after reversing is: "; 
	for (int i=0; i<6; i++) 
		cout << vect[i] << " "; 

	cout << "\nMaximum element of vector is: "; 
	cout << *max_element(vect.begin(), vect.end()); 

	cout << "\nMinimum element of vector is: "; 
	cout << *min_element(vect.begin(), vect.end()); 

	// Starting the summation from 0 
	cout << "\nThe summation of vector elements is: "; 
	cout << accumulate(vect.begin(), vect.end(), 0); 

	return 0; 
}

  1. count(first_iterator, last_iterator,x) – To count the occurrences of x in vector.

  2. find(first_iterator, last_iterator, x) – Points to last address of vector ((name_of_vector).end()) if element is not present in vector.

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
// C++ program to demonstrate working of count() 
// and find() 
#include <algorithm> 
#include <iostream> 
#include <vector> 
using namespace std; 

int main() 
{ 
	// Initializing vector with array values 
	int arr[] = {10, 20, 5, 23 ,42, 20, 15}; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	vector<int> vect(arr, arr+n); 

	cout << "Occurrences of 20 in vector : "; 

	// Counts the occurrences of 20 from 1st to 
	// last element 
	cout << count(vect.begin(), vect.end(), 20); 

	// find() returns iterator to last address if 
	// element not present 
	find(vect.begin(), vect.end(),5) != vect.end()? 
						cout << "\nElement found": 
					cout << "\nElement not found"; 

	return 0; 
}

  1. binary_search(first_iterator, last_iterator, x) – Tests whether x exists in sorted vector or not.

  2. lower_bound(first_iterator, last_iterator, x) – returns an iterator pointing to the first element in the range [first,last) which has a value not less than ‘x’.

  3. upper_bound(first_iterator, last_iterator, x) – returns an iterator pointing to the first element in the range [first,last) which has a value greater than ‘x’.

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
// C++ program to demonstrate working of lower_bound() 
// and upper_bound(). 
#include <algorithm> 
#include <iostream> 
#include <vector> 
using namespace std; 

int main() 
{ 
	// Initializing vector with array values 
	int arr[] = {5, 10, 15, 20, 20, 23, 42, 45}; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	vector<int> vect(arr, arr+n); 

	// Sort the array to make sure that lower_bound() 
	// and upper_bound() work. 
	sort(vect.begin(), vect.end()); 

	// Returns the first occurrence of 20 
	auto q = lower_bound(vect.begin(), vect.end(), 20); 

	// Returns the last occurrence of 20 
	auto p = upper_bound(vect.begin(), vect.end(), 20); 

	cout << "The lower bound is at position: "; 
	cout << q-vect.begin() << endl; 

	cout << "The upper bound is at position: "; 
	cout << p-vect.begin() << endl; 

	return 0; 
}

  1. arr.erase(position to be deleted) – This erases selected element in vector and shifts and resizes the vector elements accordingly.

  2. arr.erase(unique(arr.begin(),arr.end()),arr.end()) – This erases the duplicate occurrences in sorted vector in a single line.

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
// C++ program to demonstrate working of erase() 
#include <algorithm> 
#include <iostream> 
#include <vector> 
using namespace std; 

int main() 
{ 
	// Initializing vector with array values 
	int arr[] = {5, 10, 15, 20, 20, 23, 42, 45}; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	vector<int> vect(arr, arr+n); 

	cout << "Vector is :"; 
	for (int i=0; i<6; i++) 
		cout << vect[i]<<" "; 

	// Delete second element of vector 
	vect.erase(vect.begin()+1); 

	cout << "\nVector after erasing the element: "; 
	for (int i=0; i<5; i++) 
		cout << vect[i] << " "; 

	// sorting to enable use of unique() 
	sort(vect.begin(), vect.end()); 

	cout << "\nVector before removing duplicate "
			" occurrences: "; 
	for (int i=0; i<5; i++) 
		cout << vect[i] << " "; 

	// Deletes the duplicate occurrences 
	vect.erase(unique(vect.begin(),vect.end()),vect.end()); 

	cout << "\nVector after deleting duplicates: "; 
	for (int i=0; i< vect.size(); i++) 
		cout << vect[i] << " "; 

	return 0; 
}

  1. next_permutation(first_iterator, last_iterator) – This modified the vector to its next permutation.

  2. prev_permutation(first_iterator, last_iterator) – This modified the vector to its previous permutation.

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
// C++ program to demonstrate working of next_permutation() 
// and prev_permutation() 
#include <algorithm> 
#include <iostream> 
#include <vector> 
using namespace std; 

int main() 
{ 
	// Initializing vector with array values 
	int arr[] = {5, 10, 15, 20, 20, 23, 42, 45}; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	vector<int> vect(arr, arr+n); 

	cout << "Given Vector is:\n"; 
	for (int i=0; i<n; i++) 
		cout << vect[i] << " "; 

	// modifies vector to its next permutation order 
	next_permutation(vect.begin(), vect.end()); 
	cout << "\nVector after performing next permutation:\n"; 
	for (int i=0; i<n; i++) 
		cout << vect[i] << " "; 

	prev_permutation(vect.begin(), vect.end()); 
	cout << "\nVector after performing prev permutation:\n"; 
	for (int i=0; i<n; i++) 
		cout << vect[i] << " "; 

	return 0; 
}
  1. distance(first_iterator,desired_position) – It returns the distance of desired position from the first iterator.This function is very useful while finding the index.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// C++ program to demonstrate working of distance() 
#include <algorithm> 
#include <iostream> 
#include <vector> 
using namespace std; 

int main() 
{ 
	// Initializing vector with array values 
	int arr[] = {5, 10, 15, 20, 20, 23, 42, 45}; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	vector<int> vect(arr, arr+n); 

	// Return distance of first to maximum element 
	cout << "Distance between first to max element: "; 
	cout << distance(vect.begin(), 
					max_element(vect.begin(), vect.end())); 
	return 0; 
}

Useful Array algorithms

Array in C++ STL

  1. all_of()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// C++ code to demonstrate working of all_of() 
#include<iostream> 
#include<algorithm> // for all_of() 
using namespace std; 
int main() 
{ 
	// Initializing array 
	int ar[6] = {1, 2, 3, 4, 5, -6}; 

	// Checking if all elements are positive 
	all_of(ar, ar+6, [](int x) { return x>0; })? 
		cout << "All are positive elements" : 
		cout << "All are not positive elements"; 

	return 0; 
}
  1. any_of()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// C++ code to demonstrate working of any_of() 
#include<iostream> 
#include<algorithm> // for any_of() 
using namespace std; 
int main() 
{ 
	// Initializing array 
	int ar[6] = {1, 2, 3, 4, 5, -6}; 

	// Checking if any element is negative 
	any_of(ar, ar+6, [](int x){ return x<0; })? 
		cout << "There exists a negative element" : 
		cout << "All are positive elements"; 

	return 0; 

}
  1. none_of()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// C++ code to demonstrate working of none_of() 
#include<iostream> 
#include<algorithm> // for none_of() 
using namespace std; 
int main() 
{ 
	// Initializing array 
	int ar[6] = {1, 2, 3, 4, 5, 6}; 

	// Checking if no element is negative 
	none_of(ar, ar+6, [](int x){ return x<0; })? 
		cout << "No negative elements" : 
		cout << "There are negative elements"; 

	return 0; 
}
  1. copy_n()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// C++ code to demonstrate working of copy_n() 
#include<iostream> 
#include<algorithm> // for copy_n() 
using namespace std; 
int main() 
{ 
	// Initializing array 
	int ar[6] = {1, 2, 3, 4, 5, 6}; 

	// Declaring second array 
	int ar1[6]; 

	// Using copy_n() to copy contents 
	copy_n(ar, 6, ar1); 

	// Displaying the copied array 
	cout << "The new array after copying is : "; 
	for (int i=0; i<6 ; i++) 
	cout << ar1[i] << " "; 

	return 0; 
}
  1. iota()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// C++ code to demonstrate working of iota() 
#include<iostream> 
#include<numeric> // for iota() 
using namespace std; 
int main() 
{ 
	// Initializing array with 0 values 
	int ar[6] = {0}; 

	// Using iota() to assign values 
	iota(ar, ar+6, 20); 

	// Displaying the new array 
	cout << "The new array after assigning values is : "; 
	for (int i=0; i<6 ; i++) 
	cout << ar[i] << " "; 

	return 0; 
}

待续

 上一页

Python ALG NLP