namespace hito {
template < typename BidirectionalIterator >
void insertion_sort( BidirectionalIterator first, BidirectionalIterator last )
{
BidirectionalIterator pos = first ;
for ( ++pos ; pos != last ; ++pos )
{
typename std::iterator_traits<BidirectionalIterator>::value_type key(*pos) ;
BidirectionalIterator iter = pos, sorted_iter = pos ;
for (--iter ; iter != first && key < *iter ; --iter, --sorted_iter)
{
*sorted_iter = *iter ;
}
if ( key < *iter ) // check first element
{
*sorted_iter = *iter ;
--sorted_iter ;
}
*sorted_iter = key ;
}
}
template < typename BidirectionalIterator, typename BinaryPredicate >
void insertion_sort( BidirectionalIterator first, BidirectionalIterator last, BinaryPredicate op )
{
BidirectionalIterator pos = first ;
for ( ++pos ; pos != last ; ++pos )
{
typename std::iterator_traits<BidirectionalIterator>::value_type key(*pos) ;
BidirectionalIterator iter = pos, sorted_iter = pos ;
for (--iter ; iter != first && op(key, *iter) ; --iter, --sorted_iter)
{
*sorted_iter = *iter ;
}
if ( op(key, *iter) ) // check first element
{
*sorted_iter = *iter ;
--sorted_iter ;
}
*sorted_iter = key ;
}
}
} // namespace hito
しかし、これはちょっと汚い。reverse_iteratorを使ってみると、こうなる。
namespace hito {
template < typename BidirectionalIterator >
void insertion_sort( BidirectionalIterator first, BidirectionalIterator last )
{
BidirectionalIterator pos = first ;
std::reverse_iterator<BidirectionalIterator> const rend(first) ;
for ( ++pos ; pos != last ; ++pos )
{
typename std::iterator_traits<BidirectionalIterator>::value_type key(*pos) ;
std::reverse_iterator<BidirectionalIterator> riter(pos), rsorted_iter(pos) ;
for ( --rsorted_iter ; riter != rend && key < *riter ; ++riter, ++rsorted_iter)
{
*rsorted_iter = *riter ;
}
*rsorted_iter = key ;
}
}
template < typename BidirectionalIterator, typename BinaryPredicate >
void insertion_sort( BidirectionalIterator first, BidirectionalIterator last, BinaryPredicate op )
{
BidirectionalIterator pos = first ;
std::reverse_iterator<BidirectionalIterator> const rend(first) ;
for ( ++pos ; pos != last ; ++pos )
{
typename std::iterator_traits<BidirectionalIterator>::value_type key(*pos) ;
std::reverse_iterator<BidirectionalIterator> riter(pos), rsorted_iter(pos) ;
for ( --rsorted_iter ; riter != rend && op(key, *riter) ; ++riter, ++rsorted_iter)
{
*rsorted_iter = *riter ;
}
*rsorted_iter = key ;
}
}
} // namespace hito
No comments:
Post a Comment
You can use some HTML elements, such as <b>, <i>, <a>, also, some characters need to be entity referenced such as <, > and & Your comment may need to be confirmed by blog author. Your comment will be published under GFDL 1.3 or later license with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.