Min kod tar för lång tid på sig, evig loop eller allmänt dålig programmering? (C++)

Ditt största problem här är nog att du allokera och frigör minne alldeles för ofta.

Låt det allokerade antalet element skilja sig från antalet sparade element i vektorn och använd sedan någon form av expontentiell tillväxt. D.v.s. du har "capacity" och "size", och när "size > capacity" så låter du "capacity = size * 2".

1. Du har glömt att kopiera över capacity i likamed-operatorn när du växer vektorn.
2. Din erase funktion gör inget vettigt.
3. Du bör placera koden för att växa vektorn i en egen funktion och även överväga krympningar (säg... när "size < capacity / 4").

ps. Att Kattis inte ger dig testen är rimligt då du inom "riktig" mjukvaru-utveckling sällan har möjlighet att i förväg få alla möjliga inputs som dina användare kommer att ge.

Det gör förmodligen inte någon jätteskillnad, men memcpy är vanligtvis effektivare än att kopiera varje element när man vill kopiera ett fält. Och är det verkligen meningen att använda bubble sort för sort-funktionen?

Memcpy fungerar nog lite mindre bra. Tänk på att T kan vara något annat än Plain-Old-Data.

För att vara riktigt strikt med att duplicera beteendet hos STL's vector-klass bör man allokera minnet med en allokator som inte involverar default-konstruktorn. Sköt sedan om destruktioner genom att manuellt anropa destruktorn för varje element, och kopieringar med placement new. Lättast görs detta om man använder STL's allocator-klass.

Dock är detta rejält överkurs och inget som krävs för denna labb.

Weeblie: Memcpy och memmove måste ju fungera så länge inte containern måste bibehålla giltigheten i externa referenser.

Om syftet är att implementera om std::vector så måste destruktorn anropa elementens destruktorer för att undvika minnesläckor.

Något du också bör göra är att testa dina egna funktioner så att du ser att de verkligen ger rätt resultat, inte bara kör utan att krascha. Att Size och Capacity alltid har "rätt" värden t ex.

Du kan också implementera din insert så att den tar size - index operationer istället för size * 2. Detta kommer funka varje gång du inte behöva allokera om din vektor för att rymma ett nytt element. Du behöver bara flytta de element som ligger efter positionen du sätter in i.

Byt ut bubblesorten mot en riktigt sortering. Om de inte uttryckligen förbjudit stl::sort, så använd den, annars skulle jag rekommendera någon enklare nlogn-sortering annan än quicksort. Detta för att t ex heapsort är enklare att förstå än de varianter av quicksort som inte har n² som värsta fall. Tänk på att den som testar kan implementera T lite hur han vill, antingen genom att göra den jävlig att byta plats på (mycket data) eller genom att göra jämförelserna dyra (dyr operator==()).

Därav min kommentar om "plain old data". POD hänvisar just till strukturer där alla fälten också är POD och kopieras rakt av.

Typiska exempel på sådant som inte är POD är STL's strängar, vektor-klassen själv, o.s.v.

Tumregeln är att om en klass täcks av "rule of three" (har en icke auto-generad copy-konstruktor, copy-tilldelning eller destruktor) så är den inte POD.

Det görs implicit av delete[].

Du är nästan framme nu!

Kika på fixCapacity. Kan du hitta det logiska felet på raden med copy_between_vec?

Testa annars på din egen dator:

vector<int> v1(1000);
vector<int> v2;

v1 = v2;

Det finns dessutom ett litet fel med tänket för erase.

Pröva med att skapa en vector med talen 0 till 9. Ta sedan bort ett av dem i mitten och skriv ut innehållet igen. Vad händer?

Okay... problemet är att du (ibland) förändrar vSize innan du anropar fixCapacity.

Försök att skissa upp på papper och penna över vad som då händer.

Jag föreslår att du försöker vara lite mer konsekevent här och följer något i stil med...

Vid tillväxt:

1. Anropar fixCapacity.
2. Stoppar in element/möblerar om.
3. Sätter vSize.

Vid krympning:

1. Tar bort element/möblerar om.
3. Sätter vSize.
3. Anropar fixCapacity.

Ah, läste lite slarvigt där.

Ang. POD så krävs det bra mycket mer än så för att en datastruktur inte ska kunna flyttas. Strukturen måste ju isåfall veta var den låg från början, något som jag inte kan se hindras av rule of three. ska se om jag giter testa att flytta på STL-datastrukturer med våld någon dag. Pekare till heap-allokerad data behöver ju inte veta var de ligger.

Självklart behöver inte ett objekt vara POD för att vara flyttbart med memcpy/memmove; men jag tror att du har underskattat kraven här.

Ta t.ex. sträng-objekt. Kan du garantera att det internt allokerade minnet inte frigörs flera gånger?

Får man verkligen krympa vektorn? Jag trodde att ifall man anropar reserve() och sen inte går över den storleken så är man garanterad att elementen inte flyttar på sig (förutom de som kommer efter element man gör erase() på såklart).

Jag är uppriktigt nyfiken på hur det skulle kunna gå till, förutsatt att man inte sitter i ett system med garbage collecting. Det krävs ju att det någonstans finns information om att objektet flyttats, och att denna information skulle kunna leda till att minnet i andra ändan av pekarna skulle frigöras flera gånger.

[QUOTE=Milky Way;10405812]Får man verkligen krympa vektorn? Jag trodde att ifall man anropar reserve() och sen inte går över den storleken så är man garanterad att elementen inte flyttar på sig (förutom de som kommer efter element man gör erase() på såklart).[/QUOTE]

Du har rätt i att standarden egentligen förbjuder en från att krympa vektorn när man tar bort element från den. Inte ens ett clear-anrop skall frigöra minne.

Det är inte nödvändigt att anropa reserve för att få detta beteende.

Sköt om konstruktion och destruktion manuellt.

#include <cstdlib>
#include <memory>
#include <iostream>
using namespace std;

class Foobar
{
public:
	// Märk att vi inte har någon default-konstruktor.
	Foobar(int x)
		: x(x)
	{

	}

	Foobar(const Foobar& other)
		: x(other.x)
	{

	}

	Foobar& operator=(const Foobar& other)
	{
		x = other.x;
	}

	~Foobar()
	{
		x = 0;
	}

public:
	int x;
};

int main()
{
	Foobar obj1(1);
	Foobar obj2(2);
	size_t capacity = 100;
	Foobar* v = nullptr;
	
	// Placement new + Destruktor.
	v = static_cast<Foobar*>(malloc(sizeof(Foobar) * capacity));

	cout << "Metod 1:" << endl;
	cout << v[0].x << " " << v[1].x << endl;

	new (&v[0]) Foobar (obj1);
	new (&v[1]) Foobar (obj2);

	cout << v[0].x << " " << v[1].x << endl;

	v[1].~Foobar();
	v[0].~Foobar();

	cout << v[0].x << " " << v[1].x << endl;

	free(v);

	// Enklare och bättre alternativ med std::allocator.
	allocator<Foobar> alloc;

	v = alloc.allocate(capacity);

	cout << endl << "Metod 2:" << endl;
	cout << v[0].x << " " << v[1].x << endl;

	alloc.construct(&v[0], obj1);
	alloc.construct(&v[1], obj2);

	cout << v[0].x << " " << v[1].x << endl;

	alloc.destroy(&v[1]);
	alloc.destroy(&v[0]);

	cout << v[0].x << " " << v[1].x << endl;

	alloc.deallocate(v, capacity);
}

Det är svårt att säga exakt varför standarden är som den är; men ett troligt svar är att man inte vill göra "vector" onödigt komplicerad bara för att kunna stödja "reserve". D.v.s. emulera klassiskt "array + räknare"-beteende.