C++, std::transform replace items by indices
Question
There are 2 unsorted vectors of int v1 and v2, where v1 contains a subset of v2
v1: 8 12 4 17
v2: 6 4 14 17 9 0 5 12 8
Is there any way, how to replace items of v1 by indices of its positions in v2?
v1: 8 7 1 3
It is no problem to write such an algorithm using 2 for cycles...
But is there any solution using using std::transform?
La solution
Combine std::transform
with a function object which calls 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;
}
The output:
$ g++ -std=c++0x test.cpp
$ ./a.out
v1: 8 7 1 3
Autres conseils
You could use std::find()
in the transformation:
std::transform(v1.begin(), v1.end(), v1.begin(), [&](int v)->int {
return std::find(v2.begin(), v2.end(), v) - v2.begin());
});
std::transform
takes a unary-function-like-object. You can therefore create a functor class that performs this operation efficiently, constructing it with the second vector, and then apply that functor to the first vector.
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;
}
}
By cacheing the entire second list into a map, finding the index is efficient, instead of requiring a linear search. This requires type T to be sortable (and thus mappable). If T is not sortable, a less efficient approach requiring a brute force search is required.