Найти индексы и обратное отображение уникального вектора

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 (п журнал (п))

(я изменил индексы в 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)).