Przeszukiwanie tablicy pair

pytanie zadane 20 stycznia 2016 w C i C++ przez Noak Mądrala (5,900 p.)

Witam stworzyłem tablicę typu pair która przechowuje mi współrzędne punktu.

pair<long long ,long long>punkt[100010];

Chciałbym teraz sprawdzić czy już dany punkt znajduje się w tablicy.

Niestety ten sposób jest za wolny.

for(int j=0;j<i;j++)
    	{
    		
    		if(x==punkt[j].first)
			
    		{
    			if(y==punkt[j].second)
    			
				{
				jest=1;
    			break;
				}
			}
		}

Próbowałem przeszukać tablicę za pomocą funkcji find lecz wyskakiwał mi błąd kompilacji.

   pair<long long ,long long>heh;
    heh=make_pair(x,y);
  auto  *it= find( punkt, punkt + 8,heh) ;

Czy jest w ogóle możliwe przeszukanie tablicy pair za pomocą funkcji find ?? Jeśli tak to w jaki sposób. A jeśli nie to czy da radę przeszukać mapę za pomocą funkcji find ??

1 odpowiedź

odpowiedź 21 stycznia 2016 przez adrian17 Mentor (354,880 p.)
wybrane 21 stycznia 2016 przez Noak

Najlepsza

Próbowałem przeszukać tablicę za pomocą funkcji find lecz wyskakiwał mi błąd kompilacji.

Jaki konkretnie? Bo nie ma tam niczego złego (choć brzydkie jest).

Niestety ten sposób jest za wolny.

std::find nie będzie magicznie szybsze od takiej pętli.

Ważne pytania:

- czy kompilujesz z optymalizacjami?

- czy kompilujesz w trybie 64-bitowym? long long ma 64 bity i może być wolne w trybie 32-bitowym.

- jeśli dużo szukasz, może przydać się inna struktura, na przykład std::(unordered_)set.

komentarz 21 stycznia 2016 przez Noak Mądrala (5,900 p.)

nie wiem do końca o co chodzi z optymalizacją kompilacji :) Aczkolwiek funkcja find jest zawarta w nowszych wersjach c++ natomiast ja kompilowałem w wersji c++ 4.3.2 i w tym tkwił kłopot.

tryb 64-bitowy

komentarz 21 stycznia 2016 przez adrian17 Mentor (354,880 p.)

Aczkolwiek funkcja find jest zawarta w nowszych wersjach c++

std::find jest z oryginalnego standardu z 1998, nie wmówisz mi że GCC z 2008 go nie ma (i w dodatku widzę go w źródłach z roku 2000).

nie wiem do końca o co chodzi z optymalizacją kompilacji

To po co wspominasz że "Niestety ten sposób jest za wolny." i że próbujesz użyć std::find?

komentarz 21 stycznia 2016 przez Noak Mądrala (5,900 p.)

Te przeszukiwanie potrzebne mi było do zadanie z spoja. Dostałem na nim tle dlatego napisałem że sposób jest z wolny. Próbowałem metody std::find gdyż kolega użył jej do map i wszystko działało.

Co do "nowszych wersji" to nic nie chcę nikomu wmawiać :) Po prostu tak myślałem patrząc na różne wersje kompilacji. Dziękuję za wyprowadzenie z błędu :)

komentarz 22 stycznia 2016 przez adrian17 Mentor (354,880 p.)

cóż, std::find robiłoby dokładnie to samo co Twoje ręczne przeszukanie. Pewnie musisz przemyśleć cały algorytm lub struktury danych, jak zazwyczaj trzeba na spoju.