De Fire Hovedkomponentene i STL

STL er bygget opp rundt fire sentrale komponenter som samhandler for å tilby en fleksibel og kraftfull måte å håndtere data på:

1. Containere: Dette er objekter som holder data. STL tilbyr forskjellige typer containere, hver med sine egne fordeler og ulemper basert på hvordan dataene er organisert og hvordan de kan aksesseres. Eksempler inkluderer vektorer, lister, mengder og kart.
2. Iteratorer: Iteratorer er generaliserte pekere som brukes til å traversere elementene i containere. De gir en enhetlig måte å få tilgang til elementer uavhengig av den underliggende containerens struktur.
3. Algoritmer: Algoritmer er funksjoner som opererer på containere via iteratorer. STL tilbyr et bredt spekter av algoritmer for sortering, søking, transformasjon og andre vanlige operasjoner.

4. Funksjonsobjekter (Functors): Funksjonsobjekter er objekter av klasser som har operator() overlastet. Dette gjør at de kan oppføre seg som funksjoner og brukes som argumenter til algoritmer, noe som gir fleksibel og tilpassbar oppførsel.

Containere i STL: Grunnleggende Datastrukturer

Containere er fundamentale for STL, da de er ansvarlige for lagring og organisering av data. STL tilbyr et rikt utvalg av containerklasser, som kan deles inn i flere kategorier basert på deres egenskaper og hvordan de tillater tilgang til elementene.

Sekvensielle Containere

Sekvensielle containere lagrer elementer i en lineær rekkefølge. Dette betyr at elementene har en spesifikk posisjon i containeren i forhold til andre elementer. STL tilbyr følgende sekvensielle containere:

std::vector

std::vector er en dynamisk array som kan vokse eller krympe i størrelse etter behov. Elementer i en vektor lagres i sammenhengende minneplasseringer, noe som gir rask tilgang til elementer ved hjelp av deres indeks (random access) i konstant tid, O(1). Å legge til eller fjerne elementer på slutten av en vektor er også effektivt, med en gjennomsnittlig tidskompleksitet på O(1). Imidlertid kan innsetting eller sletting av elementer i midten av en vektor være kostbart, da det krever at alle etterfølgende elementer flyttes, noe som resulterer i en tidskompleksitet på O(n), der n er antall elementer som må flyttes.

Viktige egenskaper ved std::vector:

• Rask tilgang til elementer ved indeks.
• Effektiv tilføyelse og fjerning av elementer på slutten.
• Potensielt kostbar innsetting og sletting i midten.
• Kan dynamisk endre størrelse.
• Lagrer elementer i sammenhengende minne.

Eksempel på bruk av std::vector:

#include 





#include 
int main() {
std::vector numbers;
numbers.push_back(10);
numbers.push_back(20);
numbers.push_back(30);
std::cout << "Element at index 1: " << numbers[1] << std::endl; // Output: Element at index 1: 20
numbers.insert(numbers.begin() + 1, 15); // Insert 15 at the second position
for (int num : numbers) {
std::cout << num << " "; // Output: 10 15 20 30
}
std::cout << std::endl;
numbers.pop_back(); // Remove the last element
std::cout << "Size of vector: " << numbers.size() << std::endl; // Output: Size of vector: 3
return 0;
}

std::deque

std::deque (double-ended queue) er en sekvensiell container som tillater effektiv innsetting og sletting av elementer i begge ender (begynnelsen og slutten) i amortisert konstant tid, O(1). I motsetning til `std::vector`, garanterer ikke `std::deque` at alle elementer lagres i sammenhengende minneplasseringer. Den er vanligvis implementert som en sekvens av separate segmenter av minne. Tilgang til elementer ved indeks er også mulig, men kan være litt tregere enn for `std::vector` (ikke garantert konstant tid, men vanligvis svært nærme). Innsetting eller sletting av elementer i midten av en `std::deque` er fortsatt kostbart, med en tidskompleksitet på O(n).

Viktige egenskaper ved std::deque:

• Effektiv innsetting og sletting i begge ender.
• Tilgang til elementer ved indeks (vanligvis nær konstant tid).
• Potensielt kostbar innsetting og sletting i midten.
• Kan dynamisk endre størrelse i begge ender.
• Lagrer elementer i potensielt ikke-sammenhengende minne.

Eksempel på bruk av std::deque:

#include 
#include 
int main() {
std::deque numbers;
numbers.push_back(20);
numbers.push_front(10);
numbers.push_back(30);
std::cout << "First element: " << numbers.front() << std::endl; // Output: First element: 10
std::cout << "Last element: " << numbers.back() << std::endl; // Output: Last element: 30
std::cout << "Element at index 1: " << numbers[1] << std::endl; // Output: Element at index 1: 20

numbers.insert(numbers.begin() + 1, 15); // Insert 15 at the second position
for (int num : numbers) {
std::cout << num << " "; // Output: 10 15 20 30
}
std::cout << std::endl;

numbers.pop_front(); // Remove the first element
numbers.pop_back(); // Remove the last element
std::cout << "Size of deque: " << numbers.size() << std::endl; // Output: Size of deque: 2
return 0;

}

std::list

std::list er en dobbeltlenket liste, der hvert element inneholder pekere til det forrige og det neste elementet i sekvensen. Dette gjør at innsetting og sletting av elementer hvor som helst i listen kan gjøres effektivt i konstant tid, O(1), forutsatt at du allerede har en iterator som peker på posisjonen. Imidlertid er tilgang til et element ved indeks ineffektivt, da det krever traversering av listen fra begynnelsen eller slutten, noe som resulterer i en lineær tidskompleksitet på O(n). I tillegg krever en lenket liste mer minne per element sammenlignet med en vektor eller deque på grunn av lagringen av pekere.

Viktige egenskaper ved std::list:

• Effektiv innsetting og sletting av elementer hvor som helst.

• Ineffektiv tilgang til elementer ved indeks.
• Iterering kan være tregere enn for vektorer på grunn av ikke-sammenhengende minne.
• Krever mer minne per element.

Eksempel på bruk av std::list:

#include 
#include 
int main() {
std::list numbers;
numbers.push_back(20);
numbers.push_front(10);
numbers.push_back(30);
std::cout << "First element: " << numbers.front() << std::endl; // Output: First element: 10
std::cout << "Last element: " << numbers.back() << std::endl; // Output: Last element: 30
auto it = numbers.begin();
std::advance(it, 1); // Move the iterator to the second element
numbers.insert(it, 15); // Insert 15 at the second position
for (int num : numbers) {
std::cout << num << " "; // Output: 10 15 20 30
}
std::cout << std::endl;
numbers.erase(numbers.begin()); // Remove the first element
numbers.pop_back(); // Remove the last element
std::cout << "Size of list: " << numbers.size() << std::endl; // Output: Size of list: 2
return 0;
}

std::forward_list

std::forward_list er en enkeltlenket liste, som i likhet med `std::list` tillater effektiv innsetting og sletting av elementer i konstant tid, O(1), forutsatt at du har en iterator til posisjonen *før* innsettingspunktet (for innsetting) eller til selve elementet (for sletting). Siden den bare holder en peker til det neste elementet, har den et lavere minneoverhead per element sammenlignet med `std::list`. Imidlertid tillater den bare traversering i én retning (fremover), og operasjoner som krever tilgang til det forrige elementet kan være mer kompliserte eller ineffektive.

Viktige egenskaper ved std::forward_list:

• Effektiv innsetting og sletting etter en gitt posisjon.
• Kun traversering fremover er mulig.
• Lavere minneoverhead enn `std::list`.
• Ineffektiv tilgang til elementer ved indeks.

Eksempel på bruk av std::forward_list:

#include 
#include 
int main() {
std::forward_list numbers;
numbers.push_front(30);
numbers.push_front(20);
numbers.push_front(10);
std::cout << "First element: " << numbers.front() << std::endl; // Output: First element: 10
auto it = numbers.begin();
numbers.insert_after(it, 15); // Insert 15 after the first element
for (int num : numbers) {
std::cout << num << " "; // Output: 10 15 20 30
}
std::cout << std::endl;
numbers.erase_after(numbers.before_begin()); // Remove the first element
std::cout << "Empty? " << numbers.empty() << std::endl; // Output: Empty? 0
return 0;
}

std::array (C++11)

std::array (introduksert i C++11) er en faststørrelse array som er en wrapper rundt en tradisjonell C-stil array. Størrelsen på en `std::array` må spesifiseres ved kompileringstidspunktet og kan ikke endres dynamisk. Den tilbyr direkte tilgang til elementene ved indeks i konstant tid, O(1), akkurat som en vanlig array. Fordelen med `std::array` over en ren C-stil array er at den er et objekt med metoder (som `size()`, `begin()`, `end()`) og er bedre integrert med resten av STL, for eksempel ved bruk av iteratorer og algoritmer.

Viktige egenskaper ved std::array:

• Fast størrelse bestemt ved kompileringstidspunktet.
• Rask tilgang til elementer ved indeks.
• Effektiv iterering.
• Ingen overhead for dynamisk allokering eller deallokering.

Eksempel på bruk av std::array:

#include 
#include 
int main() {
std::array numbers = {10, 20, 30};
std::cout