c++ - 查找唯一 vector 的索引和逆映射

Question

我有一个 std::vector<int>具有重复值。我可以使用 std::unique() 找到唯一值和 std::vector::erase() ，但是如何通过逆映射 vector 有效地找到索引 vector 并在给定唯一值 vector 的情况下构造原始 vector 。请允许我用一个例子来说明这一点:

std::vector<int> vec  = {3, 2, 3, 3, 6, 5, 5, 6, 2, 6};
std::vector<int> uvec = {3, 2, 6, 5}; // vector of unique values
std::vector<int> idx_vec = {0, 1, 4, 5}; // vector of indices
std::vector<int> inv_vec = {0, 1, 0, 0, 2, 3, 3, 2, 1, 2}; // inverse mapping

逆映射 vector 是这样的，它的索引可以使用唯一 vector 构造原始 vector ，即

std::vector<int> orig_vec(ivec.size()); // construct the original vector
std::for_each(ivec.begin(), ivec.end(), 
    [&uvec,&inv_vec,&orig_vec](int idx) {orig_vec[idx] = uvec[inv_vec[idx]];});

索引 vector 只是原始 vector 中第一次出现的唯一值的 vector 索引。

我的基本解决方案效率不高。它不使用 STL 算法并且是 O(n^2)在最坏的情况下。

template <typename T> 
inline std::tuple<std::vector<T>,std::vector<int>,vector<int>>
unique_idx_inv(const std::vector<T> &a) {
    auto size_a = size(a);
    std::vector<T> uniques;
    std::vector<int> idx; // vector of indices
    vector<int> inv(size_a); // vector of inverse mapping

    for (auto i=0; i<size_a; ++i) {
        auto counter = 0;
        for (auto j=0; j<uniques.size(); ++j) {
            if (uniques[j]==a[i]) {
                counter +=1;
                break;
            }
        }
        if (counter==0) {
            uniques.push_back(a[i]);
            idx.push_back(i);
        }
    }

    for (auto i=0; i<size_a; ++i) {
        for (auto j=0; j<uniques.size(); ++j) {
            if (uniques[j]==a[i]) {
                inv[i] = j;
                break;
            }
        }
    }

    return std::make_tuple(uniques,idx,inv);
}

将其与典型的 std::sort+std::erase+std::unique 进行比较方法(顺便说一下，它只计算唯一值而不计算索引或倒数)，我在我的笔记本电脑上用 g++ -O3 得到以下时间[对于 size=10000 的 vector 只有一个重复值]

Find uniques+indices+inverse:                       145ms
Find only uniques using STL's sort+erase+unique     0.48ms

当然这两种方法并不完全相同，因为后者对索引进行排序，但我仍然相信我上面发布的解决方案可以进行相当大的优化。有什么想法我怎么能做到这一点？

Answer 1

如果我没记错的话，下面的解应该是O(n log(n))

(我已经更改了 std::size_t 值中的索引)

template <typename T> 
inline std::tuple<std::vector<T>,
                  std::vector<std::size_t>,
                  std::vector<std::size_t>>
unique_idx_inv(const std::vector<T> &a)
 {
   std::size_t               ind;
   std::map<T, std::size_t>  m;
   std::vector<T>            uniques;
   std::vector<std::size_t>  idx;
   std::vector<std::size_t>  inv;

   inv.reserve(a.size());

   ind = 0U;

   for ( std::size_t i = 0U ; i < a.size() ; ++i )
    {
      auto e = m.insert(std::make_pair(a[i], ind));

      if ( e.second )
       {
         uniques.push_back(a[i]);
         idx.push_back(i);
         ++ind;
       }

      inv.push_back(e.first->second);
    }

    return std::make_tuple(uniques,idx,inv);
}