c++searchvectorlowest-common-ancestor

What is the fastest way to find the positions of the first common entry in two vectors in c++?

I have two vectors u = {32, 25, 13, 42, 55, 33} and v = {18, 72, 53, 39, 13, 12, 28} for which I would like to determine the position of their first common entry, 13. For these example vectors, these positions are 3 and 5. What is the fastest way to find these positions? I have to do this operation many-many times.

Solution

  • Assuming you don't have duplicate, you might use the following:

    std::pair<std::size_t, std::size_t>
common_entry_indexes(const std::vector<int>& u, const std::vector<int>& v)
{
    const std::size_t min_size = std::min(u.size(), v.size());
    std::map<int, std::size_t> s; // might be `std::unordered_map`

    for (std::size_t i = 0; i != min_size; ++i)
    {
         if (auto [it, inserted] = s.insert({u[i], i}); !inserted) { return {i, it->second}; }
         if (auto [it, inserted] = s.insert({v[i], i}); !inserted) { return {it->second, i}; }
    }
    for (std::size_t i = min_size; i != u.size(); ++i)
    {
         if (auto [it, inserted] = s.insert({u[i], i}); !inserted) { return {i, it->second}; }
    }
    for (std::size_t i = min_size; i != v.size(); ++i)
    {
         if (auto [it, inserted] = s.insert({v[i], i}); !inserted) { return {it->second, i}; }
    }
    return {-1, -1}; // Not found
}

    Demo