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

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

Answer 2

O(n^2)源于您在向量上使用嵌套循环来识别重复项的方法。然而，要确定元素是否已经被读取，排序向量或(imho更好)无序映射更合适。因此，在不编写代码的情况下，我建议使用形式的无序映射

unordered_map<int,int>，它既可以保存唯一值又可以保存索引。我不确定你是否还需要这些向量来获取这些信息，但你可以很容易地从地图中导出这些向量。

复杂性应降低到O(n log(n))。