C++, std::transform заменяет элементы индексами

Есть 2 несортированных вектора int v1 и v2, где v1 содержит подмножество v2

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

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

v1: 8 7 1 3

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

Но есть ли решение с использованием std::transform?


c++ indices replace vector transform
person justik    schedule 27.01.2012    source источник

Ответы (3)


arrow_upward
7
arrow_downward

Объедините 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
person Jared Hoberock    schedule 28.01.2012
comment
@ Джаред Хоберок: Спасибо, могу ли я попросить душу без лямбда-выражений? У меня нет с ними опыта... - person justik; 28.01.2012
comment
@justik: Это просто причудливый способ C++11 для создания функционального объекта. Так что просто создайте тип с этой функцией как operator(). Объект, который принимает ссылку на std::Vector<int> в качестве параметра конструктора и члена класса. - person Nicol Bolas; 28.01.2012
comment
@justik: я обновил пример, чтобы предоставить решение С++ 03, в котором отсутствует лямбда-функция. - person Jared Hoberock; 28.01.2012

arrow_upward
0
arrow_downward

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

std::transform(v1.begin(), v1.end(), v1.begin(), [&](int v)->int {
    return std::find(v2.begin(), v2.end(), v) - v2.begin());
});
person Dietmar Kühl    schedule 28.01.2012

arrow_upward
0
arrow_downward

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 не поддается сортировке, требуется менее эффективный подход, требующий поиска методом грубой силы.

person Adam Norberg    schedule 28.01.2012