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

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

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

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

std::vector 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  
inline std::tuple,std::vector,vector>
unique_idx_inv(const std::vector &a) {
    auto size_a = size(a);
    std::vector uniques;
    std::vector idx; // vector of indices
    vector inv(size_a); // vector of inverse mapping

    for (auto i=0; i

将其与典型的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


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


1> max66..：
如果我没错,以下解决方案应为O(n log(n))

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

template  
inline std::tuple,
                  std::vector,
                  std::vector>
unique_idx_inv(const std::vector &a)
 {
   std::size_t               ind;
   std::map  m;
   std::vector            uniques;
   std::vector  idx;
   std::vector  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);
}