找到唯一向量的索引和逆映射

Question

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

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

逆映射向量使得利用其索引可以使用唯一向量即构造原始向量

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]];});

并且索引向量仅仅是原始向量中第一次出现唯一值的向量索引.

我的基本解决方案远没有效率.它不使用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只有一个重复值]

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);
}