Hi erstmal!

Ich versuche gerade in einer kleinen testimplementierung diesen Algorithmus http://drdobbs.com/database/184410529?pgno=1 http://drdobbs.com/database/184410529?pgno=1 aus Listing Four zu implementieren. Prinzipiell versteh ich den Algorithmus, allerdings kommt es in meiner Implementierung immer zu einer Assertion mit der Expression: vector iterator + offset out of range.

Meiner Meinung dürfte der Fehler nicht auftreten, aber sowie es scheint, übersehe ich etwas. Nur für den Fall das es wichtig sein sollte, ich mache das ganz mit Visual Studio 2010, es handelt sich um eine C++ Console Application.

Nachfolgend poste ich mal meinen Code, ich glaub die Variablennamen sprechen für sich, falls nicht dann nachfragen *g*, beziehungsweise sind großteils gleich dem beschriebenen Algorithmus des obigen Links.

Ich hoffe es sieht jemand vl. den Fehler, ich sehs nicht, vermutlich is es eh was ganz blödes einfaches. *g*

Code :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190

#include <iostream> #include <ctime> #include <vector>   using namespace std;   int mapsize = 10;   void init(char** map){       srand(time(0));           for(int i = 0; i<mapsize; ++i){         cout<<"\n";         for(int j = 0; j<mapsize; ++j){             map[i][j] = (int)(rand()/(double)(RAND_MAX)+0.8)+'0';         }     }       for(int i = 0; i<mapsize; ++i){         cout<<"\n";         for(int j = 0; j<mapsize; ++j){             cout<<map[i][j];         }     }     cout<<"\n\n";   }   struct Pos{     int x;     int y;       Pos(){         x = 0;         y = 0;     }       Pos(int x, int y){         this->x = x;         this->y = y;     } };   struct Rectangle{       Pos ur;     Pos ll;       Rectangle(){         ur = Pos(-1,-1);         ll = Pos(0,0);     }       Rectangle(Pos ur, Pos ll){         this->ur = ur;         this->ll = ll;     }   };   struct TempRect{       int startPos;     int width;       TempRect(int startPos, int width){         this->startPos = startPos;         this->width = width;     }   };   int area(Rectangle best_rect){         if (best_rect.ll.x > best_rect.ur.x || best_rect.ll.y > best_rect.ur.y){ // If ur is left of or         return 0;               // below 11: return 0     }     else{         return (best_rect.ur.x-best_rect.ll.x+1)*(best_rect.ur.y-best_rect.ll.y+1);     }   }   void update_cache(int x, char** map, int* cache){       for(int y = 0; y < mapsize; y++){         if(map[x][y] != '0'){             cache[y] = cache[y]+1;         }else{             cache[y] = 0;         }     }   }   void findBiggestRectangle(char** map){       int* cache = new int[mapsize];     vector<TempRect> rectangle_stack;     Rectangle best_rect;     TempRect oldRect(0,0);       for(int i = 0; i < mapsize; i++){         cache[i] = 0;     }       int width = 0;       for(int x = mapsize-1; x >= 0; x--){         update_cache(x, map, cache);         width = 0;         for(int y = 0; y < mapsize; ++y){             if(cache[y] > width){                 rectangle_stack.push_back(TempRect(y, width));                 width = cache[y];             } else if(cache[y] < width){                 do{                     cout<<rectangle_stack.size();                     oldRect = TempRect(rectangle_stack.back().startPos, rectangle_stack.back().width);                     //oldRect = rectangle_stack.back();                                           rectangle_stack.pop_back();                       if(width*(y-oldRect.startPos) > area(best_rect)){                         best_rect.ll = Pos(x, oldRect.startPos);                         best_rect.ur = Pos(x + width-1, y-1);                     }                     width = oldRect.width;                   }while(cache[y] >= width && rectangle_stack.size() != 0);                 width = cache[y];                   if(width !=0){                     rectangle_stack.push_back(TempRect(oldRect.startPos, width));                 }             }         }     }       cout<<"ll x: "<<best_rect.ll.x<<" ll y: "<<best_rect.ll.y<<endl;     cout<<"ur x: "<<best_rect.ur.x<<" ur y: "<<best_rect.ur.y<<endl;     for(int j = best_rect.ll.y; j <= best_rect.ur.y; ++j){     for(int i = best_rect.ll.x; i <= best_rect.ur.x; ++i){                     map[i][j] = 'x';         }     }       for(int i = 0; i<mapsize; ++i){         cout<<"\n";         for(int j = 0; j<mapsize; ++j){             cout<<map[i][j];         }     }     cout<<"\n\n";   }     int main(void){           char** map = new char*[mapsize];       for(int i = 0; i < mapsize; ++i) {         map[i] = new char[mapsize];     }       for(int i = 0; i<mapsize; ++i){         //cout<<"\n";         for(int j = 0; j<mapsize; ++j){             map[i][j] = '0';             //cout<<map[i][j];         }     }     //cout<<"\n\n";       init(map);       findBiggestRectangle(map);         return 0; }

Hi und Willkommen bei tutorials.de

Hast du einmal überprüft, in welcher Zeile der Fehler auftritt?

Was übrigens sofort auffällt: Du gibst den mit new reservierten Speicher nicht mehr frei.
Ist nicht der Fehlergrund, aber auch schlecht.

Erstmal schon danke für die schnelle antwort, seit echt flott hier *g*

Der Fehler tritt in Zeile 123 hier oldRect = TempRect(rectangle_stack.back().startPos, rectangle_stack.back().width); auf.

Also quasi wenn der rectangle_stack die size = 0 hat. Aber wenn das so is, sollt er ja garnicht mehr in dem Code bereich sein.

Das mit dem Speicher ist mir bewusst, wie gesagt, is nur ne schnelle testimplementierung, weils eigentlich für die Anwendung in nem umfangreicheren Projekt gedacht is, drum is der code etwas dirty momentan. *g*

Hmm, also bei läuft besagte Zeile fehlerfrei, dafür geht bei 153 was daneben...
schau mir das mal genauer an.

ich hab jetzt oben mal den code angepasst, irgendwie passts noch immer nicht, zumindest semmelts jetzt nicht mehr ab. aber das ergebnis scheint nicht zu stimmen, irgendwie, vl. sieht wer warum.

@Sheel: cool das es bei dir da nicht absemmelt, vl. mag mich mein VS auch wiedermal nicht *g*

Zumindest den Absturzgrund kann ich dir jetzt auch sagen
Ein i statt einem j in einer Schleifenbedingung...jetzt von dir schon (bewusst?) ausgebessert.
Die Reihenfolge der Schleifen hätte aber auch so bleiben können.

edit: Aber irgendwo ist da noch ein gewaltiges Pointerproblem.
Jetzt bleibt das Programm nämlich an den verschiedensten Stellen einfach stehen, immer wo anders.
Liegt wohl an den Zufallszahlen

jo oben bewusst ausgebessert, hätt ich vl. erwähnen sollen

jo das ergebnis stimmt aber igendwie leider nicht, egal ob ich die reihenfolge der schleifen umdrehe oder lasse, puh diese algo kostet mich mehr nerven als ich dache. *g*

@Sheel: aha, machts bei mir nicht, also es scheint immer auf ein ergebnis zu kommen, aber halt nit das richtige bei mir zumindest. aber durchlaufen tuts schon.

Einmal ganz unabhängig von Pointer- und Compilerwitzen:
Wtf ist die Funktion area?
Warum für x und y plus 1?
4x2 ist für mich 8. area sagt 15.

das +1 is, damit die Fläche bei einzelnem Kasterl ned null, sonderrn 1 is
bzw. einzelne Zeilen und Spalten wärn ja sonst auch imemr Fläche null

bei kommt da übrigens schon stimmiges an werten raus

Mittlerweile find ich zwar immer ein Rectangle nur ist es nicht immer das größte, obwohl es das größte sein müsste nach dem obrigen Algorithmus (siehe Link)

Scheinbar implementiere ich den Algorithmus nicht 100%ig richtig, ich seh aber nicht was ich falsch mache.

hier mal aktueller Code:

Code :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209

