CShift-Algorithmus inplace?

Fytch

Hallo.

Man denke sich einen CShift -Algorithmus auf einer Random-Access-Datenstruktur. Dieser verhält sich genau so wie std::valarray::cshift . Im Folgenden steht $s$ für die Grösse der ganzen Sequenz und $n$ für den Verschiebungsoffset. Die Bezeichner in meinen Codebeispielen dürften sich selbst erklären (alles analog zur STL).
Die Mod -Funktion ist ein Modulo, bei dem das Resultat immer zwischen 0 und dem Divisor ist (z.B. Mod(-1, 5) == 4 oder Mod(3, -2) == -1 ). Der Standard- % -Operator ist für negative Werte ja impementation-defined.

Eine naheliegende und naive Implementierung (die jedoch einen zusätzlichen Speicherplatzverbrauch in $\mathcal{O}(s)$ hat):

void CShift(DiffType n)
{
	n = Mod<DiffType>(n, this->Size);
	if(n != 0)
	{
		ValArray New;
		for(SizeType i = 0; i < this->Size; ++i)
		{
			New[i] = (*this)[(i + n) % this->Size];
		}
		*this = New;
	}
}

Diese Version kommt mit konstantem zusätzlichem Speicherplatz aus (hat jedoch einen grossen von $n$ abhängigen Laufzeitoverhead):

void CShift(DiffType n)
{
	n = Mod<DiffType>(n, this->Size);
	while(n-- != 0)
	{
		ValueType Last = this->Back();
		for(SizeType i = this->Size - 1; i != 0; --i)
		{
			(*this)[i] = (*this)[i - 1];
		}
		this->Front() = Last;
	}
}

Gibt es eine Lösung für dieses Problem, die inplace und effizient arbeitet?

Gruss.

volkard

asfdlol schrieb:

Gibt es eine Lösung für dieses Problem, die inplace und effizient arbeitet?

Ja. Reicht Dir http://www.cplusplus.com/reference/algorithm/rotate/ ?

Fytch

volkard schrieb:

Ja. Reicht Dir http://www.cplusplus.com/reference/algorithm/rotate/ ?

Huch, std::rotate kannte ich gar nicht. So etwas ähnliches habe ich auf Papier versucht aber es stimmte leider nicht ganz. Ja, reicht mir selbstverständlich, danke.

Gruss.