Posunutí hodnot ve vectoru – C / C++ – Fórum – Programujte.com

Ahoj, rád bych se zeptal, jak nejrychleji posunout všechny hodnoty ve vectoru. Př. Mám vector o velikosti 10 a všechny hodnoty potřebuji posunout  o  dvě doleva. Tak aby hodnota s klíčem č. 2 měla klíč č. 0, aby hodnota s klíčem č. 3 měla klíč č. 1 a hodnoty s klíčem č. 8,9 měly hodnotu 0. Pracuji na programu, který by měl umět streamovat velký svět do menšího.

no pravdepodobne skoncis u neceho jako zkopirovat si ty hodnoty, co chces presunout do tempu (dalsi vektor), smazani z puvodniho, a insert toho tempu na zacatek... nebo pokud to nebude velky, pouzit obousmerny list

Nebyla by vhodnější fronta - queue?

Když jsem kdysi něco vyváděl na 8051, použil jsem kus paměti a měl uložený ukazatel na nejstarší aktuální data a ukazatel na místo kam vkládat nová data a "běhal" jsem v tom kousku paměti dokola bez časově náročného posouvání, tuším, že se tomu říká kruhový buffer.

hu

#1 MiCizek

rotate

A kdybych chtěl s pomocí rotate rotovat 2d vector? Program mi vždycky spadne.

#5 MiCizek
Ak máš na mysli niečo ako vector<vector<int>> tak stačí rotovať každý vnútorný vektor:

#include <iostream>
#include <algorithm>
#include <iterator>

int main(){
    std::vector<std::vector<int>> vec{{1,2,3,4,5}, {1,2,3,4,5}, {1,2,3,4,5}};

    //rotuje kazdy podvektor:
    for(auto& v : vec)
        std::rotate(v.begin(), v.begin()+2, v.end());

    //vypis:
    for(auto& v : vec){
        std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, ", "));
        std::cout << '\n';
    }
    return 0;
}

Akorát úplně nechápu zápis 

for(auto& v:vec)

Předpokládám, že všechny prvky vectoru vec postupně uloží do  pomocného vectoru v a na nich provede funkci rotate.

Za druhé já tvořím fraktálový generátor map, který funguje velmi dobře. Ale plánuju, že bych ho použil ve skutečném grafickém enginu a momentálně planuju, že když se hráč posune, tak se mapa taky posune a nová část posunuté mapy se dogeneruje. A proto potřebuju v každém snímku řešit jenom část smyčky. Proto souřadnici x potřebuju zadávat ručně bez smyčky.

#7 MiCizek 

//iterujes cez vsetky prvky vektora vec. Nevytvara kopie prvkov ale referencie, preto je tam &
for(auto& v : vec)v = /*...*/; 

//cez iteratory:
for(auto i = vec.begin(); i != vec.end(); ++i)*i = /*...*/;

//cez index:
for(int i = 0; i < vec.size(); ++i)vec[i] = /*...*/;

//cez std::for_each:
std::for_each(v.begin(), v.end(), [](std::vector<int>& v){  //tiez nevytvara kopiu
    v = /*...*/; 
});

To je novinka z C++11?

hu

#9 hlucheucho
Ano.

#10 vitamin
Nemáš odkaz, ze kterého by se dalo C++11 nastudovat?

hu

Jenom, že mi to při tomhle tom zápisu spadne. 

std::rotate(pixels.at(*pGen->x).begin(), pixels.at(*pGen->x).begin() + CELLS, pixels.at(*pGen->x).end())

#11 hlucheucho
http://en.wikipedia.org/wiki/C++11 pro prehled

A velice podrobne od Stroustrupa The CPP Programming Language  4th edition

#11 hlucheucho
Pekny prehľad je tu: http://en.wikipedia.org/wiki/C++11

Konkrétnejšie príklady si nájdeš na nete.

#12 MiCizek
Padne ti to pri dereferencovaní pGen->x, alebo až po zavolaní rotate? Ak je CELLS väčšie ako veľkosť vektora tak to môže spadnúť.

