vector vs. lijst in STL

Ik merkte in Effectieve STL dat

vector is het type rij dat
moet standaard worden gebruikt.

Wat betekent het? Het lijkt erop dat het negeren van de efficiëntie vectoralles kan doen.

Kan iemand mij een scenario aanbieden waarin vectorgeen haalbare optie is, maar listmoet worden gebruikt?

Antwoord 1, autoriteit 100%

Situaties waarin u herhaaldelijk veel items wilt invoegen, behalve aan het einde van een reeks.

Bekijk de complexiteitsgaranties voor elk verschillend type container:

Wat zijn de complexiteitsgaranties van de standaard containers?

Antwoord 2, autoriteit 99%

vector:

• Aaneengesloten geheugen.
• Wijst vooraf ruimte toe voor toekomstige elementen, dus er is extra ruimte nodig die verder gaat dan nodig is voor de elementen zelf.
• Elk element heeft alleen de ruimte nodig voor het elementtype zelf (geen extra verwijzingen).
• Kan geheugen voor de hele vector opnieuw toewijzen wanneer u een element toevoegt.
• Invoegingen aan het einde zijn constant, afgeschreven tijd, maar invoegingen elders zijn een kostbare O(n).
• Wissen aan het einde van de vector zijn constante tijd, maar voor de rest is het O(n).
• Je hebt willekeurig toegang tot de elementen.
• Iterators worden ongeldig als u elementen toevoegt aan of verwijdert uit de vector.
• Je kunt gemakkelijk bij de onderliggende array komen als je een array van de elementen nodig hebt.

lijst:

• Niet-aangrenzend geheugen.
• Geen vooraf toegewezen geheugen. De geheugenoverhead voor de lijst zelf is constant.
• Elk element vereist extra ruimte voor het knooppunt dat het element bevat, inclusief verwijzingen naar de volgende en vorige elementen in de lijst.
• Je hoeft nooit geheugen voor de hele lijst opnieuw toe te wijzen, alleen maar omdat je een element toevoegt.
• Invoegingen en verwijderingen zijn goedkoop, ongeacht waar ze in de lijst voorkomen.
• Het is goedkoop om lijsten te combineren met splitsen.
• Je kunt niet willekeurig toegang krijgen tot elementen, dus het kan duur zijn om bij een bepaald element in de lijst te komen.
• Iterators blijven geldig, zelfs wanneer u elementen toevoegt aan of verwijdert uit de lijst.
• Als je een array van de elementen nodig hebt, moet je een nieuwe maken en ze er allemaal aan toevoegen, aangezien er geen onderliggende array is.

Gebruik in het algemeen vector als het u niet uitmaakt welk type sequentiële container u gebruikt, maar als u veel invoegingen of verwijderingen uitvoert van en naar elke andere plaats in de container dan het einde, lijst wilt gebruiken. Of als je willekeurige toegang nodig hebt, dan wil je vector, geen lijst. Afgezien daarvan zijn er natuurlijk gevallen waarin je het een of het ander nodig hebt op basis van je toepassing, maar over het algemeen zijn dit goede richtlijnen.

Antwoord 3, autoriteit 35%

Als u niet vaak elementen hoeft in te voegen, is een vector efficiënter. Het heeft een veel betere CPU-cachelocatie dan een lijst. Met andere woorden, toegang tot een element maakt het zeerwaarschijnlijk dat het volgende element in de cache aanwezig is en kan worden opgehaald zonder langzame RAM te hoeven lezen.

4, Autoriteit 17%

One Special Capability of Std :: List is splitsen (koppelen of verplaatsen van een deel van of een hele lijst in een andere lijst).

of misschien als uw inhoud erg duur is om te kopiëren. In een dergelijk geval kan het bijvoorbeeld goedkoper zijn om de collectie met een lijst te sorteren.

Houd er ook rekening mee dat als de collectie klein is (en de inhoud niet bijzonder duur is om te kopiëren), een vector mogelijk nog steeds beter dan een lijst, zelfs als u ergens inzet en ergens wist. Een lijst wijst elk knooppunt individueel toe, en dat kan veel duurder zijn dan het verplaatsen van een paar eenvoudige objecten in de buurt.

Ik denk niet dat er erg harde regels zijn. Het hangt af van wat u meestal met de container wilt doen, maar ook van hoe groot u verwacht dat de container zal zijn en het type ingesloten. Een vector overtroeft over het algemeen een lijst, omdat het de inhoud ervan toewijst als een enkel aaneengesloten blok (het is in feite een dynamisch toegewezen array, en in de meeste gevallen is een array de meest efficiënte manier om een heleboel dingen vast te houden).

