7/15/08

STL- Standard Template Library Question and answers

Where are std::min() and std::max()?
The Standard Library defines the two template functions std::min() and std::max() in the header. In general, you should use these template functions for calculating the min and max values of a pair. Unfortunately, Visual C++ does not define these function templates. This is because the names min and max clash with the traditional min and max macros defined in . As a workaround, Visual C++ defines two alternative templates with identical functionality called _cpp_min() and _cpp_max(). You can use them instead of std::min() and std::max().To disable the generation of the min and max macros in Visual C++, #define NOMINMAX before #including .

The remove_if() algorithm
The remove_if() algorithms (defined in the standard header ) has the following prototype:

template

ForwardIterator remove (ForwardIterator first,

ForwardIterator last,

Predicate pred);

The first two arguments mark the sequence's beginning and end. The third argument is a predicate. Unlike remove(), remove_if() uses the predicate provided to select the elements it removes. This enables you to remove elements with different values that fall under the same category, e.g., odd numbers, vowels, uppercase letters etc. Using remove_if() is similar to using remove(). The tricky part in is the definition of the predicate. A concrete example will clarify this issue.

Suppose we want to remove all the vowels from a string object. Our predicate has to distinguish between a vowel and a non-vowel. We define the is_vowel predicate as follows:

template

class is_vowel: public unary_function

{

public:

bool operator ()(T t) const

{

if ((t=='a')||(t=='e')||(t=='i')||(t=='o')||(t=='u'))

return true; //t is a vowel

return false; // t is not a vowel

}

};

Our goal is to read a string from the standard input, remove all the vowels therein by using remove_if(), and display the resulting vowel-less string. The first part is straightforward:

#include

#include

#include // for remove_if

using namespace std;

int main()

{

string original;

cin >> original;

//…

Next, we call remove_if() to remove all the vowels from the input string. We create a temporary object of the specialization is_vowel and pass it as the predicate of remove_if():

// move vowels to end and store the position where the vowels start

string::iterator it= remove_if(original.begin(),

original.end(),

is_vowel());

Remember that remove_if() doesn't actually delete elements from a string; it simply moves them to the end and returns an iterator to that position. We use that iterator to mark the logical end of the desired string -- the one without vowels -- and construct a new string from it:

// create new string from original using previous iterator

string no_vowels(original.begin(),it);

cout >> no_vowels;

}

The remove() Algorithm
The Standard Library defines the std::remove() algorithm, which moves desired elements to the front of a container and returns an iterator pointing to the end of the sequence of the desired elements. The elements to be removed are positioned past the sequence's end. remove() is declared in the header as follows:

template

ForwardIterator remove (ForwardIterator first,

ForwardIterator last,

const T& value);


remove() removes all the elements in the range (first, last) that are equal to 'value'. It returns an iterator that points to the end of the resulting range. However, remove() doesn't actually reduce the size of the sequence nor does it erase the removed elements. Instead, it copies the values that are to be retained to the beginning of the sequence, while pushing the “removed” elements past that sequence. remove() returns an iterator that indicates the end of that sequence. In the following example, remove() removes all occurrences of the number eight from a vector containing the following numbers:

3,5,4,6,8,1,8,7


The result is the following sequence:

3,5,4,6,1,7|,8,8


The vertical bar indicates the position of the iterator returned by remove(). As you can see, the elements to the left of the vertical bar are the original sequence except that all occurrences of the number eight were moved to the right of the vertical bar.

#include // for remove

#include

#include

using namespace std;

int main()

{

int arr[] = {3,5,4,6,8,1,8,7};

vector vi(arr,arr+8); // fill vi with arr's elements

vector::iterator seq_end= // store returned iterator

remove(vi.begin(), vi.end(),8); // remove all 8's

vector::iterator seq_beg=vi.begin();

while(seq_beg!=seq_end)

{

cout<<*seq_beg<<“ “; // display the 8-less sequence

++seq_beg;

}

}


The program prints the following sequence:

3 5 4 6 1 7

Factorial Function One of the classic examples of using recursion is calculating a factorial of a number. Here's a typical implementation of this function:

int factorial (int num)

{

if (num==1)

return 1;

return factorial(num-1)*num; // recursive call

}

factorial() calls itself recursively, subtracting 1 from num on each call, until it equals 1. As always, you can use iteration instead of recursion:

int factorial (int num)

{

int result=1;

for (int i=1; i<=num; ++i)

result=result*=i;

return result;

}

The fill() Algorithm The algorithm fill() is declared in as follows:

void fill(ForwardIterator f, ForwardIterator l, const T&);

The arguments f and l mark the sequence's beginning and end, respectively. fill() fills the elements in the sequence with the fixed value T. This algorithm is useful when you want to initialize or reinitialize a sequence with a fixed value. For example, to initialize a char array, use fill() as follows:

#include

char *p = new char[100];

std::fill(p, p+100, '\0'); // zero all characters

This is similar to calling memset(p, 0, 100). Note however, that fill() respects object semantics, unlike memset(). Therefore, you can use it to reinitialize a sequence of objects as well:

