set_intersection

Artigo
03/14/2013

Une todos os elementos que pertencem a ambos os intervalos de origem classificadas em um único, classificados intervalo de destino, onde o critério classificação pode ser especificado por um predicado binário.

template<class InputIterator1, class InputIterator2, class OutputIterator>
   OutputIterator set_intersection(
      InputIterator1 _First1, 
      InputIterator1 _Last1,
      InputIterator2 _First2, 
      InputIterator2 _Last2, 
      OutputIterator _Result
   );
template<class InputIterator1, class InputIterator2, class OutputIterator, class BinaryPredicate>
   OutputIterator set_intersection(
      InputIterator1 _First1, 
      InputIterator1 _Last1,
      InputIterator2 _First2, 
      InputIterator2 _Last2, 
      OutputIterator _Result,
      BinaryPredicate _Comp
   );

Parâmetros

_First1
Um iterador de entrada que trata a posição do primeiro elemento na primeira classificado dois dos intervalos de fonte a ser unidos e classificado em um único intervalo que representa a interseção dos dois intervalos de origem.
_Last1
Um iterador de entrada que trata a posição um passado o último elemento em primeira classificado dois dos intervalos de fonte a ser unidos e classificado em um único intervalo que representa a interseção dos dois intervalos de origem.
_First2
Um iterador de entrada que trata a posição do primeiro elemento em um segundo de dois intervalos de origem classificados consecutivos ser unido e classificado em um único intervalo que representa a interseção dos dois intervalos de origem.
_Last2
Um iterador de entrada que trata a posição um passado o último elemento em um segundo de dois intervalos de origem classificados consecutivos ser unido e classificado em um único intervalo que representa a interseção dos dois intervalos de origem.
resultado de**_**
Um iterador de saída que trata a posição do primeiro elemento no intervalo de destino onde os dois intervalos de origem devem ser unida em um único intervalo classificado que representa a interseção dos dois intervalos de origem.
_Comp
Objeto definido pelo usuário da função de predicado em que define o sentido que o elemento é maior do que outros.O predicado binário leva dois argumentos e deve retornar true quando o primeiro elemento é menor que o segundo elemento e false caso contrário.

Valor de retorno

Um iterador de saída que trata a posição um passado o último elemento no intervalo classificado de destino que representa a interseção dos dois intervalos de origem.

Comentários

Os intervalos de origem classificados referenciados deve ser válido; todos os ponteiros devem ser dereferenceable e em cada seqüência a posição da última deve ser alcançável da primeira incrementação.

O intervalo de destino não deve sobrepor nenhum dos intervalos de origem e deve ser grande o suficiente para conter o intervalo de destino.

Os intervalos de origem classificados eles devem ser organizados como uma condição anterior para o aplicativo do algoritmo de mesclagem de acordo com a mesma ordem que é que ser usada pelo algoritmo para classificar os intervalos combinados.

A operação é estável porque a ordem relativo de elementos em cada intervalo é mantido no intervalo de destino.Os intervalos de origem não são modificados pelo algoritmo.

Tipos de valor de iteradores de entrada precisam ser " menor que " comparável ordenada seja, para que, dado dois elementos, pode determinar se qualquer um que são equivalentes (no sentido que nenhum for menor do que o outro) ou um que é menor que o outro.Isso resulta em ordenação entre elementos nonequivalent.Quando houver elementos equivalentes em ambos os intervalos de origem, os elementos no primeiro intervalo precedem os elementos do intervalo de segunda fonte no intervalo de destino.Se os intervalos de origem contenha duplicatas de um elemento, então o intervalo de destino conterá o número máximo de esses elementos que ocorrem em ambos os intervalos de origem.

A complexidade do algoritmo é um-a-um com no máximo 2 * ( (_Last1 – _First1) + (_Last2 – _First2) ) – 1 comparações para intervalos de origem não vazio.

set_intersection tem dois formulários relacionados:

Para obter informações sobre como essas funções se comportam, consulte Iteradores selecionados.

Exemplo

// alg_set_intersection.cpp
// compile with: /EHsc
#include <vector>
#include <algorithm>
#include <functional>   // For greater<int>( )
#include <iostream>

// Return whether modulus of elem1 is less than modulus of elem2
bool mod_lesser (int elem1, int elem2 ) {
   if ( elem1 < 0 ) 
      elem1 = - elem1;
   if ( elem2 < 0 ) 
      elem2 = - elem2;
   return elem1 < elem2;
}

