Visual C++ .Net and GNU C++
Md. Mahmud Ahsan
Containers and algorithms:
Like many class libraries, the STL includes container classes: classes whose purpose is to contain other objects. The STL includes the classes vector, list, deque, set, multiset, map, multimap, hash_set, hash_multiset, hash_map, and hash_multimap. Each of these classes is a template, and can be instantiated to contain any type of object.
Iterators
In the example of reversing a C array, the arguments to reverse are clearly of type double*. What are the arguments to reverse if you are reversing a vector, though, or a list? That is, what exactly does reverse declare its arguments to be, and what exactly do v.begin() and v.end() return?
The answer is that the arguments to reverse are iterators, which are a generalization of pointers. Pointers themselves are iterators, which is why it is possible to reverse the elements of a C array. Similarly, vector declares the nested types iterator and const_iterator. In the example above, the type returned by v.begin() and v.end() is vector<int>::iterator. There are also some iterators, such as istream_iterator and ostream_iterator, that aren’t associated with containers at all.
Concepts and Modeling
One very important question to ask about any template function, not just about STL algorithms, is what the set of types is that may correctly be substituted for the formal template parameters. Clearly, for example, int* or double* may be substituted for find’s formal template parameter InputIterator. Equally clearly, int or double may not: find uses the expression *first, and the dereference operator makes no sense for an object of type int or of type double. The basic answer, then, is that find implicitly defines a set of requirements on types, and that it may be instantiated with any type that satisfies those requirements. Whatever type is substituted for InputIterator must provide certain operations: it must be possible to compare two objects of that type for equality, it must be possible to increment an object of that type, it must be possible to dereference an object of that type to obtain the object that it points to, and so on.
Find isn’t the only STL algorithm that has such a set of requirements; the arguments to <for_each.html> and <count.html>, and other algorithms, must satisfy the same requirements. These requirements are sufficiently important that we give them a name: we call such a set of type requirements a concept, and we call this particular concept Input Iterator <InputIterator.html>. We say that a type conforms to a concept, or that it is a model of a concept, if it satisfies all of those requirements. We say that int* is a model of Input Iterator because int* provides all of the operations that are specified by the Input Iterator requirements.
Reference:
Silicon Graphics Computer Systems, Inc.
Hewlett-Packard Company
The STL documentation classifies components in two ways.
Categories are a classification by functionality. The categories are:
Container, Iterator, Algorithm, Function, Object, Utility, Adaptor, Allocator.
Component types are a structural classification: one based on what kind of C++ entity (if any) a component is. The component types are:
Type (i.e. a struct or class) , Function , Concept
Sequence
A Sequence is a variable-sized Container whose elements are arranged in a strict linear order. It supports insertion and removal of elements.
Vector
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
main(){
vector <int> v;
vector <int> ::iterator p; // creating iterator
v.push_back(10); v.push_back(20); // insert element
cout << v[0] << endl; // we can use vector like array
// to sort vector elements
sort(v.begin(), v.end()); // sort algo define in algorithm
// using iterator, access all elements of the vector
for (p = v.begin(); p != v.end(); ++p)
cout << *p << ” “;
cout << v.size() << endl; // return the size of the vector
cout << v.capacity() << endl; //capacity of the vector
cout << v.empty() << endl; // checks vector empty or not
v.pop_back(); // removes the last element of the vector
v.clear(); // erase all the elements }
Vector Members: iterator insert(iterator pos,const T& x); //Erases the element at position pos. iterator erase(iterator pos); //Erases all of the elements.
List A list is a doubly linked list.
#include <iostream>
#include <list>
using namespace std;
int main(){
list <int> L;
list <int> ::iterator i;
// insert element at the front
L.push_front(10); L.push_front(30);
// insert element at the end
L.push_back(20); L.push_back(40);
for(i = L.begin(); i != L.end(); ++i)
cout << *i << endl;
cout << “First Element: ” << L.front();// first element
cout << “Last Element: ” << L.back();// last element
L.pop_front(); // removes element at the front
L.pop_back(); //removes element at the end
L.insert(++L.begin(), 100); //insert 100 before position
// remove all element that are equal 100
L.remove(100);
L.unique(); // remove duplicate item except the first one
L.sort(); // sort the linked list, built in function
L.reverse(); // reverse the order of elements
cout << “Size: ” << L.size(); // give the size of list
//another way to represent each element
copy(L.begin(), L.end(), ostream_iterator<int>(cout, ” “));
cout << “IS Empty: ” << L.empty() << endl; // Check empty
L.clear(); // erase all the elements
} Members:
template<class BinaryPredicate> void sort(BinaryPredicate comp);
Comp must be a comparison function that induces a strict weak ordering This function sorts the list *this according to Comp. The sort is stable, that is, the relative order of equivalent elements is preserved.
Deque A deque is very much like a vector: like vector, it is a sequence that supports random access to elements, constant time insertion and removal of elements at the end of the sequence, and linear time insertion and removal of elements in the middle.
#include <iostream>
#include <deque>
using namespace std;
int main(){
deque <int> q;
q.push_back(5); // insert element at the end
q.push_front(1); // insert element at the front
q.insert(q.begin() + 2, 10);
// insert element at the given position
// could be use as like as array []
for (int i = 0; i < q.size(); ++i)
cout << q[i] << endl;
q.pop_front(); // removes the first element
q.pop_back(); // removes the last element
q.clear(); // erase all the elements
} //Erases the element at position pos. iterator erase(iterator pos); // Erases the range [first, last) iterator erase(iterator first, iterator last);
Bitset
#include <iostream>
#include <bitset>
using namespace std;
int main(){
// <12> means the size of the bitset
bitset <12> x; //initially all bits are zero
cout << “Enter a 12-bit bitset in binary: ” << endl;
cin >> x;
cout << “x = ” << x << endl;
cout << “As ulong: ” << x.to_ulong() << endl; // convert unsign long
cout << “Count: ” << x.count() << endl; // numbers of bit that are set
for (int i = 0; i < x.size(); ++i)
cout << x[i] << endl;
}
Stack
#include <iostream>
#include <stack>
using namespace std;
int main(){
stack <int> s;
s.push(10); s.push(20); // insert item at top of the stack
cout << “Top: ” << s.top(); // return the top element
s.pop(); // removes the top element
cout << “Size: ” << s.size(); // size of the stack
cout << “Is Empty: ” << s.empty(); // checks empty
}
Queue
#include <iostream>
#include <queue>
using namespace std;
int main(){
queue <int> q;
q.push(10); q.push(20) ;
// Inserts x at the back of the queue.
//Returns the element at the front of the queue,
cout << “Front: ” << q.front();
//Returns the element at the back of the queue
cout << “Back: ” << q.back();
q.pop(); //Removes the element at the front of the queue
cout << “Size: ” << q.size(); // size of the stack
cout << “Is Empty: ” << q.empty(); // checks empty
}
Priority Queue It is guaranteed that the top element is the largest element in the priority_queue.
#include <iostream>
#include <queue>
using namespace std;
int main(){
priority_queue <int> p;
p.push(10); p.push(20) ;
//Inserts X into the priority_queue.
//Returns a const reference to the element at the top
cout << “Top: ” << p.top() << endl;
p.pop(); //Removes element at the top of the priority_queue
cout << “Size: ” << p.size(); // size of the stack
cout << “Is Empty: ” << p.empty(); // checks empty
}
Set
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
struct ltstr { bool operator()(const char* s1, const char* s2) const { return strcmp(s1, s2) < 0; } }; int main() { const int N = 6; const char* a[N] = {"isomer", "ephemeral", "prosaic", "nugatory", "artichoke", "serif"}; const char* b[N] = {"flat", "this", "artichoke", "frigate", "prosaic", "isomer"}; set<const char*, ltstr> A(a, a + N); // create a set set<const char*, ltstr> B(b, b + N); set<const char*, ltstr> C; cout << "Set A: "; copy(A.begin(), A.end(), ostream_iterator<const char*>(cout, " ")); cout << endl; cout << "Set B: "; copy(B.begin(), B.end(), ostream_iterator<const char*>(cout, " ")); cout << endl; cout << "Union: "; set_union(A.begin(), A.end(), B.begin(), B.end(), ostream_iterator<const char*>(cout, " "), ltstr()); cout << endl; cout << "Intersection: "; set_intersection(A.begin(), A.end(), B.begin(), B.end(), ostream_iterator<const char*>(cout, " "), ltstr()); cout << endl; set_difference(A.begin(), A.end(), B.begin(), B.end(), inserter(C, C.begin()), ltstr()); cout << "Set C (difference of A and B): "; copy(C.begin(), C.end(), ostream_iterator<const char*>(cout, " ")); cout << endl;
}
//set_union, set_intersection, set_difference are algorithm
Multimap Multimap is a key : value pairs. Here, key is automatically arranged by lexicographical or ascending order.
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main(){
multimap <string, int> m;//create a map
multimap <string, int> ::iterator p;
m.insert (pair <string, int> (“mahmud”, 01));
m.insert (pair <string, int> (“fuad”, 02));
string name; int pos;
cin >> name >> pos;
m.insert (pair <string, int> (name, pos)); // insert
for (p = m.begin(); p != m.end(); ++p)
cout << p->first << ” ” << p->second << endl;
// p->first is the key and p->second is the data
cout << "Number of Elements (“fuad”):" << m.count("fuad") << endl; //count number of elements whose key is given(“fuad”)
}
Members:
void erase(iterator pos); //Erases the element pointed to by pos. void clear(); // Erases all of the elements. iterator find(const key_type& k); //Finds an element whose key is k.
Algorithm count: Count finds the number of elements in [first, last) that are equal to value.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int A[] = { 2, 0, 4, 6, 0, 3, 1, -7 };
const int N = sizeof(A) / sizeof(int);
cout << “Number of zeros: ” << count(A, A + N, 0) << endl;
}
swap: Assigns the contents of a to b and the contents of b to a.
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int x = 1;
int y = 2;
cout << x << ” ” << y << endl;
swap(x, y); //swaping x and y
cout << x << ” ” << y << endl;
}
replace: Replace replaces every element in the range [first, last) equal to old_value with new_value.
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int x[] = {1, 2, 3, 1, 5, 7};
copy(x, x+6, ostream_iterator <int> (cout, ” “));
replace(x, x+6, 1, 100); // replace 1 by 100
cout << endl;
copy(x, x+6, ostream_iterator <int> (cout, ” “));
}
fill:
Fill assigns the value value to every element in the range [first, last).
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
vector<double> V(4);
fill(V.begin(), V.end(), 137); //filling by 137 to each element
copy(V.begin(), V.end(), ostream_iterator <double> (cout, ” “));
}
reverse: Reverse reverses a range.
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main(){
char str[] = “Koi mill gayaaaa”;
cout << str << endl;
reverse(str, str + strlen(str));
cout << str << endl;
string a(“mahmud ahsan”);
string b(a);
cout << a << endl;
reverse(b.begin(), b.end());
cout << b << endl;
}
sort:
complexity: O(N log(N))
#include <iostream>
#include <algorithm>
using namespace std;
inline bool comp(int a, int b){
return a > b;
}
int main(){
int a[] = {10, 2, 1, 3, 5};
sort(a, a+5); // ascending order sorting
sort(a, a+5, comp); // modifying comp (‘>’ for) descending order
copy(a, a+5, ostream_iterator <int> (cout, ” “));
}
stable sort:
stable_sort is stable: it preserves the relative ordering of equivalent elements. That is, if x and y are elements in [first, last) such that x precedes y, and if the two elements are equivalent (neither x < y nor y < x) then a postcondition of stable_sort is that x still precedes y.
#include <iostream>
#include <cctype>
#include <string>
#include <algorithm>
using namespace std;
inline bool lt_nocase(char c1, char c2) {
return tolower(c1) < tolower(c2);
}
int main()
{
char A[] = “fdBeACFDbEac”;
int N = strlen(A);
stable_sort(A, A+N, lt_nocase);
printf(“%s\n”, A);
// The printed result is “”AaBbCcdDeEfF”.
}
binary search:
Binary_search is a version of binary search: it attempts to find the element value in an ordered range [first, last) It returns true if an element that is equivalent to value is present in [first, last) and false if no such element exists.
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(){
string a[3] = {“mango”, “black berry”, “jackfruit”};
sort(a, a + 3); //don’t forget to sort first
if (binary_search(a, a + 3, “mango”))
cout << “Item Found” << endl;
else
cout << “Not Found” << endl;
}
//Before using these algorithms items must be sorted in ascending order.
set union:
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(){
string a[] = {“mahmud”, “fuad”, “emon”, “mehedi”};
string b[] = {“fuad”, “emon”};
sort(a, a+4); sort(b, b+2); // must sorted
set_union(a, a+4, b, b+2, ostream_iterator <string > (cout, ” “));
}
set intersection:
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(){
string a[] = {“mahmud”, “emon”, “fuad”};
string b[] = {“mehedi”, “emon”, “ifti”};
sort(a,a+3); sort(b, b+3); // don’t forget to sort
set_intersection(a,a+3, b, b+3, ostream_iterator<string>(cout, ” “));
}
set difference:
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(){
string s1[] = {“mahmud”, “emon”, “fuad”};
string s2[] = {“mehedi”, “emon”, “ifti”};
sort (s1, s1+3); sort(s2, s2+3); // recall sort before using these algo
set_difference(s1, s1+3, s2, s2+3, ostream_iterator <char* >(cout, ” “));
}
make_heap: and sort heap:
Make_heap turns the range [first, last) into a heap
Sort_heap turns a heap [first, last) into a sorted range
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int A[] = {1, 4, 2, 8, 5, 7};
const int N = sizeof(A) / sizeof(int);
make_heap(A, A+N);
copy(A, A+N, ostream_iterator<int>(cout, ” “));
cout << endl;
sort_heap(A, A+N);
copy(A, A+N, ostream_iterator<int>(cout, ” “));
cout << endl;
}
min and max:
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int mn = min(10, 5);
int mx = max(5, 10);
cout << “Min: ” << mn << ” ” << “Max: ” << mx << endl;
}
next_permutation:
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
char items[] = {‘A’, ‘B’, ‘C’};
while (next_permutation(items, items+3)){
copy(items, items+3, ostream_iterator<char>(cout, “”));
cout << endl;
}
}
Think Different 