To Do List

From wiki
Revision as of 20:14, 15 October 2007 by SeanParent (Talk | contribs)

Jump to: navigation, search

Order Selection Networks - Rework pin, min, max, median_3, median_5, select_ith_n

Review chapter from book (4)

For each provide a comparison based, const, and non-const versions.

Go to how many elements?

Definitions: select_ith_n: return the ith element in non-descending order out of n elements.

The network is minimal in the worst case if it does the minimum number of comparisons in the worst case and minimal in the average case if it does the minimum number of comparisons on average.

The selection network is stable if the retuned element is selected out of n elements stably soreted in non-decending order (we do not do sorting).

A selection network from partially ordered inputs is a selection network where a certain partial ordering of the elements is already determined.

[We need to develop a naming convention for paritial ordering.]

Question - do we provide sorting networks?

Replace bound_if() with partition_point()

Write a proper partition() (ordering and for forward iterator), partition_point_n(), and is_partitioned.

Make cautionary note about wrapped standard algorithms.

non_strict_order_partition(range, element, strict_weak_ordering) arranges it so that elements are not greater followed by elements which are not less.

Pull count_min/max_element. Replace with two passes - max_element(), count().

Binary searches

Write a better binary_search which returns lower_bound() if exists else last.

Write an adaptor for is_in_sorted_range - set_member?

find_first_of_set() - becomes find_if with adaptor.

We should try to adapt binary search algorithms such as upper bound and lower bound to work on sets and multisets.

Finding and Counting

Extending find() - also provide find_not() and count_if_not() and count_not(). exists, none, all?

Check what other adobe/STL algorithms take unary predicates (partition_not?).

Versions of find and count need to take a binary predicate - see find_match().

And find_n(), count_n() for all versions.

Remove find_not_equal (the one working version is find_not() ).

Versions of for_each for_each_value() - rename of for_each_position() for_each_value_n() for_each_n()

Sorting Group is_sorted sorted() rename to sorted_run()

mismatch() gets grouped with equal() and search() Add mismatch_n().

Look at reduce accumulate and related functions - do we keepr reduce_balanced()?