Sprehľadniť a možno aj zrýchliť by sa to dalo takto:

auto& v = pixels.at(*pGen->x);
std::rotate(v.begin(), v.begin() + CELLS, v.end())

Spadne mi to i když napíšu:

cout << pixels.size() << endl;
cout << pixels.at(0).size() << endl;
std::rotate(pixels.at(0).begin(), pixels.at(0).begin() + 1, pixels.at(0).end());

a obě dimenze mají velikost 512. Spadne mi to vždycky, když k pixels.at(0).begin() přičtu jakékoliv číslo.

#15 MiCizek
Skusil som nieco taketo a toto nepada:

#include <iostream>
#include <algorithm>
#include <iterator>

const auto CELLS = 6;

int main(){
    std::vector<std::vector<int>> vec(512, std::vector<int>(512, 0));

    auto& v = vec.at(5);
    std::rotate(v.begin(), v.begin()+ (CELLS % vec.size()), v.end());

    std::cout << "OK\n";
    return 0;
}

Zjistil jsem, ze problem nastane, když se zavola jeden z operatoru new nebo delete v konstructoru/destructoru struct, co je prvkem vectoru.

#17 MiCizek
Mas kopirovaci konstruktor?

nevoláš delete na něco co neexistuje?

hu

#18 vitamin
aha :-D

Stejně to padá při volání deleta v destructoru.

#20 MiCizek

Tak sem postni tu tvoju triedu.

struct CPixel
{
	CPixel ()
	{
		pixelHeight = new UNSHORT;
		pixelType = new TYPETERRAIN;
		index = new UNSHORT;
		*pixelHeight = 0;
		*pixelType = gtt_Empty;
		*index = 0;
	};
	~CPixel()
	{
		delete pixelHeight;
		delete pixelType;
		delete index;
	}
	CPixel (CPixel *right)
	{
		pixelHeight = new UNSHORT;
		pixelType = new TYPETERRAIN;
		index = new UNSHORT;
		*pixelHeight = *right->pixelHeight;
		*pixelType = *right->pixelType;
		*index = *right->index;
	};
	UNSHORT *pixelHeight;
	TYPETERRAIN *pixelType;
	UNSHORT *index;
};

*height = CELLSCALE*CELLS;
*width = CELLSCALE*CELLS;
pixels.resize(*height);
for (UNSHORT i = 0; i < *height; i++) {
	pixels.at(i).resize(*width);

#23 MiCizek
Kopirovaci konstruktor ma takyto tvar:

MenoTriedy(const MenoTriedy& x);

Ty vobec nepotrebujes dynamicky alokovat premenne:

struct CPixel
{
	UNSHORT pixelHeight = 0;
	TYPETERRAIN pixelType = gtt_Empty;
	UNSHORT index = 0;
};

protoze je to ve vectoru?

#25 MiCizek
new a delete je relativne pomale lebo musi riesit fragmentaciu heapu. Dalej musis vytvarat konstruktor, destructor a copy ctor aby trieda/struktura spravne fungovala. Zaroven bude struktura vecsia lebo v nej mas pointre na data ktore zaberaju 8B (pri 64bit systeme) + data na heape a pristup k nim bude pomalsi lebo musis dereferencovat pointer a data na heape nemusia ist za sebou takze ani cache pamet sa nepotesi :)

Tomuto vsetkemu sa vyhnes ak pouzies tu strukturu co som sem dal predtym.

to vím, že když dynamicky allocuju paměť, tak je to pomalejší. Ale zase pro nedynamicky allocovanou paměť je omezenější velikost ne?

#27 MiCizek

Dynamicky alokovat mozes celu triedu:

new CPixel;
//alebo cele pole:
new CPixel[20];

Vector interne dynamicky alokuje pole prvkov.

Jinak děkuju, teď se mi to zase celé rozbilo, ale to je asi u programováni normální. :-)