c++ - 如何在跟踪原始索引的同时压缩 vector (具有重复项)？

Question

假设我有一个 vector {1,3,1,5,4,2,3,4,5,2}( vector 大小可能非常大)，

indices --> 1 2 3 4 5 6 7 8 9 10
values  --> 1 3 1 5 4 2 3 4 5 2

其关系为:

1 --> {1,3}
2 --> {6,10}
3 --> {2,7}
4 --> {5,8}
5 --> {4,9}

现在使用 set，我可以将它减少到 {1,2,3,4,5}，

std::set<int> uniqNumbersSet;
for(unsigned int i = 0; i < uniqNumbers.size(); ++i )
{
    uniqNumbersSet.insert(uniqNumbers[i]);
}
uniqNumbers.assign(uniqNumbersSet.begin(), uniqNumbersSet.end());

但是我怎样才能跟踪他们原来的关系呢？使用 STL 有什么有效的方法吗？

Answer 1

您可以使用 vector 的 map。

#include <map>
#include <vector>

std::map<int, std::vector<unsigned> > uniqNumMap;
for (unsigned i = 0; i < uniqNumbers.size(); ++i) {
    uniqNumMap[uniqNumbers[i]].push_back(i+1);
}

for (std::map<int, std::vector<unsigned> >::const_iterator i = uniqNumMap.begin(); i != uniqNumMap.end(); ++i) {
    std::cout << i->first << " --> {";
    for (std::vector<unsigned>::const_iterator j = i->second.begin(); j != i->second.end(); ++j) {
        if (j != i->second.begin()) std::cout << ",";
        std::cout << *j;
    }  
    std::cout << "}\n";
}