Pole pointerů na struktury – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

Pole pointerů na struktury – C / C++ – Fórum – Programujte.comPole pointerů na struktury – C / C++ – Fórum – Programujte.com

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
-stco
~ Anonymní uživatel
4 příspěvky
28. 3. 2013   #1
-
0
-

Ahoj, potřeboval bych poradit jak vytvořit pole pointerů na struktury. Pole samotných struktur mi asi nevyhovuje kvůli časové náročnosti na kopírování obsahu pole při zvětšování (kopírování celých struktur oproti kopírování pointerů). Pole musím být schopný i zvětšit (zatím se mi nepodařilo zvětšení bez memory leaku). Nesmím použít vector ani list (STL). Snad jsem to sepsal dost srozumitelně

Dejme tomu, že mám strukturu:

struct S {
  string a;
  string b;
};

Pole ukazatelů vytvořím takto?

S ** polePointeru = new S*[velikost];
for(int i = 0; i < velikost; i++) {
  polePointeru[i] = new S;
}

Zápis?

for(int i = 0; i < velikost; i++) {
  polePointeru[i]->a = "a";
  polePointeru[i]->b = "b";
}

Výpis?

for(int i = 0; i < velikost; i++) {
  cout << polePointeru[i]->a << ' ' << polePointeru[i]->b << endl;
}

Uvolnění paměti (to nedělám před zvětšováním pole, jen ukázka jestli nedělám něco špatně):

for (int i = 0; i < velikost; i++) {
  delete polePointeru[i];
}
delete[] polePointeru;

Špatné zvětšování pole:

S ** tmp = new S*[zvetsenaVelikost];  // nove vetsi pole
for(int i = 0; i < zvetsenaVelikost; ++i) {
  tmp[i] = new S;
}

for (int i = 0; i < velikost; i++) { // kopirovani pointeru do vetsiho pole
  tmp[i] = polePointeru[i];
}

polePointeru = tmp; // timhle zrejme zpusobim memory leak

Jak správně zvětšit to pole a uvolnit paměť?

Nahlásit jako SPAM
IP: 2001:718:2:31:4847:f017:d...–
Reklama
Reklama
vitamin+8
Grafoman
29. 3. 2013   #2
-
0
-

std::string je vlastne pointer ktory ukazuje na dynamicky alokovane pole charov (pripadne aj dalsie data). To znamena ze velkost stringuje je na 64bit systeme vecsinou 8B. Struktura S ma len 2 stringy, takze samotna struktura zabera len 16B co je strasne malo. Takze kludne mozes pouzit pole v ktorom budu priamo ulozene data, nemusis dynamicky alokovat kazdy prvok (co je o dost pomalsie ako alokovanie jedneho bloku naraz). V pripade stringu mozes na kopirovanie pouzit std::memcpy co sposobi ze sa nebude volat zbytocne kopirovaci/presuvaci konstruktor (std::vektor funguje podobne). 

Uchovavanie v poli pointre na prvky miesto samotnych prvkov ma dalsiu nevyhodu. Kedze su jednotlive prvky alkovane dynamicky tak su rostrusene po heape. To sposoby ze program nemoze natiahnut cely blok dat do cache pamete a kvoly kazdemu jednemu prvku ho musi nacitavat z ram, cize dalsie spomalenie. 

Tvoje riesenie ma jednu vyhodu. Ak realokujes pole, tak adresa prvku ostane rovnaka, takze mozes vytvarat pointre na prvky a po realokovani pola su pointre stale OK co pri std::vectore neplati (vecsinov tato vlastnost nie je potrebna)

Takze aj ked si myslis ze pole pointrov na data bude efektivnejsie ako pole dat, tak to bude skor opacne  (Samozrejme implementacia dynamcikeho pola tak aby sa zbytocne nevolali konstruktory nie je uplne trivialna)

----------------------------------

Tvoje riesenie je ok, a tam kde si napisal ze mas memory lake ho naozaj mas, riesenie je jednoduche:

size_t pocetPrvkov = N;	//pocet prvkov v poly
size_t povodnaVelkost = N;	//velkost pola
size_t zvetsenaVelikost = N + X;	//velkost zvecseneho pola, je dobre ak X > 1 neh sa nemusi casto realokovat
S** polePointeru;	

