lexicographical是C++ STL 泛型算法函式，用於按字典序比較兩個序列。
基本介紹
- 中文名：lexicographical
- 用法：用於按字典序比較兩個序列
- 類型：C++ STL 泛型算法函式
- 科目：計算機
介紹,MSDN,
介紹
C++ STL 泛型算法函式：用於按字典序比較兩個序列。
函式申明：
//重載1，如果[first1, last1)按字典序列小於[first2, last2)，返回true，否則返回false。
template
bool
lexicographical_compare(
InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2 );
//重載2，功能同重載1，增加了比較函式comp，即大小關係由comp函式確定。
template < class InputIterator1, class InputIterator2,
class Compare >
bool
lexicographical_compare(
InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
Compare comp );
示例代碼：
#include
#include
#include
using namespace std;
void Output(const int * a,const int & a_size,const int * b,const int & b_size)
{
cout<<"a[]=";
copy(a,a+a_size,ostream_iterator(cout," "));
cout<
cout<<"b[]=";
copy(b,b+b_size,ostream_iterator(cout," "));
cout<
}
typedef bool (* CMP)(const int &,const int &);
int Compare(const int * a,const int & a_size,const int * b,const int & b_size,CMP cmp) //按照cmp方式進行比較
{
bool ASmallerThanB,BSmallerThanA;
ASmallerThanB=lexicographical_compare(a,a+a_size,b,b+b_size,cmp); //按照cmp方式進行比較
BSmallerThanA=lexicographical_compare(b,b+b_size,a,a+a_size,cmp);
if(! ASmallerThanB && ! BSmallerThanA) //a[] 和 b[] 相等
return 0;
else if(ASmallerThanB) //a[] < b[]
return -1;
else
return 1;
}
int Compare(const int * a,const int & a_size,const int * b,const int & b_size) //默認比較方式
{
bool ASmallerThanB,BSmallerThanA;
ASmallerThanB=lexicographical_compare(a,a+a_size,b,b+b_size); //默認比較方式
BSmallerThanA=lexicographical_compare(b,b+b_size,a,a+a_size);
if(! ASmallerThanB && ! BSmallerThanA) //a[] 和 b[] 相等
return 0;
else if(ASmallerThanB) //a[] < b[]
return -1;
else
return 1;
}
bool greater(const int & a,const int & b) //自定義越大的字典序越小
{
return a>b;
}
int main()
{
int a[]={1,2,3,4,5,6};
int b[]={1,2,3,4,5,6};
Output(a,6,b,6);
cout<<"Compare(a,6,b,6)="<<
cout<<"Compare(a,6,b,6,greater)="<<
rotate(a+2,a+4,a+6);
Output(a,6,b,6);
cout<<"Compare(a,6,b,6)="<<
cout<<"Compare(a,6,b,6,greater)="<<
return 0;
}
return a>b;
}
int main()
{
int a[]={1,2,3,4,5,6};
int b[]={1,2,3,4,5,6};
Output(a,6,b,6);
cout<<"Compare(a,6,b,6)="<<
cout<<"Compare(a,6,b,6,greater)="<<
rotate(a+2,a+4,a+6);
Output(a,6,b,6);
cout<<"Compare(a,6,b,6)="<<
cout<<"Compare(a,6,b,6,greater)="<<
return 0;
}
MSDN
Compares element by element between two sequences to determine which is lesser of the two.
template bool lexicographical_compare( InputIterator1 _First1, InputIterator1 _Last1, InputIterator2 _First2, InputIterator2 _Last2 );template bool lexicographical_compare( InputIterator1 _First1, InputIterator1 _Last1, InputIterator2 _First2, InputIterator2 _Last2, BinaryPredicate _Comp );
ParametersAn input iterator addressing the position of the first element in the first range to be compared.An input iterator addressing the position one past the final element in the first range to be compared.An input iterator addressing the position of the first element in the second range to be compared.An input iterator addressing the position one past the final element in the second range to be compared.User-defined predicate function object that defines sense in which one element is less than another. A binary predicate takes two arguments and returns true when satisfied and false when not satisfied.Return Valuetrue if the first range is lexicographically less than the second range; otherwise false.
RemarksA lexicographical comparison between sequences compares them element by element until:
It finds two corresponding elements unequal, and the result of their comparison is taken as the result of the comparison between sequences.
No inequalities are found, but one sequence has more elements than the other, and the shorter sequence is considered less than the longer sequence.
No inequalities are found and the sequences have the same number of elements, and so the sequences are equal and the result of the comparison is false.
Example
// alg_lex_comp.cpp// compile with: /EHsc#include #include #include #include // Return whether second element is twice the firstbool twice ( int elem1, int elem2 ){ return 2 * elem1 < elem2;}int main( ){ using namespace std; vector v1, v2; list L1; vector ::iterator Iter1, Iter2; list ::iterator L1_Iter, L1_inIter; int i; for ( i = 0 ; i <= 5 ; i++ ) { v1.push_back( 5 * i ); } int ii; for ( ii = 0 ; ii <= 6 ; ii++ ) { L1.push_back( 5 * ii ); } int iii; for ( iii = 0 ; iii <= 5 ; iii++ ) { v2.push_back( 10 * iii ); } cout << "Vector v1 = ( " ; for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ ) cout << *Iter1 << " "; cout << ")" << endl; cout << "List L1 = ( " ; for ( L1_Iter = L1.begin( ) ; L1_Iter!= L1.end( ) ; L1_Iter++ ) cout << *L1_Iter << " "; cout << ")" << endl; cout << "Vector v2 = ( " ; for ( Iter2 = v2.begin( ) ; Iter2 != v2.end( ) ; Iter2++ ) cout << *Iter2 << " "; cout << ")" << endl; // Self lexicographical_comparison of v1 under identity bool result1; result1 = lexicographical_compare (v1.begin( ), v1.end( ), v1.begin( ), v1.end( ) ); if ( result1 ) cout << "Vector v1 is lexicographically_less than v1." << endl; else cout << "Vector v1 is not lexicographically_less than v1." << endl; // lexicographical_comparison of v1 and L2 under identity bool result2; result2 = lexicographical_compare (v1.begin( ), v1.end( ), L1.begin( ), L1.end( ) ); if ( result2 ) cout << "Vector v1 is lexicographically_less than L1." << endl; else cout << "Vector v1 is lexicographically_less than L1." << endl; bool result3; result3 = lexicographical_compare (v1.begin( ), v1.end( ), v2.begin( ), v2.end( ), twice ); if ( result3 ) cout << "Vector v1 is lexicographically_less than v2 " << "under twice." << endl; else cout << "Vector v1 is not lexicographically_less than v2 " << "under twice." << endl;}
Output
Vector v1 = ( 0 5 10 15 20 25 )List L1 = ( 0 5 10 15 20 25 30 )Vector v2 = ( 0 10 20 30 40 50 )Vector v1 is not lexicographically_less than v1.Vector v1 is lexicographically_less than L1.Vector v1 is not lexicographically_less than v2 under twice.
