• CSci202 Computer Science II, Session 14 C++ Algorithms
• : Preparation
• : Assigned Work Due
• : Objectives
• : Input
• : : Doing it the hard way
• : : Glossary for the C++ Standard Library
• : : C.1 Search
• : : C.2 Scan, compare, and count
• : : C.3 Copy, Move and swap
• : : C.4 Change and Delete
• : : C.5 Generate and Fill
• : : C.6 Sort
• : : C.7 Search, Merge and Permute Sorted Containers
• : : C.8 Set Operations: union, intersection, complement,...
• : : C.9 Numeric algorithms
• : : C.10 Heaps
• Questions
• : Can you explain heaps?
• : Do these algorithms work with non-numeric data?
• : How do you choose the right algorithm?
• : What can the different types of iterator do?
• : When and how do we use generate?
• : Is there a way to find out all the algorithms in the library?
• : How do we find out how an <algorithm> works?
• : When should we use a heap?
• : When should we write a heap?
• : What is the difference between XXX and XXX_if?
• : What are the most important algorithms in Appendix C?
• : When we push an item onto a priority_queue is the queue automatically sorted?
• : How well can we determine the best algorithm for a situation?
• Exercises
• Specifications of Algorithms on WWW
• Further Reading
• Laboratory 7 Comparing Algorithms for Sorting
• Next
• Abbreviations

CSci202 Computer Science II, Session 14 C++ Algorithms


(previous): Introduction to the theory of algorithms [ 13.html ]

Preparation

Review [ stl.html ] and study this page and appendix C!

Try this interactive page [ stl.review.html ] out.

Assigned Work Due

Hand in a question, doubt or surprise. Include name and a page number.

Project 4 is due!

Objectives

I do not expect you to have memorized the complete set of algorithms in this appendix. I definitely will not expect you to use them correctly in quizzes and the final. However, I expect you to recognize them in code that I give you (in class, lab, quiz, and final) and either fill in a blank or two, or predict what the code should do.

Some of the algorithms are worth learning to use because they are easier to learn and use than programming them your self. The classic one of these is

 		sort( first, last );

Hint: pay attention to the algorithms that have example programs (*.cpp) on this web site. I might recycle these into quizzes and the final.

In practice you may need to look up a function in the book or on the web to find out how to use it.

Input

Doing it the hard way

Three classic O(n*n) sorts coded without using the Standard Library algorithms: [ showInsertionSort.cpp ] [ timeInsertionSort.cpp ] [ timeBubbleSort.cpp ] [ timeSelectionSort2.cpp ]

Glossary for the C++ Standard Library

1. binary_function::=A function that has two arguments f(x,y).
2. binary_predicate::=a function or function_object that returns a bool value when given two items, used for testing to see if items match, or that they are in order.
3. function::=Something that can be called like this f(x) with an argument x.
4. function_object::=any object of a class that has defined an operator() and so can be called as if it was a function. [ testFillGen2.cpp ]
5. interval::=a range.
6. iterator::=an object that indicates an item in a container,
7. iterators::=plural of iterator.
8. predicate::=a function or function_object that returns a bool value when given an item. [ testFillGen2.cpp ]
9. range::= a sequence of items in a container given by a pair of iterators indicating the beginning and the point after the last one.

   In the following 'pack' is a container of playing cards.

   C.1 Search

   
   (find): looks for a value in a range.

    		found = find( pack.begin(), pack.end(), ace_of_spades);

   
   (find_if): looks for items in a range that satisfy a predicate.

    		found = find_if(pack.begin(), pack.end(), isHeart);

   where

    	bool isHeart(Card& c) { return c.suit() == HEART ; }

   
   (find_first_of): looks for items in first range that is also in the second range or uses a binary_predicate to find first matching item.
   (find_end): looks backward for items in first range that are not also in the second range or uses a binary_predicate to find first non_matching item.
   (adjacent_find): looks for first pair in range that are equal, or match under a binary_predicate.

   
   (max): returns larger of two items, possible using a binary_predicate.
   (max_element): finds largest item in a range, may use a binary_predicate.

    		biggest = max( p.begin(), p.end(), compareRank).

   where

    	int compareRank(Card& c, Card& d) { return d.rank() - c.rank(); }

   
   (min): returns larger of two items, possible using a binary_predicate.
   (min_element): finds largest item in a range, may use a binary_predicate. [ timeSelectionSort.cpp ]

   
   (mismatch): search two parallel ranges and returns position of the first one that is unequal or doesn't satisfy a binary_predicate.

   
   (search): look in first range for an occurrence of the second range, possibly using a binary_predicate.
   (search_n): look in range for an occurrence of n items equal to a value, possibly using a binary_predicate.

   C.2 Scan, compare, and count

   
   (count): scan range and count occurrence of a value.
   (count_if): scan range and count times a predicate is true.

    		aces = count_if(pack.begin(), pack.end(), isAce);

   where

    	bool isAce(Card& c) { return c.rank() == ACE ; }

   
   (equal): test if a range equals, element another parallel range, possibly using a binary_predicate.
   (for_each): Apply a function to every item in a range.

    		for_each( pack.begin(), pack.end(), showCard);

   C.3 Copy, Move and swap

   Error on Page 594: Under the iter-swap heading the book has a function swap(it1, it2) that should be iter_swap(it1, it2). Used in [ timeQuickSort.cpp ]

   
   (copy): Copy items in range to another place indicate by its start.
   (copy_backward): Copy items in range to another place indicated by its end.

   
   (swap): swaps values of two given variables.
   (iter_swap): swaps two items in a container indicated by iterators. Used in [ timeSelectionSort.cpp ]

   
   (swap_ranges): interchanges value between two ranges.
   (reverse): places the elements in the reverse order.
   (reverse_copy): creates a backwards copy of a range.
   (rotate): given a middle point in a range, reorganizes range so that middle comes first...
   (rotate_copy): creates a rotated copy.

   
   (partition): takes a range and reorganizes the items so that a predicate is true at first and then false... A key part of QuickSort! [ timeQuickSort.cpp ]
   (stable_partition): takes a range and reorganizes the items so that a predicate is true at first and then false... but in each part the items are still in the same sequence (with some gaps).

   
   (random_shuffle): shuffles a range, you can supply your own random number generator.

   C.4 Change and Delete

   
   (replace): scan a range and replace given old values by given new value.
   (replace_if): scan a range and replace given old values by given new value IF a predicate is true.
   (replace_copy): make a copy of a range but replace given old values by given new value.
   (replace_copy_if): make a copy of a range but replace given old values by given new value IF a predicate is true. [ testFillGen2.cpp ] (old fashioned functions...) and with [ testFillGen.cpp ] newfangled function_objects.

   
   (remove): deletes items in a range that equal a given value.
   (remove_if): deletes items in a range if a predicate is true.
   (remove_copy): makes a copy of items in a range but not those with a given value.
   (remove_if): makes a copy of items in a range but not those where a predicate is true.

   
   (unique): deletes duplicated items, leaves the first. Can use a binary_predicate.
   (unique_copy): copies range but not duplicated items, leaves the first. Can use a binary_predicate.

   C.5 Generate and Fill

   
   (fill): change a range to all have the same given value. [ testFillGen.cpp ] [ testFillGen2.cpp ]

   
   (fill_n): change n items to all have the same given value.
   (generate): change items in a range to be values produced by a function_object. [ testFillGen.cpp ] [ testFillGen2.cpp ] Notice: generate uses a copy of the function object that you give to it. So if it is an object the original internal state will be the same after generating the objects in the container, and so you will get the same values the next time generate is called. But if you hand generate a function with an internal state (static) this can not be reset and so successive calls of generate will give different results!
   (generate_n): change n items to be values produced by function_object.
   (transform): takes two intervals and applies a binary operation to items to generate a new container. For example: [ transformer.cpp ] , OR scans a range and for each item uses a function to generate a new object put in a second container [ toUpper.cpp ] (notice that we have to disambiguate the toupper and tolower function names [ ../samples/c++.cctype.html ] )

   C.6 Sort

   
   (sort): reorganize a range to be in order, can use a binary_predicate.

    		string tab[]={"dog", "cat", "python"};

    		sort(tab, tab+3);

   [ 14sort.cpp ] [ timeVectorSort.cpp ]

   Also some containers have a sort member function: [ timeListSort.cpp ]

   
   (stable_sort): like sort but equivalent items are kept in the same sequence.
   (partial_sort): Sorts part of a range.
   (partial_sort_copy): makes a copy of a range but with part sorted.

   
   (nth_element): Sorts out just the nth element!

   C.7 Search, Merge and Permute Sorted Containers

   
   (binary_search): search a sorted range for a value.
   (lower_bound): finds first place in a sorted range which is not less than a given value.
   (upper_bound): finds first place in a sorted range which is not greater than a given value.
   (equal_range): finds a range that brackets a given value.

   
   (merge): Combines two sorted ranges to give a new sorted range both all their items.
   (inplace_merge): Combines two sorted halves of a range to give a sorted range both all their items. [ timeMergeSort.cpp ]

   
   (next_permutation): permutes items in a range... will generate each possible order once until it returns false.
   (prev_permutation): undoes next_permutation

   C.8 Set Operations: union, intersection, complement,...

   [ timeMultisetSort.cpp ]

   
   (includes): set theoretic test.
   (set_union ): set theoretic operation.
   (set_intersection): set theoretic operation.
   (set_difference): set theoretic operation.
   (set_symmetric_difference): set theoretic operation.

   C.9 Numeric algorithms

   
   (accumulate): adds up items in range starting with given initial value, can also do any binary operation if it is given as an function of two arguments(binary_function).Used to code the math Σ and Π symbols.
   (inner_product): the heart of linear algebra, but can be generalized to do other things by supplying two binary_function s.
   (partial_sum): scans range and replaces items by sum so far, can use general binary_function.
   (adjacent_difference): Scans range and replace items by differences

   C.10 Heaps

   The big lumps rise to the top. Seriously! A heap is an array of vector where the first item is always the biggest time. Further, the next two smallest items are in the second and third places. After the second you have the fourth and fifth, and after the third the sixth and seventh. As a rule the n'th item is larger than the 2*n'th and (2*n+1)'th items. For more take CSCI330 Data Structures.

   
   (make_heap): rearranges a range so that it becomes a heap.
   (sort_heap): takes a heap and creates a sorted container from it (by popping items).

   Combining make_heap and sort_heap gives a pretty good sort: [ timeHeapSort.cpp ]

   
   (push_heap): puts a new element into a heap and rearranges it to still be a heap.
   (pop_heap): removes the top/largest element and rearranges to leave a heap behind.

Questions

Can you explain heaps?

No! Not in CSCI202. Please take CSCI330!

Do these algorithms work with non-numeric data?

Yes: characters, strings, and objects of your own classes.

Note: for your own classes, some containers only work if you define

 		bool operator<( yourClassName * the_other );

How do you choose the right algorithm?



1. Know lots of algorithms and how they perform.
2. Know what you need: run quickly, write quickly, save space, score points, ...
3. Put the two piees of knowledge together and make an educated guess.
4. TEST your guess.



What can the different types of iterator do?

Different containers provide different iterators, and these differ in the operations defined on them

type	Operations
forward	++, ==, !=
bidirectional	++,--,==,!=
random	+, +=, -, -=, ++,--,==,!=

When and how do we use generate?

Here is are two examples of code generating a series of numbers using generate: [ testFillGen.cpp ] [ testFillGen2.cpp ]

Use generate when there is a simple way to calculate a series of items in a container.

Is there a way to find out all the algorithms in the library?

The book is pretty complete.... Also see the next question.

There are many more algorithms that covered in this book. See the further see [ Are there any good books on algorithms? in alg ]

How do we find out how an <algorithm> works?

Mostly yopu only need to know how to use it and how it performs.

You can learn how they should be coded in CSCI330.

You could look in Barjne Stroustrup's Book (Chapter 13).

To be sure what we have, you have to find the source code. On UNIX systems, like ours, you need to look in

 		/usr/include

You can use ls to "LiSt" what is in this. I think you will find the relevant #include files in

 		ls /usr/include/c++/4.1.1/

and the details in

 		ls /usr/include/c++/4.1.1/bits

However, this code is not very readable.

When should we use a heap?

In [ lab07.html ]

When should we write a heap?

After starting CSci330.

What is the difference between XXX and XXX_if?

XXX does something to every item in a range, XXX_if does the same thing to some items in a range. It has an extra argument that is a function that turns on the action: true means do it, and false means don't.

What are the most important algorithms in Appendix C?

It all depends on what you need. For quizzes and the final I don;t expect you to be able to do anything that involves a predicate or mother function object.

It would be good if you new of the existence of all the algorithms. You need to be able to use the simplest ones (no function objects or predicates).

When we push an item onto a priority_queue is the queue automatically sorted?

In effect yes. In practice, a priority queue is designed so that the minimum of work is done to reorganize the data into the right order.

How well can we determine the best algorithm for a situation?

The better you understand the situation the better choice you can make. Sometime you might as well just choose the simplest code and get that to work. Optimize it later.

Exercises

Depends on the questions!

Specifications of Algorithms on WWW

Only the draft but close to the real thing: [ lib-algorithms.html ] (also nearly unreadable without working on it).

Silicon Graphics provide a more than complete set of technical documentation [ http://www.sgi.com/tech/stl/ ] of the complete C++ Standard Library including the algorithms. They include some non-standard items and assume you've mastered the basics.

Further Reading

---

1. Scott Meyers
2. Effective STL: 50 specific ways to improve your use of the standard Template Library
3. Addison Wesley 2001 QA76.73.C153.M49 ISBN 0-201-74962-9

---

. . . . . . . . . ( end of section CSci202 Computer Science II, Session 14 C++ Algorithms) <<Contents | End>>

Laboratory 7 Comparing Algorithms for Sorting

Abbreviations