S ** tmp = new S*[zvetsenaVelikost];  // nove vetsie pole
std::memcpy(tmp, polePointeru, sizeof(S*)*povodnaVelkost);	//skopyruje pointre, netreba znovu alokovat kazdy prvok

delete [] polePointeru;	//zmaze povodne pole

polePointeru = tmp; 
//--------------------------------------------------------------
//pridanie prvku do pola:

polePointeru[pocetPrvkov] = new S;
++pocetPrvkov;
Nahlásit jako SPAM
IP: 95.105.157.–
obfuscate: "The cruel god Malloc will strike you down. "
ZMeson: "That's the C god. C++ has a new god. "
-stco
~ Anonymní uživatel
4 příspěvky
29. 3. 2013   #3
-
0
-

Díky za rady, navedlo mě to na jednu chybu, kterou jsem dělal.

Celkově je ten problém trochu složitější. Při vkládání prvku ho musím zařadit na správné místo a posunout zbytek prvků, aby zůstalo seřazené - tady myslím je ten rozdíl pointer na strukturu oproti samotné struktuře více znát (možná se pletu). Taky je potřeba prvky odebírat a vyhledávat (binarysearch kvůli rychlosti).

Jestli máš ještě další tipy, rád si je přečtu.

Nahlásit jako SPAM
IP: 90.181.8.–
vitamin+8
Grafoman
29. 3. 2013   #4
-
0
-

V akom pomere (priblizne) mas oparecie vkladania prvka do pola a vyhladavanie prvka?

Budes prvky z pola mazat?

Idealne by bolo kebyze pole najprv naplnis a potom budes v nom len vyhldavat.

Nahlásit jako SPAM
IP: 95.105.157.–
obfuscate: "The cruel god Malloc will strike you down. "
ZMeson: "That's the C god. C++ has a new god. "
-stco
~ Anonymní uživatel
4 příspěvky
29. 3. 2013   #5
-
0
-

Vyhledávání bude mnohem častější (tipuju tak 10 vyhledávání na 1 vložení). Některé prvky z pole budu mazat. Pole se nebude plnit celé najednou a bude bez duplicitních záznamů.

Nahlásit jako SPAM
IP: 90.181.8.–
vitamin+8
Grafoman
30. 3. 2013   #6
-
0
-

Mozes si spravyt upravene binarne vyhladavanie ktore bude hladat adresu/index najvecsieho prvka pola ktory je mensi ako prvok ktory chces do pola vlozit. Potom vsetky prvky ktore su napravo od najdeneho prvka posunies (napr pomocou memcpy, ak treba tak zvecsis pole). Potom vlozis na uvolnenu poziciu novy prvok.

Dalej ma napada ze mozes prvky vkladat na koniec pola, a pred vyhladavanim spustis daky sort(napr quick sort, marge sort) ktory usporiada pole (v dakej premennej si uchovavaj stav pola: zotridene/nezotriedene).

Dalej mozes miesto pola pouzit binarny strom (nieco na sposob std::set, std::map).

//.....

Vo vsetkych pripadoch mozes urychlit porovnavanie prvkov tym ze budes porovnavat hashe prvkov (na sposob std::unordered_map)

Nahlásit jako SPAM
IP: 95.105.157.–
obfuscate: "The cruel god Malloc will strike you down. "
ZMeson: "That's the C god. C++ has a new god. "
-stco
~ Anonymní uživatel
4 příspěvky
31. 3. 2013   #7
-
0
-

Dělám to správně, když chci posunout prvky pole o jeden doprava? Používám memmove, protože memcpy by mi nejspíš přepisoval hodnoty, které ještě nestihl zkopírovat.

searchIndex je return hodnota binary searche, pole bude vždycky dost velké na posun

memmove(polePointeru + (searchIndex+1) * sizeof(S*),
	polePointeru + searchIndex * sizeof(S*),
	(pocetPrvku - position) * sizeof(S*));
Nahlásit jako SPAM
IP: 90.181.8.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 100 hostů

Podobná vlákna

Inkrementace pointeru — založil Zelenáč

Vyznam pointeru — založil Alan

Velikost pointeru — založil Pavelv

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý