Przeszukiwanie listy

Question

Cześć wszystkim!

Chcę napisać program, który zbierze dla mnie bliżej nieokreśloną ilość liczb spełniającą pewne warunki. Pomyślałem, ze użycie listy będzie dobrym pomysłem, tylko czy jest jakiś sposób na odszukanie  n-tego elementu listy nie znając jego wartości?

Answer 1

Witam,

wydaje mi się że lepszym kontenerem od listy jest vector. W vector możesz odwołać się do zmiennej za pomocą operatoru [] lub metodą at().

np.

vector<int> tablica(2);
tablica.push_back(1);
tablica.push_back(2);
cout << tablica[0] << " " << tablica.at(1) << endl; // wyświetli dwa razy 1

Tutaj na szybko stworzyłem kod. Może Ci to pomoże.

#include <list>
#include <iostream>

using namespace std;

int main()
{
//zbierze dla mnie bliżej nieokreśloną ilość liczb spełniającą pewne warunki(tutaj dałem jekies przykładowe od 1 - 10
list<int> lista;
lista.push_back(1);
lista.push_back(2);
lista.push_back(3);
lista.push_back(4);
lista.push_back(5);
lista.push_back(6);
lista.push_back(7);
lista.push_back(8);
lista.push_back(9);
lista.push_back(10);
//szukanie  n-tego, na przykład indeks 6 bo liczy się od 0
int nElement = 5;
list<int>::iterator iter;
int index, value = 0;
for(iter = lista.begin() , index = 0; iter != lista.end() ; ++index , ++iter)
{
    // sposób na odszukanie  n-tego elementu listy nie
    if(index == nElement){
        value = *iter;
        break;
    }

}

cout << "Wartosc n-tego elementu " << value << endl;


system("pause");
return 0;
}

 

Comments

Bondrusiek po co używasz at() bez obsługi wyjątków?

---

@Evelek

Nie wiem o co Ci chodzi odnośnie obsług wyjątków(nie ogarniam tego jeszcze). Wiem tylko z książek, że lepsze jest pobieranie wartości tylko do odczytu używając metody at() zamiast przeładowywać operator []

---

Czy jest lepsze to bym spekulował. Jeśli mamy pewność, że odczytamy poprawny adres vectora, to używamy []. A jeśli chcemy "ryzykować", to używamy at(), które nam rzuci wyjątek out_of_range jeśli odczytamy niepoprawny adres. Nieobsłużony wyjątek zamyka nam program, a po przechwyceniu go możemy go obsłużyć i nasz program kontynuuje swe działanie.

Answer 2

#include <list>
#include <iterator>
#include <iostream>
using namespace std;

int main(){
    list<int> lista {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    
    cout << "Odczytaj wartosc, ktora jest szosta w kolejnosci:" << endl;
    auto pos = lista.cbegin();
    advance(pos, 5);
    cout << *pos;
}

 

Comments

Czy funkcja cbegin() ustala miejsce od którego później zaczniemy odliczanie do pięciu na miejsce pierwsze czyli na sam początek listy?

Jeśli tak to w jaki sposób (i czy to w ogóle jest możliwe)  mógłbym ustalić to miejsce na przykład na czwarte w liście?

---

Najpierw wyjaśnienia: mamy dwie podobne funkcje: begin() oraz cbegin(). Różnica pomiędzy nimi jest taka:

#include <list>
#include <iterator>
#include <iostream>
using namespace std;
 
int main(){
    list<int> lista {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
     
    cout << "Odczytaj wartosc, ktora jest szosta w kolejnosci:" << endl;
    auto pos = lista.begin();
    advance(pos, 5);
    *pos = 100;
    cout << *pos;
}

Samo begin() pozwoli nam na modyfikację wartości wskazywanej przez iterator pos, zaś uzycie cbegin() nam na to nie pozwoli:

#include <list>
#include <iterator>
#include <iostream>
using namespace std;
 
int main(){
    list<int> lista {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
     
    cout << "Odczytaj wartosc, ktora jest szosta w kolejnosci:" << endl;
    auto pos = lista.cbegin();
    advance(pos, 5);
    *pos = 100; // błąd: assignment in read-only location
    cout << *pos;
}

Literka c w funkcji cbegin() to skrót od const, czyli stały. Funkcje begin() oraz cbegin() wskazują zawsze na pierwszy początkowy element danego kontenera.

Następnie użyłem funkcji advance() w celu przesunięcia iteratora pos o 5 miejsc do przodu. Jeśli chcesz go ustawić na miejsce czwarte, napiszesz: advance(pos, 3). Poeksperymentuj.  Ale tak jak już napisał mokrowski, użycie vectora będzie lepsze. Ale jeśli chcesz poznać jak działa kontener list, to użyj list.  Na koniec możesz jeszcze to samo napisać ale używając forward_list.

---

To wiele wyjaśnia, dzięki ;)

Answer 3

Jeśli nie masz ku temu poważnych powodów by stosować listę, zastosuj vector. Lista ma duży narzut związany z wydajnością bo pogarsza współczynnik trafiania w cache procesora. Wartości wskazują na "porozrzucane" adresy pamięci. Za to lista broni się szybkim wstawianiem przy znanym elemencie przed/po. vector przy wstawieniu elementu pomiędzy inne powoduje kopiowanie zawartości pamięci wszystkich elementów po oraz w najbardziej pesymistycznym przypadku kopiowanie całości wektora.

Comments

Chcę znaleźć wartość jakiegoś elementu np 4-tego wykonać na nim pewne operacje a później przeskoczyć do 5-tego elementu i zrobić z nim to samo. Jeżeli dobrze rozumiem to co napisałeś to w tym przypadku lista będzie lepszym rozwiązaniem.

---

Użycie vectora będzie lepsze, bo pozwoli Ci na bezpośrednie odwoływanie się do elementów.

---

Jeśli potrzebujesz tego co napisałeś, użyj vector.

Answer 4

Dzięki za odpowiedzi, zaraz przetestuję obie wersje ;)