#include <iostream> #include <ctime> #include <vector>   using namespace std;   int mapsize = 10;   void init(char** map){       srand(time(0));           for(int i = 0; i<mapsize; ++i){         cout<<"\n";         for(int j = 0; j<mapsize; ++j){             //map[i][j] = '1';             map[i][j] = (char)((int)(rand()/(double)(RAND_MAX)+0.1)+'0');         }     }     //map[9][10] = '1';     //map[9][11] = '1';     //map[10][9] = '1';     //map[10][10] = '1';     //map[10][11] = '1';     //map[10][9] = '1';     //map[11][9] = '1';     //map[10][8] = '1';     //map[11][8] = '1';     //map[11][10] = '1';     //map[11][11] = '1';     //map[11][12] = '1';     //map[12][10] = '1';     //map[12][9] = '1';         for(int i = 0; i<mapsize; ++i){         cout<<"\n";         for(int j = 0; j<mapsize; ++j){             cout<<map[i][j];         }     }     cout<<"\n\n";   }   struct Pos{     int x;     int y;       Pos(){         x = 0;         y = 0;     }       Pos(int x, int y){         this->x = x;         this->y = y;     } };   struct Rectangle{       Pos ur;     Pos ll;       Rectangle(){         ur = Pos(-1,-1);         ll = Pos(0,0);     }       Rectangle(Pos ur, Pos ll){         this->ur = ur;         this->ll = ll;     }   };   struct TempRect{       int startPos;     int width;       TempRect(int startPos, int width){         this->startPos = startPos;         this->width = width;     }   };   int area(Rectangle best_rect){         if (best_rect.ll.x > best_rect.ur.x || best_rect.ll.y > best_rect.ur.y){ // If ur is left of or         return 0;               // below 11: return 0     }     else{           int val = (best_rect.ur.x-best_rect.ll.x+1)*(best_rect.ur.y-best_rect.ll.y+1);           return val;     }   }   void update_cache(int x, char** map, int* cache){       for(int y = 0; y < mapsize; y++){         if(map[x][y] != '0'){             cache[y] = cache[y]+1;         }else{             cache[y] = 0;         }     }   }   void findBiggestRectangle(char** map){       int* cache = new int[mapsize];     vector<TempRect> rectangle_stack;     Rectangle best_rect;     TempRect oldRect(0,0);       for(int i = 0; i < mapsize; i++){         cache[i] = 0;     }       int width = 0;       for(int x = mapsize-1; x >= 0; x--){         update_cache(x, map, cache);         width = 0;         for(int y = 0; y < mapsize; ++y){             if(cache[y] > width){                 rectangle_stack.push_back(TempRect(y, width));                 width = cache[y];             } else if(cache[y] < width){                 do{                     //cout<<rectangle_stack.size();                     oldRect = TempRect(rectangle_stack.back().startPos, rectangle_stack.back().width);                     //oldRect = rectangle_stack.back();                                           rectangle_stack.pop_back();                       if(width*(y-oldRect.startPos) > area(best_rect)){                         best_rect.ll = Pos(x, oldRect.startPos);                         best_rect.ur = Pos(x + width-1, y-1);                     }                     width = oldRect.width;                   }while(cache[y] >= width && rectangle_stack.size() != 0);                 width = cache[y];                   if(width !=0){                     rectangle_stack.push_back(TempRect(oldRect.startPos, width));                 }             }         }     }       cout<<"ll x: "<<best_rect.ll.x<<" ll y: "<<best_rect.ll.y<<endl;     cout<<"ur x: "<<best_rect.ur.x<<" ur y: "<<best_rect.ur.y<<endl;     for(int j = best_rect.ll.y; j <= best_rect.ur.y; ++j){         for(int i = best_rect.ll.x; i <= best_rect.ur.x; ++i){                     map[i][j] = 'x';         }     }       for(int i = 0; i<mapsize; ++i){         cout<<"\n";         for(int j = 0; j<mapsize; ++j){             cout<<map[i][j];         }     }     cout<<"\n\n";   }     int main(void){           char** map = new char*[mapsize];       for(int i = 0; i < mapsize; ++i) {         map[i] = new char[mapsize];     }       for(int i = 0; i<mapsize; ++i){         //cout<<"\n";         for(int j = 0; j<mapsize; ++j){             map[i][j] = '0';             //cout<<map[i][j];         }     }     //cout<<"\n\n";       init(map);       findBiggestRectangle(map);         return 0; }

Sieht jemadn was ich anders oder falsch implementiert habe bei dem Algo?