From: Ian Knowles (iknowles_at_[hidden])
Date: 2000-10-26 05:17:09
I have recently developed a "diff" template class which determines
(within customisable limits) the minimum number of differences between
two containers of the same type of items (currently only vectors but
could easily be re-worked for any container that supports random
The minimum requirement of the contained item type is to support "less
than" and "equal to" comparision operators.
The algorithm works in a number of stages, firstly sorting the two
containers of items to find all "matches", then creating a table of
"all matches" which is sorted so that a "best match path" can be
determined (i.e. this will produce the least number of differences).
A few parameters and virtual functions provide mechanisms to limit the
number of matches needing to be considered (as this can greatly affect
the total number of comparisons required) and the "match table" can
also be scanned after determing the best path in order to determine
item "movements" for those matches that were not included in the best
The sample program is a "command line" utility which outputs all item
matches and diffs (similar to the file output of WinDiff) and has been
compiled and tested using BCB 4.0 (patch 2) on Win32 and gcc 188.8.131.52
under Linux (Red Hat 6.0).
If anyone would like to get a hold of the source for a play please
email me either at iknowles_at_[hidden] or ian_at_who.net.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk