Sprawdzania obecności zmiennej w vectorze.

Dzień dobry, chciałem się dowiedzieć czy jest jakiś inny sposób na sprawdzenie czy X jest w vectorze niż na pętli.

W bibliotece standardowej jest find, ale jeśli chodzi Ci o szybszy sposób, to nie ma, złożoność wyszukiwania liniowego jest zawsze n.

p = std::find (myints, myints+4, 30); 30 oznacza liczbe szukaną?

@KomnatoMan:

1. a może potrzebujesz innej struktury danych, np std::map?
2. Hipotetycznie, gdyby to było na wskaźnikach / referencjach to typu danych, można by myśleć o dualnym kontenerze

na pewno sa liczne biblioteki poza std:: do twojego zagadnienia

Jeśli elementy są nieuporządkowane to raczej nie ma innego wyjścia, niż przejść po elementach w O(n).

Co innego, gdyby był uporządkowany, bo wtedy mógłbyś wykorzystać wyszukiwanie binarne w O(logn).

Wydaje mi się, że znając rozkład wartości dało się nawet zejść do O(loglogn) czy jakoś tak, przynajmniej optymistycznie.

A gdybyś zamiast wektora mógł użyć zbioru wartości (zależy co z nim jeszcze robisz, poza szukaniem elementów) z czymś pokroju hash table pod spodem, to miałbyś znajdowanie elementu w O(1) ;)

@AnyKtokolwiek:
Nie znam std::map i nie mam pojęcie jak działa.
A jeśli chodzi o zadanie to (http://szkopul.edu.pl/problemset/problem/Cgw52wK7lgkABFnX_GbP-kiD/site/?key=statement)
i warto zauważyć że w pewnym momencie pojawia się cykl, ale można go użyć tylko wtedy gdy X==2,4,8,16,14,10.

Czy cykl występuje też dla cyfr 3, 5, 6, 7, 9? Jeśli tak to czy wszystkie liczby można znormalizować do cyklu? Jeśli tak to tutaj nie potrzeba tablicy a dzielenie modulo.

@lubie_programowac: takie rozwiązanie jest za wolne, dla tego zadania

Na razie takie coś wyszło, ale czy może zmienić p=find (t,t+N,X); ponieważ ten element zgłasza błąd o złym operatorze.

#include <iostream>
#include <vector>
using namespace std;
int suma(long long X)
{
    int wynik=0;
    while(X!=0);{
        wynik = wynik + X%10;
        X=X/10;
    }
    return wynik;
}
int main()
{
    ios_base::sync_with_stdio(0);
    int N,X,p;
    cin >> N >> X;
    int A=X;
    if(N==1){
        cout << X;
    }
    else{
        X=suma(X)*2;
        vector <int> t={2,4,8,16,14,10};
        p=find (t,t+N,X);
        if(p==X){
            cout << t[(N-2)%6];
            break;
        }
        else{
            for(int i =2;i<=N;i++){
                A=suma(A)*2;
            }
            cout << A;
            break;
        }
    }

    return 0;
}

Sugerowałbym użycie vector<size_t> used(18*9*2+1);
Zaznaczasz w tym wektorze elementy które już były oprócz elementu pierwszego jeżeli jest poza zakresem.
used[wartość]=numer;

A ja bym sugerował przeanalizować problem.
W tym ciągu pojawiają się cykle, na dodatek każda wartość początkowa, zawsze zbiega się do jednego z cykli, więc nie trzeba liczyć tego siłowo.
Wpisz te cykle "twardo" w kod. Potem licz kolejne elementy ciągu, aż do napotkania cyklu, a potem korzystając z cykliczności skacz do wyniku końcowego.
Tych cykli jest mało, więc można liczyć je na kartce.
Okaże się, że std::vector jest tu zbędny.

@KomnatoMan: Raczej nie, inaczej po sprawdzeniu miliona losowych liczb, (co wyklucza, imo, przypadek) widać, że średnia ilość iteracji, żeby znaleźć cykl to 7.21, maksymalna 10. Liczy to kod w Pythonie, samotłumaczący się:

def sum_digit(n):
    s = 0
    while n > 0:
        s += n % 10
        n //= 10
    return s

def cycle(n):
    x0 = n
    cnt = 0
    xn = None
    s = set()
    s.add(x0)
    while True:
        xn = 2 * sum_digit(x0)
        x0 = xn
        cnt += 1
        if xn in s:
            return xn, cnt
        else:
            s.add(xn)
    


if __name__ == '__main__':
    n = 10 ** 18
    max = 0
    acc = 0
    iters = 1000000
    for _ in range(iters):
        k = random.randint(1, n)
        m = cycle(k)[1]
        acc += m
        if m >= max:
            max = m
    print(max)  # -> 10
    print(acc / iters)  # -> 7.21

Istnieją tylko trzy cykle:

18
6,12
2,4,8,16,14,10

https://godbolt.org/z/ajrWzr