Antwoord 5, autoriteit 12%

Nou, de leerlingen van mijn klas lijken me niet in staat uit te leggen wanneer het effectiever is om vectoren te gebruiken, maar ze kijken best tevreden als ze me adviseren om lijsten te gebruiken.

Zo begrijp ik het

Lijsten:
Elk item bevat een adres naar het volgende of vorige element, dus met deze functie kun je de items willekeurig rangschikken, zelfs als ze niet zijn gesorteerd, verandert de volgorde niet: het is efficiënt als je geheugen gefragmenteerd is.
Maar het heeft ook nog een heel groot voordeel: je kunt er gemakkelijk items invoegen/verwijderen, want het enige wat je hoeft te doen is enkele pointers veranderen.
Nadeel:
Om een willekeurig afzonderlijk item te lezen, moet je van het ene item naar het andere springen totdat je het juiste adres vindt.

Vectoren:
Bij het gebruik van vectoren is het geheugen veel meer georganiseerd als gewone arrays: elk n-de item wordt opgeslagen net na het (n-1)de item en vóór (n+1)de item.
Waarom is het beter dan een lijst?
Omdat het snelle willekeurige toegang mogelijk maakt.
Hier is hoe: als je de grootte van een item in een vector weet, en als ze aaneengesloten zijn in het geheugen, kun je gemakkelijk voorspellen waar het n-de item is; je hoeft niet door alle items van een lijst te bladeren om degene te lezen die je wilt, met vector lees je het direct, met een lijst die je niet kunt.
Aan de andere kant gaat het wijzigen van de vectorarray of het wijzigen van een waarde veel langzamer.

Lijsten zijn geschikter om objecten bij te houden die in het geheugen kunnen worden toegevoegd/verwijderd.
Vectoren zijn geschikter wanneer u toegang wilt tot een element uit een grote hoeveelheid afzonderlijke items.

Ik weet niet hoe lijsten zijn geoptimaliseerd, maar je moet weten dat als je snelle leestoegang wilt, je vectoren moet gebruiken, want hoe goed de STL-lijsten ook zijn, het zal niet zo snel zijn in leestoegang dan vector.

Antwoord 6, autoriteit 11%

Maak het eenvoudig-
Aan het eind van de dag, als je in de war bent met het kiezen van containers in C++, gebruik dan deze stroomdiagramafbeelding (bedank mij):-

Vector-

1. vector is gebaseerd op besmettelijk geheugen
2. vector is de beste keuze voor een kleine dataset
3. vector presteert het snelst tijdens verplaatsingen op dataset
4. verwijdering van vector-invoegingen is traag op een enorme dataset, maar snel voor zeer
   klein

Lijst-

1. lijst is gebaseerd op heap-geheugen
2. lijst is een goede keuze voor een zeer grote dataset
3. lijst is relatief traag bij het doorlopen van een kleine dataset, maar snel bij
   enorme dataset
4. Het verwijderen van lijst-invoegingen gaat snel bij grote datasets, maar langzaam bij kleinere
   degenen

Antwoord 7, autoriteit 9%

Elke keer dat je iterators niet ongeldig kunt maken.

Antwoord 8, autoriteit 9%

Een vector is in feite een array met automatisch geheugenbeheer. De gegevens zijn aaneengesloten in het geheugen. Proberen om gegevens in het midden in te voegen is een kostbare operatie.

In een lijst worden de gegevens opgeslagen op niet-gerelateerde geheugenlocaties. Invoegen in het midden houdt niet in dat je een deel van de gegevens moet kopiëren om ruimte te maken voor de nieuwe.

Om uw vraag specifieker te beantwoorden, citeer ik deze pagina

vectoren zijn over het algemeen het meest efficiënt in tijd om toegang te krijgen tot elementen en om elementen aan het einde van de reeks toe te voegen of te verwijderen. Voor bewerkingen waarbij elementen worden ingevoegd of verwijderd op andere posities dan het einde, presteren ze slechter dan deques en lijsten, en hebben ze minder consistente iterators en referenties dan lijsten.

Antwoord 9, autoriteit 7%

Als je veel invoegingen of verwijderingen hebt in het midden van de reeks. bijv. een geheugenbeheerder.

Antwoord 10, autoriteit 4%

Het behouden van de geldigheid van iterators is een reden om een lijst te gebruiken. Een andere is wanneer u niet wilt dat een vector opnieuw wordt toegewezen bij het pushen van items. Dit kan worden beheerd door een intelligent gebruik van reserve(), maar in sommige gevallen kan het eenvoudiger of haalbaarder zijn om gewoon een lijst te gebruiken.

Antwoord 11, autoriteit 4%

Als u objecten tussen containers wilt verplaatsen, kunt u list::splicegebruiken.

Een algoritme voor het partitioneren van grafieken kan bijvoorbeeld een constant aantal objecten recursief verdelen over een toenemend aantal containers. De objecten moeten één keer worden geïnitialiseerd en altijd op dezelfde locaties in het geheugen blijven. Het is veel sneller om ze te herschikken door ze opnieuw te koppelen dan door ze opnieuw toe te wijzen.

Bewerken:terwijl bibliotheken zich voorbereiden op de implementatie van C++0x, wordt het algemene geval van het splitsen van een subreeks in een lijst lineaire complexiteit met de lengte van de reeks. Dit komt omdat splice(nu) de reeks moet herhalen om het aantal elementen erin te tellen. (Omdat de lijst zijn grootte moet registreren.) Gewoon tellen en opnieuw koppelen van de lijst is nog steeds sneller dan welk alternatief dan ook, en het splitsen van een hele lijst of een enkel element zijn speciale gevallen met constante complexiteit. Maar als je lange reeksen moet splitsen, moet je misschien graven naar een betere, ouderwetse, niet-conforme container.

Antwoord 12, autoriteit 4%

In het geval van een vectoren lijstzijn de belangrijkste verschillen die mij opvallen de volgende:

vector

• Een vector slaat zijn elementen op in een aaneengesloten geheugen. Daarom, willekeurig
  toegang is mogelijk binnen een vector, wat betekent dat toegang tot een
  element van een vector is erg snel omdat we de . eenvoudig kunnen vermenigvuldigen
  basisadres met de itemindex om toegang te krijgen tot dat element. In feite is het
  neemt hiervoor alleen O(1) of constante tijd in beslag.

• Omdat een vector in feite een array omhult, zal elke keer dat u een . invoegt,
  element in de vector (dynamische array), moet het zichzelf verkleinen door
  een nieuw aaneengesloten geheugenblok vinden om het nieuwe te accommoderen
  elementen die tijdrovend zijn.

• Het verbruikt geen extra geheugen om verwijzingen naar andere op te slaan
  elementen erin.

lijst

• Een lijst slaat zijn elementen op in niet-aangrenzend geheugen. Daarom,
  willekeurige toegang is niet mogelijk binnen een lijst, wat betekent dat
  toegang krijgen tot de elementen, we moeten de aanwijzers gebruiken en doorkruisen
  de lijst die langzamer is ten opzichte van vector. Dit kost O(n) of lineaire tijd, wat is
  langzamer dan O(1).

• Aangezien een lijst niet-aangrenzend geheugen gebruikt, is de tijd die nodig is om een
  element in een lijst is veel efficiënter dan in het geval van zijn
  vector tegenhanger omdat hertoewijzing van geheugen wordt vermeden.

• Het verbruikt extra geheugen om pointers op te slaan naar het element ervoor en
  na een bepaald element.

Dus, rekening houdend met deze verschillen, overwegen we meestal geheugen, frequente willekeurige toegangen invoegingom de winnaar van te bepalen vector versus lijstin een bepaald scenario.

Antwoord 13, autoriteit 3%

De enige harde regel waar listmoet worden gebruikt, is waar je verwijzingen naar elementen van de container moet distribueren.

In tegenstelling tot vectorweet je dat het geheugen van elementen niet opnieuw wordt toegewezen. Als het zou kunnen, heb je misschien verwijzingen naar ongebruikt geheugen, wat op zijn best een grote nee-nee is en in het slechtste geval een SEGFAULT.

(Technisch gezien zou een vectorvan *_ptrook werken, maar in dat geval emuleer je list, dus dat is slechts semantiek.)

Andere zachte regels hebben te maken met de mogelijke prestatieproblemen van het invoegen van elementen in het midden van een container, waarna listde voorkeur zou hebben.

Antwoord 14

Lijsten zijn slechts een wrapper voor een dubbel-LinkedList in stl, en bieden dus functies die u van d-linklist mag verwachten, namelijk O(1) invoegen en verwijderen.
Terwijl vectoren besmettelijke gegevensreeksen zijn die werken als een dynamische array.P.S- gemakkelijker te doorkruisen.

Antwoord 15

De antwoorden samenvatten in een tabel voor snelle referentie: