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

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ěť?

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;

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.

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.

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ů.

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)

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*));