2012-01-27 4 views
2

Есть 2 несортированных векторы INT v1 и v2, где v1 содержит подмножество v2C++, станд :: преобразование заменить детали индексов

v1: 8 12 4 17 
v2: 6 4 14 17 9 0 5 12 8 

Есть ли способ, как заменить пункты v1 на индексы его позиций в v2?

v1: 8 7 1 3 

Это не проблема, чтобы написать такой алгоритм, использующий 2 для циклов ...

Но есть ли решение с использованием с использованием зОго :: преобразования?

ответ

5

Объединить std::transform с функцией объекта, который вызывает std::find:

#include <vector> 
#include <algorithm> 
#include <iostream> 
#include <iterator> 

struct find_functor 
{ 
    std::vector<int> &haystack; 

    find_functor(std::vector<int> &haystack) 
    : haystack(haystack) 
    {} 

    int operator()(int needle) 
    { 
    return std::find(haystack.begin(), haystack.end(), needle) - haystack.begin(); 
    } 
}; 

int main() 
{ 
    std::vector<int> v1 = {8, 12, 4, 17}; 
    std::vector<int> v2 = {6, 4, 14, 17, 9, 0, 5, 12, 8}; 

    // in c++11: 
    std::transform(v1.begin(), v1.end(), v1.begin(), [&v2](int x){ 
    return std::find(v2.begin(), v2.end(), x) - v2.begin(); 
    }); 

    // in c++03: 
    std::transform(v1.begin(), v1.end(), v1.begin(), find_functor(v2)); 

    std::cout << "v1: "; 
    std::copy(v1.begin(), v1.end(), std::ostream_iterator<int>(std::cout, " ")); 
    std::cout << std::endl; 

    return 0; 
} 

Выход:

$ g++ -std=c++0x test.cpp 
$ ./a.out 
v1: 8 7 1 3 
+0

@ Jared Hoberock: Спасибо, мог ли я попросить о душевности без лямбда-выражений? У меня нет опыта с ними ... – justik

+0

@justik: Это просто фантастический способ создания объекта функции C++ 11. Поэтому просто введите тип с этой функцией как 'operator()'. Объект, который ссылается на 'std :: Vector ' как на параметр конструктора и член класса. –

+0

@justik: Я обновил пример, чтобы предоставить решение C++ 03, которое опускает функцию лямбда. –

0

Вы можете использовать std::find() в трансформации:

std::transform(v1.begin(), v1.end(), v1.begin(), [&](int v)->int { 
    return std::find(v2.begin(), v2.end(), v) - v2.begin()); 
}); 
0

std::transform принимает одноместной -функции-ли ка-объект. Поэтому вы можете создать класс функтора, который эффективно выполняет эту операцию, создавая ее со вторым вектором и затем применяя этот функтор к первому вектору.

template <typename T> 
class IndexSeeker{ 
    private: 
     map<T, int> indexes; 
    public: 
     IndexSeeker(vector<T> source){ 
      for(int k = 0; k < t.size(); ++k){ 
       indexes[source[k]] = k; 
      } 
     } 

     int operator()(const T& locateme){ 
      if(indexes.find(T) != indexes.end()){ 
       return indexes[T]; 
      } 
      return -1; 
     } 
} 

Кэшируя весь второй список на карте, поиск индекса эффективен, вместо того, чтобы требовать линейного поиска. Для этого требуется, чтобы тип T был сортируемым (и, следовательно, отображаемым). Если T не сортируется, требуется менее эффективный подход, требующий поиска грубой силы.