[C++] Dopisywanie do vectora z STL

wawek91
Użytkownik
Użytkownik
Posty: 795
Rejestracja: 2 cze 2010, o 08:56
Płeć: Mężczyzna
Lokalizacja: Tarnów
Podziękował: 14 razy
Pomógł: 66 razy

[C++] Dopisywanie do vectora z STL

Post autor: wawek91 »

Witam mam nadzieję, że ktoś znajdzie błąd nad którym ja już siedzę dłuższą chwilę i nie mogę sobie poradzić. Mianowicie mam do napisania algorytm Dijkstry tylko, że graf buduję na zasadzie pobranej mapy z portalu, ale mniejsza o to. Mam vector wierzchołków. Struktura wierzchołka to jego id, długość i szerokość geograficzna. Jednak prowadzący zażyczył sobie aby Dijkstra nie wypisywała drogi po id wierzchołków tylko po ich nazwie. Ok i tutaj następuję problem:

Kod: Zaznacz cały

void getnodesname(vector < Node > &n, vector < Way > w)
{
 for(int i = 0; i < w.size(); i++) //dopóki mamy jakieś drogi
 {
  for(int j = 0; j < w[i].nodes.size(); j++) //dopóki droga posiada zbiór wierzchołków
  {
   for(int k = 0; k < n.size(); k++) //dopóki mamy jakiś wierzchołek
   {
    if(n[k].nid == w[i].nodes[j]) //jeśli id wierzchołka jest takie samo jak id wierzchołka, który zawiera
                                          //sprawdzana droga
    {
     n[k].name = w[i].name;     //to polu name w wierzchołku przypisujemy nazwę drogi     
    }        
   }        
  }        
 }     
}
Tak wiem wiem złożonością się tu nie popisałem jednak chodzi mi o to, że do funkcji jako argument przekazuję vector wierzchołków n, który jest już uzupełniony wartościami takimi jak id, szer i dł geogr. Teraz jednak dopiero mogę przypisać im nazwę i myślałem, że jeśli przekaże vector n jako referencję to zmiany zostaną zachowane jednak po wyjściu z funkcji ten vector jakos dziwnie wygląda. Niektóre wierzchołki dostały nazwę, ale są też takie, które tej nazwy nie mają. Dla przykładu sprawdzałem w funkcji czy są wierzchołki o nazwie "Szkotnik" i takowe są, jednak po wyjściu z funkcji kiedy sprawdzam to samo w mainie to takich wierzchołków już niestety nie ma. Gdzie popełniam błąd?
Ostatnio zmieniony 21 cze 2011, o 11:23 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
abc666

[C++] Dopisywanie do vectora z STL

Post autor: abc666 »

Nie bardzo rozumiem o co tutaj chodzi. Drogi mają nazwy?
wawek91
Użytkownik
Użytkownik
Posty: 795
Rejestracja: 2 cze 2010, o 08:56
Płeć: Mężczyzna
Lokalizacja: Tarnów
Podziękował: 14 razy
Pomógł: 66 razy

[C++] Dopisywanie do vectora z STL

Post autor: wawek91 »

Tak struktura drogi to jej id, nazwa oraz vector wierzchołków które zawiera. Generalnie mam przeparsować xml'a w którym jest zapisana mapa <node> i <way>. Tylko że Dijkstra wypisuje po jakich wierzchołkach przechodzi więc nie wystarczy tylko, że nadam drodze nazwę, ale muszę też nadać ją wierzchołkom, aby potem mogła być wypisana.
abc666

[C++] Dopisywanie do vectora z STL

Post autor: abc666 »

Hmm jeśli dobrze rozumiem to może nadpisujesz po prostu tą nazwę, kiedy dany wierzchołek należy do więcej niż jednej drogi?
wawek91
Użytkownik
Użytkownik
Posty: 795
Rejestracja: 2 cze 2010, o 08:56
Płeć: Mężczyzna
Lokalizacja: Tarnów
Podziękował: 14 razy
Pomógł: 66 razy

[C++] Dopisywanie do vectora z STL

Post autor: wawek91 »

Hm fakt, myslałem o tym jednak nie wiem czemu wziałem pod uwagę jedynie, że nadpiszę go inną nazwą, a nie brakiem nazwy (choć to tez faktycznie jest możliwe). Teraz przetestowałem i faktycznie tak się dzieję, ten wierzchołek jest na skrzyżowaniu paru ulic i stąd dostaje w moim programie inną nazwę. Jeszcze mam pytanie. Ponieważ powyższy kod jak sam widzisz jest strasznie brutalnie napisany. Dałoby się go jakoś przyspieszyć? Choć ja nie widzę póki co innego sposobu, bo muszę sprawdzić wszystkie drogi, potem vector wierzchołków każdej drogi, a w końcu lecieć po wszystkich wierzchołkach, które mam w vectorze i sprawdzać czy należy on do sprawdzanej drogi czy nie.
abc666

[C++] Dopisywanie do vectora z STL

Post autor: abc666 »

Można bardziej pamięć obciążyć. Wpisać do tablicy nazwy od indeks a potem przypisać.

Kod: Zaznacz cały

//alokacja tablic tab

for(int i = 0; i < w.size(); i++)
for(int j = 0; j < w[i].nodes.size(); j++)
    tab[w[i].nodes[j]] = i;

for(int k = 0; k < n.size(); k++)
    n[k].name = tab[n[k].nid];

//dealokacja tab
rozmiar tab musi być taki jak największe id wierzchołka+1

Można to zrobić lepiej, wcześniej, przy parsowaniu. Zależy oczywiście jak to tam wygląda.
ODPOWIEDZ