Sprawdzenie czy liczba nie wystąpiła

Witam
Jak można zaimplementować taką funkcję, która by sprawdzała czy podana liczba już nie wystąpiła? Mi nic innego do głowy nie przychodzi poza tym co niżej, czyli rozwiązaniem pamięciożernym, które z czasem może być no i z czasem to szukanie może być czasochłonne jeżeli byśmy użyli seta zamiast unordered_seta. Kolega miał takie pytanie na rozmowie kwalifikacyjnej o pracę. Podejrzewam, że jest jaki myk/sztuczka ale pojęcia nie mam jaka. Chociaż nie mogę sobie nawet wyobrazić jaka to może być ta sztuczka, przecież musisz zapamiętać wszystkie liczby, więc musi to być rozwiązanie pamięciożerne. Co to długiego szukania, wstawiania to tutaj mamy złożoność czasową wydaje mi się O(1) (jeżeli tylko max load factor jest ustawiony na 1 i rehash nie występuje). Jakby był set to by było O(log(n)). Tak średnio jestem tego pewny, musze jeszcze o tym poczytać.

#include <stdio.h>
#include <iostream>
#include <unordered_set>

using namespace std;

bool sprawdz(const unsigned& x)
{
    static unordered_set<unsigned> checkTable;
    
    if(checkTable.find(x) != checkTable.end())
        return true;
        
    checkTable.insert(x);
}

int main()
{
    cout << sprawdz(6) << endl;
    cout << sprawdz(45) << endl;
    cout << sprawdz(1) << endl;
    cout << sprawdz(6) << endl;
            
    return 0;
}

Praktycznie tak samo, tylko static tak jak Chcesz nie działa:

#include <stdio.h>
#include <iostream>
#include <unordered_set>
 
using namespace std;
 
bool check(const unsigned x,  unordered_set<unsigned> & s)
{
 
    if (s.find(x) != s.end()){
        return true;
    }
    else{
        s.insert(x);
        return false;
    }
}
 
int main() {
    unordered_set<unsigned> table;
    cout << check(0, table) << endl; // -> 0
    cout << check(0, table) << endl; // -> 1
    cout << check(3, table) << endl; // -> 0
    cout << check(3, table) << endl; // -> 1
    cout << check(7, table) << endl; // -> 0
    cout << check(0, table) << endl; // -> 1
    return 0;
}

Działa, jak powinno, o co chodzi ze złożonością, czasowa jest O(1), jak to hash; pamięciowo O(n) - zapamiętujemy podane liczby, żeby je sprawdzać.

@lion137: wg mnie Twoje podejście jest nieprawidłowe. Funkcja sprawdz powinna zajmować się tylko sprawdzeniem czy zbiór nie zawiera elementu, a tutaj mamy efekt uboczny w postaci modyfikacji tegoż, jeśli element w nim nie występuje. IMHO jest to klasyczne łamanie SRP i wpuszczenie użytkownika takiej funkcji w pułapkę.

PS: Po co przesyłać x referencją? ;)

offtopic:
nazwa funkcji po polsku na rozmowie o pracę?
To oznacza, że kandydat ma problemy z angielskim!
Czyli będą problemy z pisaniem i czytaniem dokumentacji oraz kodu.
W tej sytuacji trzeba podzielić pensję przez dwa (szczególnie, że nazwa polska też jest beznadziejna) - to nie jest moja opinia tylko cytat z konferencji kogoś kto zajmuje się rekrutacją

użycie zmiennej statycznej w funkcji w tym przypadku dla mnie to programistyczne WTF.

grzesiek51114 napisał(a):

@lion137: wg mnie Twoje podejście jest nieprawidłowe. Funkcja sprawdz powinna zajmować się tylko sprawdzeniem czy zbiór nie zawiera elementu, a tutaj mamy efekt uboczny w postaci modyfikacji tegoż, jeśli element w nim nie występuje. IMHO jest to klasyczne łamanie SRP i wpuszczenie użytkownika takiej funkcji w pułapkę.

PS: Po co przesyłać x referencją? ;)

Rzeczywiście (to x referencją), ale tak miał, zrobiłem copy paste:)
Co do meritum, z tego co napisał (ciężkim, ale jednak polskim:)) tutaj: "która by sprawdzała czy podana liczba już nie wystąpiła?"; oraz z konstrukcji programu: ciąg zapytań, gdzie chcemy wiedzieć czy podana liczba wystąpiła właśnie w tym ciągu, wychodzi, że działanie ma być takie jak napisałem. Domyślam sie, że chodziło o to, czy ktoś umie użyć hash table( O(1)), a nie napisze tego przy użyciu listy (O(n^2)).
I jeszcze, tylko nazwa funkcji jest po polsku, reszta po angielsku, ha, ha, poprawiłem wpis:)

jak ja bym to zrobił podczas rozmowy o pracę:
https://wandbox.org/permlink/JOyHE6X18dEVUaw2

#include <iostream>
#include <algorithm>
#include <iterator>
#include <unordered_set>

template<class InputIter, class OutputIter>
void copyWithoutDuplicates_n(InputIter begin, size_t n, OutputIter result)
{
    using value_type = typename std::iterator_traits<InputIter>::value_type;
    std::unordered_set<value_type> itemsUsed;
    itemsUsed.reserve(n);
    
    while (n != 0) {
        --n;
        if (itemsUsed.count(*begin) == 0) {
            itemsUsed.insert(*begin);
            *result = *begin;
            ++result;
        }
        ++begin;
    }
}

int main() 
{
    size_t n;
    std::cin >> n;
    
    copyWithoutDuplicates_n(std::istream_iterator<int>(std::cin), n, 
                            std::ostream_iterator<int>(std::cout, "\n"));
    
    return 0;
}