Is there an algorithm that checks whether a container contains only distinct elements?

Viewed 100

Hello I want to find some algorithm that checks whether a container contains all distinct elements.

Here is what I've tried:

template <typename It>
bool hasAllDistinctElems(It first, It last){
    for(auto i = first; i != last; ++i)
        for(auto j = i; ++j != last; )
            if(*i == *j )
                return false;
    return true;
}


int main(){

    std::vector<int> vi{5, 7, 3, 8, 2, 7, 5};
    std::deque<int> di{1, 5, 7, 2, 3, 8, 6};
    std::cout << hasAllDistinctElems( vi.cbegin(), vi.cend() ) << '\n'; // 0
    std::cout << hasAllDistinctElems( di.cbegin(), di.cend() ) << '\n'; // 1
}

It works just fine but I've found another method:

  • copy all the elements of the first container into a container that guarantees the uniqueness of its elements like the STL associative containers like std::set, std::map.

  • Compare the sizes of the containers so if the sizes are equal it means all the elements from the first one has been copied to the set which means they are all unique otherwise they are not unique thus not all of them have been copied into the set:

    #include <unordered_set>
    #include <deque>
    #include <vector>
    #include <iostream>
    
    int main(){
    
        std::vector<int> vi{5, 7, 3, 8, 2, 7, 5};
        std::deque<int> di{1, 5, 7, 2, 3, 8, 6};
    
        std::unordered_set<int> usi(vi.cbegin(), vi.cend());
        std::unordered_set<int> usi2(di.cbegin(), di.cend());
    
        std::cout << std::boolalpha;
        std::cout << "vi's all distinct? " << (vi.size() == usi.size()) << '\n'; // false
        std::cout << "di's all distinct? " << (di.size() == usi2.size()) << '\n'; // true
    
    }
    
  • Both work fine but I'd like to know which one should I use? Is there an algorithm that does that?? or another workaround? Thank you!

0 Answers
Related