|
[ Relaja @ 20.03.2006. 11:33 ] @
| Ovako...Kada deklarisemo niz ,recimo int a[10], a predstavlja pointer na prvi element niza..Tako
se mozemo kretati kroz sve elemente tako sto cemo a povecati za jedan i nalazimo se na &a[1]..
E sad, zasto recimo ne bi moglo ovo...Mislim, ja sam probao i radi , ali do sada nisam igde video da neko to radi.
Recimo dodjemo do zadnjeg elementa niza , sto je pointer a = &a[9].Kada to a uvecamo za jedan
nadjemo se na novoj memorijskoj adresi koja bi trebalo da predstavlja sledeci element ukoliko niz ima 11 clanova.
Ukoliko na toj memorijskoj adresi upisemo neku vrednost, pristupanje clanu a[10] bi trebalo da bude moguce...
Da li sam u pravu?
Poz, |
[ Buffy @ 20.03.2006. 11:56 ] @
Nisi u pravu, jer &a[10] nije alocirano. Program bi ti trebao da pukne u runtime-u, ali na zalost to se uvjek ne desava.
Poenta je da nikad ne treba izlaziti iz opsega alociranog memorijskog prostora, jer kad tad program moze da pukne.
[ Relaja @ 20.03.2006. 12:40 ] @
ok.Hvala ti.
[ Goran Arandjelovic @ 20.03.2006. 13:06 ] @
Pazi ovaj primer...
Code:
#include <iostream>
using namespace std;
int main(int argc, char *argv[])
{
int x[5];
int a[5];
for(int i=0;i<5;i++){
x[i] = 13; // ceo niz a ispunimo trinaesticama
}
a[8] = 17;
for(int i=0;i<5;i++){
cout << x[i] << endl; // ovde bi trebalo da ispise sve trinaestice, ali...
}
}
Elem, bombardovao bi memoriju koja nije alocirana. Ne mora doći do pucanja programa u datom trenutku, nego se može desiti gora stvar, da uništiš neki drugi objekat, a da program nastavi... ali sa totalno neočekivanim rezultatima. Igraj se malo sa adresama tih nizova (objekata), jer kao što vidiš adresa nealociranog elementa a[8] je zapravo adresa prvog elementa x niza!
Code:
#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char *argv[])
{
vector<int> mojniz;
mojniz.push_back(13);
mojniz.push_back(17);
cout << mojniz[0] << endl << mojniz[1];
}
Koristi vektor.
[ seymour @ 20.03.2006. 14:23 ] @
Evo sledeca fu-ja bi mogla da se koristi za dinamicko menjanje velicine niza int-ova(int **n je pokazivac na sam niz(to je pokazivac na pokazacivac na int),int size je nova velicina, int oldsize je stara velicina niza(podrazumevano je 0))
Code:
void newSize(int **n,int size,int oldSize = 0){
int *tmp;
tmp = new int[size];
if (oldSize > 0) memcpy(tmp,*n,4*oldSize);
delete *n;
*n = tmp;
}
}
evo ti primer koji koristi ovu fu-ju
Code:
#include <cstdlib>
#include <iostream>
using namespace std;
void newSize(int **n,int size,int oldSize = 0){
int *tmp;
tmp = new int[size];
if (oldSize > 0) memcpy(tmp,*n,4*oldSize);
delete *n;
*n = tmp;
}
int main(int argc, char *argv[])
{
int i;
int *d;
newSize(&d,10);
for (i = 0;i<10;i++)
d[i] = i;
newSize(&d,20,10);
for (i = 0;i<10;i++)
d[i + 10] = i;
for (i = 0; i < 20; ++i)
cout<<d[i]<<endl;
system("pause");
return EXIT_SUCCESS;
}
[ Relaja @ 20.03.2006. 15:19 ] @
Dobro.Hvala svima..I predpostavljao sam da nacin koji sam ja naveo nije
dobar samim tim sto vector koristi drugi nacin promene velicine niza.Nisu drugi ljudi glupi  .
Ali sam hteo da proverim gde pada...
Sada znam.
Poz,
[ leka @ 20.03.2006. 17:33 ] @
Dobro, svima je jasno da je svaka diskusija na ovu temu zapravo diskusija kako implementirati std::vector :)
[ Srđan Krstić @ 21.03.2006. 21:03 ] @
samo da napomenem da vredi pogledati i realloc (narocito ako se radi o c-u)
[ z@re @ 22.03.2006. 02:02 ] @
najgore su greske koje se pojave tu i tamo...a upravo ce ti se to desiti ako budes gazio nealociranu memoriju po volji. u C-u koristis realloc za ovakve stvari.
prvo niz neces deklarirati sa int a[10]; vec int *a = (int *)malloc(sizeof(int) * 10);
ako ga hoces produziti na recimo 12 elemenata pises a = (int *)realloc(a, sizeof(int) * 12);
i to bi bilo to.
[ Srđan Krstić @ 24.03.2006. 02:01 ] @
cisto interesantna cinjenica: verovatno najgora moguca greska koja moze da se napravi u c-u je korisenje realloc-a na sledeci nacin:
int *a = (int *)malloc(a, (size_t)sizeof(int) * 10);
...
realloc(a, (size_t)sizeof(int) * 12);
greska je sto je zaboravljeno da se pokazivacu a dodeli nova vrednost, pocetak memorije oslobodjene realloc-om. Ukoliko je odmah iza memorije gde je bio smesten niz od 10 elemenata bilo dovoljno mesta da se smeste jos 2 elemena, ovo ce bez greske odraditi posao. Medjutim, ako nije, ceo niz ce biti iskopiran na novo mesto u memoriji gde ima dovoljno mesta za niz od 12 clanova. Ono sto je interesantno je sto se ovim pravi ne jedna, nego 3 ocajne greske (meni je bar ovo bas cool :)). Dakle:
1. ne moze se nikako proveriti da li je realloc vratio NULL, i samim tim sledeca upotreba niza a dovesce do segmentation fault-a
2. ne moze se nikako osloboditi memorija u kojoj je sada niz a, sto dovodi do memory leak-a
3. posto smo svi, jel'te, dobri i pazljivi programeri, mi cemo lepo pokusati da free-ujemo niz a posle upotrebe. Ali avaj, a jos uvek pokazuje na mesto gde je NEKAD bio niz a, sto je vec oslobodio realloc, i dakle pravimo tzv "double free" gresku.
Mislim da sa samo 2 karatkera razlike gora glupost ne moze nikako da se napravi :)
[ z@re @ 27.03.2006. 01:43 ] @
Ne razumijem sta zelis kazat. Ako ima mjesta za prosirenje realokacijom postojeceg bloka, postojeci blok se siri i pointer ostaje isti. Ako nema, alocira se tamo gdje ima, stari blok se prekopira na novo alocirano mjesto, pointer gleda na novi blok, a stari blok se dealocira.
Citat:
OpenBSD 3.5 -> src.tar.gz -> \.\lib\libc\stdlib\malloc.c
Code:
static void *realloc(void *ptr, size_t size)
{
void *p;
u_long osize, index;
struct pginfo **mp;
int i;
if (suicide)
abort();
if (!malloc_started) {
wrtwarning("malloc() has never been called\n");
return (NULL);
}
index = ptr2index(ptr);
if (index < malloc_pageshift) {
wrtwarning("junk pointer, too low to make sense\n");
return (NULL);
}
if (index > last_index) {
wrtwarning("junk pointer, too high to make sense\n");
return (NULL);
}
mp = &page_dir[index];
if (*mp == MALLOC_FIRST) { /* Page allocation */
/* Check the pointer */
if ((u_long)ptr & malloc_pagemask) {
wrtwarning("modified (page-) pointer\n");
return (NULL);
}
/* Find the size in bytes */
for (osize = malloc_pagesize; *(++mp) == MALLOC_FOLLOW;)
osize += malloc_pagesize;
if (!malloc_realloc && /* Unless we have to, */
size <= osize && /* .. or are too small, */
size > (osize - malloc_pagesize)) { /* .. or can free a page, */
if (malloc_junk)
memset((char *)ptr + size, SOME_JUNK, osize-size);
return (ptr); /* ..don't do anything else. */
}
} else if (*mp >= MALLOC_MAGIC) { /* Chunk allocation */
/* Check the pointer for sane values */
if ((u_long)ptr & ((1UL<<((*mp)->shift))-1)) {
wrtwarning("modified (chunk-) pointer\n");
return (NULL);
}
/* Find the chunk index in the page */
i = ((u_long)ptr & malloc_pagemask) >> (*mp)->shift;
/* Verify that it isn't a free chunk already */
if ((*mp)->bits[i/MALLOC_BITS] & (1UL<<(i%MALLOC_BITS))) {
wrtwarning("chunk is already free\n");
return (NULL);
}
osize = (*mp)->size;
if (!malloc_realloc && /* Unless we have to, */
size <= osize && /* ..or are too small, */
(size > osize/2 || /* ..or could use a smaller size, */
osize == malloc_minsize)) { /* ..(if there is one) */
if (malloc_junk)
memset((char *)ptr + size, SOME_JUNK, osize-size);
return (ptr); /* ..don't do anything else. */
}
} else {
wrtwarning("pointer to wrong page\n");
return (NULL);
}
p = imalloc(size);
if (p != NULL) {
/* copy the lesser of the two sizes, and free the old one */
/* Don't move from/to 0 sized region !!! */
if (osize != 0 && size != 0) {
if (osize < size)
memcpy(p, ptr, osize);
else
memcpy(p, ptr, size);
}
ifree(ptr);
}
return (p);
}
[ PeRuN_RoJs @ 20.04.2006. 00:19 ] @
Ukoliko vec koristis pokazivac, zasto stavljas i a[10], tj. staticki alociras deset mesta?
zar nije pametnije uvesti pokazivac a na tip od koga je sastavljen niz, recimo int, i kasnije alocirati 10 mesta:
Code:
a=(int*)malloc(10*sizeof(int));
naravno bilo kom clanu mozes pristupiti sa:
Code:
n-ti_clan=*(a+n-1);
//n<10
a i mozes uvek povecati-smanjiti broj rezervisanih mesta za taj niz
[ z@re @ 20.04.2006. 17:36 ] @
Moze na dva nacina pristupit : standardnom notacijom polja, a[10], ili *(a + 10). Cini mi se da je drugi nacin brzi, jer kod prvog slucaja kompajler pravi adresa+offset, a kod drugog se automatski generira krajnja adresa, iako izgleda bas obratno.
[ @zrael @ 20.04.2006. 19:20 ] @
prije nekoliko dana sam imao mogucnost da pricam sa jednim od svjetskih strucnjaka sa podrucja programiranja. rekao mi je kako danas u velikim programskim pothvatima su polja sve manje i manje u upotrebi te da da se umjesto njih koriste iskljucivo vezane liste. u c i c++ jos postoji mogucnost direktnog rada i manipuliranja vezanih lista. u programskim jezicima tipa java, python i tcl takodjer se radi sa vezanim listama samo, ali korisnik to ne primjeti posto koristi runtime envireoment. u pythonu se moze reci da su polja i lista jedno te isto. polja se koristi samo zato jer je lakse razmisljati s njima iako vezane liste daju daleko vise mogucnosti. U svakom slucaju su polja za pocetnika fantasticna stvar, ali za one koji se malo ozbiljnije zele baviti moraju napustiti polja i preci na liste. mozda jos uvijek razmiljas sa poljima, ali ako hoces i nemas jos iskustva ili bilo sto drugo, mogu postat adrese na jako dobre power point prezentacije s kojima ces razumjeti jako lako bit vezanih listi. Ne znam koliko znas o tome, pa please nemoj misliti da te podcjenjujem ili bilo sto slicno.
[ NrmMyth @ 20.04.2006. 22:19 ] @
Citat: z@re: Moze na dva nacina pristupit : standardnom notacijom polja, a[10], ili *(a + 10). Cini mi se da je drugi nacin brzi, jer kod prvog slucaja kompajler pravi adresa+offset, a kod drugog se automatski generira krajnja adresa, iako izgleda bas obratno. Istina, ali to neradi nikakvu, ama bas nikakvu razliku, jedino 2 oblik moze pogorsati citljivost koda. I sigurno postoji optimizacija u samom kompjleru koja izvodi prepis [x] i *(+x).
Citat: @zrael:svjetskih strucnjaka sa podrucja programiranja.
I on ti je rekao da ne koristis polja nego liste...
Citat: , ali za one koji se malo ozbiljnije zele baviti moraju napustiti polja i preci na liste
Boze...
- Polje ima O(1) za dohvacanje elemenata dok lista ima O(N)
- Polje ima za insertiranje elemenata O(N) dok lista ima O(1)
To su glavne razlike (ima ih naravno jos ali mi se neda pisati)...
Sta ako ja zelim implementirati hash tabelu kod koje je krucijalno dohvacanje elemenata po nekom kljucu?
Najblize tome mogu doci sa listama ako napravim binarno stablo, a onda mi je dohvacanje O(log 2N) sto i nije neka brzina ako ti kazem da imam u tom stablu milijardu elemenata.
Hash stablo implementirano sa poljem pruza mi dohvacanje na O(1) koji ne ovisi o broju elementata u samoj tablici (polju).
Sve ima svoje karakteristike, a treba se znati sluziti sa sto vise teorije da bi se znalo iskorititi "ono" pravo u pravom trenutku.
I zato tvoja gornja tvrdnja ne stoji.
Bez uvrede, morao sam stviti karte na stol.
[ Srđan Krstić @ 20.04.2006. 22:20 ] @
Ne mozes tako da kazes, "danas se sve vise koriste samo povezane liste"!
U nekim slucajevima je pametno, ali u nekim je apsolutno suludo koristiti liste
@zare: ne, pointer gleda na novu adresu samo ako mu dodelis vrednost koju ti vrati realloc. U suprotnom naravno nece se automatski promeniti pointer
[Ovu poruku je menjao Srđan Krstić dana 20.04.2006. u 23:24 GMT+1]
[ z@re @ 21.04.2006. 00:56 ] @
Citat: @zrael: prije nekoliko dana sam imao mogucnost da pricam sa jednim od svjetskih strucnjaka sa podrucja programiranja. rekao mi je kako danas u velikim programskim pothvatima su polja sve manje i manje u upotrebi te da da se umjesto njih koriste iskljucivo vezane liste. u c i c++ jos postoji mogucnost direktnog rada i manipuliranja vezanih lista. u programskim jezicima tipa java, python i tcl takodjer se radi sa vezanim listama samo, ali korisnik to ne primjeti posto koristi runtime envireoment. u pythonu se moze reci da su polja i lista jedno te isto. polja se koristi samo zato jer je lakse razmisljati s njima iako vezane liste daju daleko vise mogucnosti. U svakom slucaju su polja za pocetnika fantasticna stvar, ali za one koji se malo ozbiljnije zele baviti moraju napustiti polja i preci na liste. mozda jos uvijek razmiljas sa poljima, ali ako hoces i nemas jos iskustva ili bilo sto drugo, mogu postat adrese na jako dobre power point prezentacije s kojima ces razumjeti jako lako bit vezanih listi. Ne znam koliko znas o tome, pa please nemoj misliti da te podcjenjujem ili bilo sto slicno.
Apsurd. Koristenje dinamickih polja je visoko preporuceno u C-u, zbog optimizacije memorije na kompajlerskom nivou. Jedina pogodnost kod koristenja vezanih lista - ako struktura liste ima recimo, 8 bajtova, mozes imat 2000 elemenata u listi, bez da imas slobodan memorijski blok od 16 kilobajta u komadu, dovoljno je da imas 16 kilobajta slobodne memorije u blokovima, a najmanja kapacitetna vrijednost bloka je sizeof(strukture). No to su vec ekstremni slucajevi. Za danasnje uslove, pa cak i za sistemsko programiranje, dinamicka polja odradjuju posao jako dobro. Imaju i oni problema - brisanje elementa sa back-realokacijom je spor proces, medjutim to se manifestira samo na ogromnim vrijednostima, za koja se ionako koriste stabla, hashtabele, ili neke druge strukture.
Copyright (C) 2001-2025 by www.elitesecurity.org. All rights reserved.
|