CODEWITHSUNDEEP
c++
Shahgee
Shahgee

Reputation: 3405

Getting index of unique elements in a vector

Is there any STL/Boost function in C++ that allows me to find the indices of all unique elements in a vector?

I have seen many solutons to find unique elements, but I need their index.

  vector<int> v = { 1,1,1, 2,2,2,2, 3, 3, ,4,5,5,5,5,5,5 };// already sorted

Either I need first index of unique elemnt

vector<int> unique_index={0,3,7,9,10};

or I need last index of unique elements

vector<int> unique_index={2,6,8,9,15};

Upvotes: 0

Views: 1389

Answers (3)

alireza
alireza

Reputation: 88

you can change this code and using int instead of a string.

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <iterator>
#include <algorithm>


std::map<std::string, int> get_unique_indices(const std::vector<std::string>& products) {
    std::vector<std::string> tempProducts(products);
    std::map<std::string, int> result;
    std::sort(std::begin(tempProducts), std::end(tempProducts));
    for (auto it1 = std::begin(tempProducts), it2 = it1; it1 != std::end(tempProducts); it1 = it2) {
        int duplication = 0;
        for (; it2 != std::end(tempProducts) && (*it2 == *it1); ++it2) {
            duplication++;
        }
        if (duplication == 1) {
            result.insert({ *it1, std::find(std::begin(products), std::end(products), *it1) - std::begin(products) });
        }
    }
    return result;
}


int main()
{
    using namespace std;
    vector<string> products = { "apple", "orange", "lemon", "apple", "kivi", "orange", "kivi", "melon"};
    auto result = get_unique_indices(products);
    for (const auto& [key, value] : result) {
        std::cout << key << " " << value << std::endl;
    }
    return 0;
}

At first, I create another vector to save the original data. (Cause the position of the item will change in the sort method).

then I use two iterators to find duplicate items and count them. the result will be saved in a map instance. this code must compile with c++17 onwards.

Upvotes: 0

Ranoiaetep
Ranoiaetep

Reputation: 6637

Similar to David's answer of using std::set, you could also use std::map with its member function try_emplace(key, value):

#include <iostream>
#include <vector>
#include <map>

int main (void) {
    
    std::vector<int> v = { 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 4, 5, 5, 5, 5, 5, 5 };
    std::map<int, int> m;
    
    for (size_t i = 0; i < v.size(); i++)
    {
        // `i` is only entered if the `m[v[i]]` isn't filled yet.
        m.try_emplace(v[i], i);
    }

    for (auto [valueFromV, indexFromV] : m) 
    {
        std::cout << indexFromV << '\n';
    }
}

Upvotes: 1

David C. Rankin
David C. Rankin

Reputation: 84521

A simple way (aside from just keeping track of what the last element was) is to use a std::set to test if the current element is unique in the elements of the vector -- seen so far, and populate your unique indexes as you go. This provides a single pass through to collect the indexes where the first unique element is seen, e.g.

#include <iostream>
#include <vector>
#include <set>

int main (void) {
    
    std::vector<int> v = { 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 4, 5, 5, 5, 5, 5, 5 },
                uniqueidx{};
    std::set<int> s{};
    
    for (size_t i = 0; i < v.size(); i++)
        if (s.insert(v[i]).second)
            uniqueidx.push_back(i);
    
    for (const auto i : uniqueidx) 
        std::cout << i << '\n';
}

Example Use/Output

$ ./bin/set_index_of_unique_in_vector
0
3
7
10
11

(note: the last two values are 10 and 11, not 9 and 10 -- you are missing a value in your vector initialization, e.g. 3, ,4)

If you just wanted a simple-old loop to do the same thing, you could use:

#include <iostream>
#include <vector>

int main (void) {
    
    std::vector<int> v = { 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 4, 5, 5, 5, 5, 5, 5 },
                uniqueidx{};
    
    for (size_t i = 0; i < v.size(); i++)
        if (!i || v[i-1] != v[i])
            uniqueidx.push_back(i);
    
    for (const auto i : uniqueidx) 
        std::cout << i << '\n';
}

(same output)

The benefit of the approach with std::set is you leave the determination of uniqueness up to std::set, with the simple loop -- it's up to you....

Look things over and let me know if you have questions.

Upvotes: 5

Related Questions