#include

#include

#include

std::vector <> vs(100);

std::fill(vs.begin(), vs.end(), "greetings!");

The vector vs initially contains 100 empty strings. fill() assigns a new value: "greetings!" to all the strings in the vector.

Calculating the Difference Between Two Times When you need to compute the time that elapsed between two dates, use the standard function difftime(). This way, you avoid potential bugs such as leap years or Y2K issues. difftime() takes two variables of type time_t, each representing a date, and returns the number of seconds that elapsed between the two. For example:

#include

#include

using namespace std;

int main()

{

time_t now = time(0); // get current time

time_t last_week = now - (60*60*24*7); // a week ago

double seconds = difftime(now, last_week);

cout<

The binary_search Algorithm STL's binary_search() algorithm traverses a sequence and returns a Boolean value indicating whether the sought-after element exists in that sequence. binary_search() is declared in the header as follows:

bool binary_search (ForwardIterator first,

ForwardIterator last,

const T& value)

binary_search() takes two forward iterators that mark the sequence's bounds, and the sought-after value as the third argument. It returns true if the sought-after value exists in the sequence, or false otherwise. In the following example, binary_search() checks whether the integers 5 and 0 exist in a vector of integers:

#include

#include

using namespace std;

int main()

{

int arr[5] = {1,3,4,5,5};

// set a vector from the array

vector vi(arr, arr+5);

// search for 5 and 0 in the vector

bool found = binary_search(vi.begin(), vi.end(), 5);// true

found = binary_search(vi.begin(), vi.end(), 0);// false

}

Calculating the Absolute Value of a Number The standard functions abs() and labs() (declared in ) return the absolute value of int and long, respectively. You can use these functions in computations that need absolute values. For example:

int begin = 0, end = 100;

int offset = abs(begin - end); // offset = 100

Calculating the Maximum of Three Values The max() macro or template takes two values and returns the highest. What if you need to calculate the maximum of three values? You don't need to write a special function template for this purpose. Instead, apply max() to two arbitrary values of the three, and then apply max() once again to the result and the third value:

int l=10, m=11, n=7;

int highest = max(l,max(n,m)); //highest = 11

The unique() Algorithm

STL's unique() algorithm eliminates all but the first element from every consecutive group of equal elements in a sequence of elements. unique() takes two forward iterators, the first of which marks the sequence's beginning and the second marks its end. The algorithm scans the sequence and removes repeated identical values. The duplicate values are moved to the sequence's end. For example, applying unique to the following sequence of integers: 1,0,0,9,2 changes their order to: 1,0,9,2,0 unique() doesn't really delete the duplicate values; it moves them to the container's end. The third element in the original container is moved one position past the final 2. unique() returns an iterator pointing to the logical end of the container. In other words, it returns an iterator pointing to the element 2, not 0. You can delete all the duplicate elements that were moved past the logical end using the iterator returned from unique(). For example: int main() { vector vi; vi.push_back(1); // insert elements into vector vi.push_back(0); vi.push_back(0); vi.push_back(9); vi.push_back(2); //move consecutive duplicates past the end; store new end vector::iterator new_end= unique(vi.begin(), vi.end()); // delete all elements past new_end vi.erase(new_end, vi.end());} } unique() is useful when you want to make sure that only a single instance of a given value exists in a range, regardless of its distribution. For example, suppose you want to write an automated dictionary containing all the words Shakespeare's texts. First, you scan all the words in his texts and store them in a vector. Next, you sort the vector using the sort() algorithm. Finally, apply the unique() algorithm to the sorted vector to move duplicate words past its logical end and erase the duplicates as shown above.



The reverse() Algorithm Another useful STL algorithm is reverse(). This algorithm reverses the order of elements in a specified sequence. reverse() takes two iterators that mark the sequence's beginning and end, respectively. Here is an example of reversing the order of a char array:

#include

#include

using namespace std;

int main()

{

char arr[4] = {'a','b','c','d'};

reverse(arr, arr+4); // arr is now "dcba"

}

Remember that the second argument of reverse() must point one element past the array's bounds. Here's an example of applying reverse() to a vector object:

int main()

{

char arr[]= {'a','b','c','d'};

vector vc (arr, arr+4); // initialize vc

reverse(vc.begin(), vc.end());

}

The replace() Algorithm Another useful STL algorithm is replace(), which is defined in the standard header and has the following prototype:

void replace (ForwardIterator start,

ForwardIterator end,

const T & old_value,

const T & new_value);

The first and the second arguments mark the sequence's beginning and end, respectively. replace() changes every occurrence of old_value in the sequence to new_value.

The following example uses replace() to replace every occurrence "NT" by "Win2000" in a vector of strings. You can apply replace() to built-in arrays, too. In the second example, replace() scans an array of integers and replaces every 1 by 5:

#include

#include

#include

using namespace std;

main()

{

vector vs;

// fill vector

vs.push_back ("Unix");

vs.push_back ("VMS");

vs.push_back ("NT");

// replace every occurrence of "NT" by "Win2000"

replace (vs.begin(), vs.end(), "NT", "Win2000");

// replace() can be applied to built-in arrays too

int n [] = {1, 0, 2, 1};

replace( n, n + 4, -1, 5); // replace every 1 by 5

}

Using the random_shuffle Algorithm STL includes the random_shuffle() algorithm. As the name suggests, this algorithm randomly shuffles the elements of a sequence. It takes two arguments, the first of which is an iterator that points to the first element of the sequence. The second argument is an iterator that points one position past the last element of the sequence. The following program instantiates a vector of characters, fills it with four consecutive elements and displays the elements. Then, the random_shuffle() algorithm is called to shuffle the elements of the vector. Finally, the elements are displayed:

#include

#include

#include

using namespace std;

int main()

{

vector vc;

vc.push_back('a'); //fill vector

vc.push_back('b');

vc.push_back('c');

vc.push_back('d');

cout<

random_shuffle(vc.begin(), vc.end()); /* shuffle elements */

cout<

}

As you can see, random_shffle() changed the order of the elements. You can use random_shuffle() with built-in arrays too:

int n[4] = {0,1,2,3};

random_shuffle(n, n+4);

Locate an Element of a Container Using the find() Algorithm You can use the generic algorithm find() to locate an element of a container. The find() algorithm takes three arguments. The first two are iterators that point at the beginning and the end of the sequence, respectively. The third argument is the sought after value. The find() algorithm returns an iterator pointing to the first element that is identical to the sought after value. If find() cannot locate the requested value, it returns an iterator pointing one element past the final element in the sequence (that is, it returns the same value as end() does). For example:

#include // definition of find()

#include

#include

using namespace std;

int main()

{

list lc;

lc.push_back('A');

lc.push_back('T');

lc.push_back('L');

list::iterator p = find(lc.begin(), lc.end(), 'A'); // find 'A'

if (p != lc.end()) // was A found?

*p = 'S'; // replace 'A' with 'S'

while (p != lc.end()) //display the modified list

cout<<*p++;

}

Using Predicate Objects to Alter Computation of a Generic Algorithm A predicate is an expression that returns either true or false. Similarly, a function object that returns a Boolean value is a predicate object. The Standard Template Library has several predicate objects that can be used to alter the computation of a generic algorithm. For example, you can alter the computation of sort() by its predicate:

#include //definitions of STL predicates

#include //definition of sort

#include

#include

using namespace std;

int main()

{

vector vi;

vi.push_back(9);

vi.push_back(5);

vi.push_back(10);

sort(vi.begin(), vi.end(), greater () ); // descending order

cout<< style=""> // output: 10 9 5

sort(vi.begin(), vi.end(), less () ); // now in ascending order

cout<< style=""> // output: 5 9 10

}

Sorting With the sort() Algorithm The generic algorithm sort() is part of the Standard Library. sort() takes two arguments of type const iterator that point to the beginning and the end of the sequence respectively:

#include

#include //definition of sort()

#include

using namespace std;

void main()

{

vector vi;

vi.push_back(7);

vi.push_back(1);

vi.push_back(19);

sort(vi.begin(), vi.end() ); // sort vi; default is ascending order

cout<< style=""> <<", "<< style=""> // output: 1, 7, 19

}

When a descending order is preferred, you can use reverse iterators:

sort(vi.rbegin(), vi.rend() ); // now sort in descending order

cout<<>

The Copy Algorithm The Standard Library provides a generic copy function, which can be used to copy a sequence of objects to a specified target. The first and the second arguments of copy() are const iterators that mark the sequence's beginning and its end, respectively. The third argument points to a container into which the sequence is copied. The following example demonstrates how to copy the elements of a list into a vector:

#include

#include

#include

using namespace std;

void main()

{

list li; vector vi;

li.push_back(1); // fill the list with elements

li.push_back(2);

vi.reserve( li.size() ); // a vector must make room for copied elements in advance

copy (li.begin(), li.end(), vi.begin() ); //copy list elements into vector, starting at vector's beginning

}

Why qsort is Still Useful in C++ C++ defines a set of generic algorithms such as sort and find. However, the corresponding C algorithms, qsort and bsearch, are still useful in C++ programs for at least three reasons:

· Legacy code. Familiarity with C algorithms is needed to maintain legacy C code.

· Efficiency. You cannot apply STL algorithms to items that are not stored in an STL container. To apply these algorithms to a built-in array, you first have to copy it into a container--an operation that incurs runtime overhead.

· Applicability to non-OO data types. STL algorithms rely on operators == and >. However, these operators are either meaningless or not defined when applied to plain structs or built-in arrays. C algorithms do not rely on these operators to work.

Using bsearch the Right Way Standard C defines the function bsearch, which performs a binary search on an array of elements. The function bsearch is very efficient, but it works only on sorted arrays. You can use the function qsort to sort a non-sorted array first, and then use bsearch to perform a binary search on the sorted array. Both functions are declared in the header file .

No comments: