last day (15 days later) » 

1:56 PM
1
A: Compute indices of two vectors' common elements efficiently

NelxiostNew answer The new requirement is that the original vectors cannot be modified when computing the solution. The sorting-intersection solution does not work anymore since the indices are mixed up. Here is what I suggest : mapping the first vector values to the corresponding indices with an unord...

 
MrX
In general, the vectors that I deal with are not sorted. I just had to construct a toy example and used std::set for that.
 
@MrX You say in your edit that you need the indices of the unsorted vector. But your current solution sorts your vectors. So, is sorting ok or do you want the original vectors untouched ? I'm taking a wild guess here, but I doubt that another algorithm beats sorting and using set_intersection.
 
MrX
My solution (not the setup) works also for unsorted vectors. I just added a random_shuffle for the problem setup to make it more clear.
 
My bad. I edited so that you get the indices instead of the values. I deleted the part with set_intersection since you cannot use it for the problem (except maybe by creating a special output iterator). @MrX You didn't answer. Do you require the original vectors to remain unsorted ?
 
MrX
@Nelxiost: Yes, they have to remain unsorted. In fact, I am not allowed to modify the original vectors. Will add it to the question.
 
1:56 PM
@MrX Edited. I cannot test the new code at the moment, though. It might be bugged.
 
MrX
Great! Debugged and test: performs comparable to @Host's solution.
 
@MrX Glad to hear it. I added a version where the range of values is known (and relatively small) : what user2079303 was asking about. Hopefully I also corrected the code.
 
MrX
Not yet bug-free: Your second for loop is not correct. You should use iterators and not range-based foor loop. Also, the mapped type is size_t and I would avoid the variable name map since some use using namespace std and then map is a keyword because of std::map.
 
@MrX I don't see how the loop is incorrect. it contains successive values in random_vec_1, and I indexed map with the values of random_vec_2. Thus, map[it] gives the index in random_vec_2 of the value it (if it is mapped). The mapped type is indeed size_t since it is the type of indices. As to the name map... I never use using namespace std, exactly for the reason you stated. Anyway, I edited it.
 
MrX
@Nelxiost: Sorry, had the older edit in mind where you used (*it) but now it's correct. I just mentioned the map naming because in many beginner books they use std namespace for some reason.
 
2:04 PM
I see. At first I forgot that range-based for loops directly gave the value instead of the iterator.
The use of using namespace std in books is unfortunate. I guess it makes for more readable code examples in books, but it really doesn't in practice.
 
 
4 hours later…
6:21 PM
@MrX By the way, if your problem is solved, don't forget to mark an answer.
 

  last day (15 days later) »