int main() {
   using namespace std;
   vector <int> v1a, v1b, v1 ( 12 );
   vector <int>::iterator Iter1a,  Iter1b, Iter1, Result1;

   // Constructing vectors v1a & v1b with default less than ordering
   int i;
   for ( i = -1 ; i <= 3 ; i++ )
      v1a.push_back( i );

   int ii;
   for ( ii =-3 ; ii <= 1 ; ii++ )
      v1b.push_back( ii );

   cout << "Original vector v1a with range sorted by the\n "
        <<  "binary predicate less than is  v1a = ( " ;
   for ( Iter1a = v1a.begin( ) ; Iter1a != v1a.end( ) ; Iter1a++ )
      cout << *Iter1a << " ";
   cout << ")." << endl;

   cout << "Original vector v1b with range sorted by the\n "
        <<  "binary predicate less than is  v1b = ( " ;
   for ( Iter1b = v1b.begin ( ) ; Iter1b != v1b.end ( ) ; Iter1b++ )
      cout << *Iter1b << " ";
   cout << ")." << endl;
   
   // Constructing vectors v2a & v2b with ranges sorted by greater
   vector <int> v2a ( v1a ) , v2b ( v1b ) , v2 ( v1 );
   vector <int>::iterator Iter2a, Iter2b, Iter2, Result2;
   sort ( v2a.begin ( ) , v2a.end ( ) , greater<int> ( ) );
   sort ( v2b.begin ( ) , v2b.end ( ) , greater<int> ( ) );

   cout << "Original vector v2a with range sorted by the\n "
        << "binary predicate greater is   v2a =  ( " ;
   for ( Iter2a = v2a.begin ( ) ; Iter2a != v2a.end ( ) ; Iter2a++ )
      cout << *Iter2a << " ";
   cout << ")." << endl;

   cout << "Original vector v2b with range sorted by the\n "
        << "binary predicate greater is   v2b =  ( " ;
   for ( Iter2b = v2b.begin ( ) ; Iter2b != v2b.end ( ) ; Iter2b++ )
      cout << *Iter2b << " ";
   cout << ")." << endl;

   // Constructing vectors v3a & v3b with ranges sorted by mod_lesser
   vector <int> v3a ( v1a ), v3b ( v1b ) , v3 ( v1 );
   vector <int>::iterator Iter3a,  Iter3b, Iter3, Result3;
   sort ( v3a.begin ( ) , v3a.end ( ) , mod_lesser );
   sort ( v3b.begin ( ) , v3b.end ( ) , mod_lesser );

   cout << "Original vector v3a with range sorted by the\n "
        <<  "binary predicate mod_lesser is   v3a =  ( " ;
   for ( Iter3a = v3a.begin ( ) ; Iter3a != v3a.end ( ) ; Iter3a++ )
      cout << *Iter3a << " ";
   cout << ")." << endl;

   cout << "Original vector v3b with range sorted by the\n "
           <<  "binary predicate mod_lesser is   v3b =  ( " ;
   for ( Iter3b = v3b.begin ( ) ; Iter3b != v3b.end ( ) ; Iter3b++ )
      cout << *Iter3b << " ";
   cout << ")." << endl;

   // To combine into an intersection in asscending order with the
   // default binary predicate less <int> ( )
   Result1 = set_intersection ( v1a.begin ( ) , v1a.end ( ) ,
      v1b.begin ( ) , v1b.end ( ) , v1.begin ( ) );
   cout << "Intersection of source ranges with default order,"
        << "\n vector v1mod =  ( " ;
   for ( Iter1 = v1.begin( ) ; Iter1 != Result1 ; ++Iter1 )
      cout << *Iter1 << " ";
   cout << ")." << endl;

   // To combine into an intersection in descending order, specify
   // binary predicate greater<int>( )
   Result2 = set_intersection ( v2a.begin ( ) , v2a.end ( ) ,
      v2b.begin ( ) , v2b.end ( ) ,v2.begin ( ) , greater <int> ( ) );
   cout << "Intersection of source ranges with binary predicate"
        << " greater specified,\n vector v2mod  = ( " ;
   for ( Iter2 = v2.begin( ) ; Iter2 != Result2 ; ++Iter2 )
      cout << *Iter2 << " ";
   cout << ")." << endl;

   // To combine into an intersection applying a user-defined
   // binary predicate mod_lesser
   Result3 = set_intersection ( v3a.begin ( ) , v3a.end ( ) ,
      v3b.begin ( ) , v3b.end ( ) , v3.begin ( ) , mod_lesser );
   cout << "Intersection of source ranges with binary predicate "
        << "mod_lesser specified,\n vector v3mod  = ( " ; ;
   for ( Iter3 = v3.begin( ) ; Iter3 != Result3 ; ++Iter3 )
      cout << *Iter3 << " ";
   cout << ")." << endl;
}

Saída

Original vector v1a with range sorted by the
 binary predicate less than is  v1a = ( -1 0 1 2 3 ).
Original vector v1b with range sorted by the
 binary predicate less than is  v1b = ( -3 -2 -1 0 1 ).
Original vector v2a with range sorted by the
 binary predicate greater is   v2a =  ( 3 2 1 0 -1 ).
Original vector v2b with range sorted by the
 binary predicate greater is   v2b =  ( 1 0 -1 -2 -3 ).
Original vector v3a with range sorted by the
 binary predicate mod_lesser is   v3a =  ( 0 -1 1 2 3 ).
Original vector v3b with range sorted by the
 binary predicate mod_lesser is   v3b =  ( 0 -1 1 -2 -3 ).
Intersection of source ranges with default order,
 vector v1mod =  ( -1 0 1 ).
Intersection of source ranges with binary predicate greater specified,
 vector v2mod  = ( 1 0 -1 ).
Intersection of source ranges with binary predicate mod_lesser specified,
 vector v3mod  = ( 0 -1 1 2 3 ).

Requisitos

Cabeçalho: <algorithm>

namespace: STD

Consulte também

Referência

Standard Template Library

Partilhar via