C++
iteratorer

C Iteratorer (pekare)

// This creates an array with 5 values.
const int array[] = { 1, 2, 3, 4, 5 };

#ifdef BEFORE_CPP11

// You can use `sizeof` to determine how many elements are in an array.
const int* first = array;
const int* afterLast = first + sizeof(array) / sizeof(array[0]);

// Then you can iterate over the array by incrementing a pointer until
// it reaches past the end of our array.
for (const int* i = first; i < afterLast; ++i) {
    std::cout << *i << std::endl;
}

#else

// With C++11, you can let the STL compute the start and end iterators:
for (auto i = std::begin(array); i != std::end(array); ++i) {
    std::cout << *i << std::endl;
}

#endif

Denna kod skulle mata ut siffrorna 1 till 5, en på varje rad som denna:

1
2
3
4
5

Breaking It Down

const int array[] = { 1, 2, 3, 4, 5 };

Den här raden skapar en ny heltalarray med 5 värden. C-matriser är bara pekare på minnet där varje värde lagras tillsammans i ett sammanhängande block.

const int* first = array;
const int* afterLast = first + sizeof(array) / sizeof(array[0]);

Dessa rader skapar två pekare. Den första pekaren ges värdet på matrispekaren, som är adressen till det första elementet i matrisen. sizeof när den används på en C-array returnerar storleken på matrisen i byte. Dividerat med storleken på ett element ger detta antalet element i matrisen. Vi kan använda detta för att hitta adressen till blocket efter matrisen.

for (const int* i = first; i < afterLast; ++i) {

Här skapar vi en pekare som vi kommer att använda som en iterator. Det initialiseras med adressen till det första elementet vi vill iterera över, och vi fortsätter att iterera så länge i är mindre än afterLast , vilket betyder så länge i pekar på en adress inom array .

    std::cout << *i << std::endl;

Slutligen kan vi få tillgång till värdet som vår iterator i pekar på genom att återföra det. Här returnerar dereferenceoperatören * värdet på adressen i i .

Översikt

Iteratorer är positioner

Iteratorer är ett sätt att navigera och arbeta på en sekvens av element och är en general förlängning av pekare. Konceptuellt är det viktigt att komma ihåg att iteratorer är positioner, inte element. Ta till exempel följande sekvens:

A B C

Sekvensen innehåller tre element och fyra positioner

+---+---+---+---+
| A | B | C |   |
+---+---+---+---+

Element är saker inom en sekvens. Positioner är platser där meningsfulla operationer kan hända sekvensen. Till exempel sätter man in en position, före eller efter element A, inte i ett element. Även radering av ett element ( erase(A) ) görs genom att först hitta sin position och sedan ta bort det.

Från Iteratorer till värderingar

För att konvertera från en position till ett värde är en iterator avskedad :

auto my_iterator = my_vector.begin(); // position
auto my_value = *my_iterator; // value

Man kan tänka på en iterator som en återgång till värdet den hänvisar till i sekvensen. Detta är särskilt användbart för att förstå varför du aldrig ska återvända end() iteratorn i en sekvens:

+---+---+---+---+
| A | B | C |   |
+---+---+---+---+
  ↑           ↑
  |           +-- An iterator here has no value. Do not dereference it!
  +-------------- An iterator here dereferences to the value A.

I alla sekvenser och behållare som finns i C ++ standardbiblioteket, begin() återställa en iterator till den första positionen och end() kommer att returnera en iterator till en förbi den sista positionen ( inte den sista positionen!). Följaktligen är namnen på dessa iteratorer i algoritmer ofta märkta first och last :

+---+---+---+---+
| A | B | C |   |
+---+---+---+---+
  ↑           ↑
  |           |
  +- first    +- last

Det är också möjligt att erhålla en iterator till vilken sekvens som helst , eftersom även en tom sekvens innehåller minst en position:

+---+
|   |
+---+

I en tom sekvens kommer begin() och end() att vara samma position, och ingen av dessa kan avvikas:

+---+
|   |
+---+
  ↑
  |
  +- empty_sequence.begin()
  |
  +- empty_sequence.end()

Den alternativa visualiseringen av iteratorer är att de markerar positionerna mellan element:

+---+---+---+
| A | B | C |
+---+---+---+
↑   ^   ^   ↑
|           |
+- first    +- last

och dereferencing en iterator returnerar en referens till elementet som kommer efter iteratorn. Vissa situationer där denna vy är särskilt användbar är:

• insert operationer kommer att sätta in element i det läge som indikeras av iteratorn,
• erase operationer kommer att returnera en iterator som motsvarar samma position som den som passeras in,
• en iterator och motsvarande omvänd iterator är belägna i samma position mellan elementen

Ogiltiga Iteratorer

En iterator blir ogiltig om (säg, under en operation) dess position inte längre är en del av en sekvens. En ogiltig iterator kan inte avskaffas förrän den har tilldelats till en giltig position. Till exempel:

std::vector<int>::iterator first;
{
    std::vector<int> foo;
    first = foo.begin(); // first is now valid
} // foo falls out of scope and is destroyed
// At this point first is now invalid

De många algoritmerna och sekvensmedlemfunktionerna i C ++ -biblioteket har regler som reglerar när iteratorer är ogiltiga. Varje algoritm är annorlunda på det sätt som de behandlar (och ogiltiga) iteratorer.

Navigera med Iterators

Som vi vet är iteratorer för att navigera i sekvenser. För att göra det måste en iterator migrera sin position genom hela sekvensen. Iteratorer kan gå framåt i sekvensen och vissa kan gå bakåt:

auto first = my_vector.begin();
++first;                                             // advance the iterator 1 position
std::advance(first, 1);                              // advance the iterator 1 position
first = std::next(first);                            // returns iterator to the next element
std::advance(first, -1);                             // advance the iterator 1 position backwards
first = std::next(first, 20);                        // returns iterator to the element 20 position forward
first = std::prev(first, 5);                         // returns iterator to the element 5 position backward
auto dist = std::distance(my_vector.begin(), first); // returns distance between two iterators.

Observera att det andra argumentet om std :: avstånd bör vara tillgängligt från det första (eller med andra ord bör det first vara mindre eller lika mycket som det second ).

Även om du kan utföra aritmetiska operatörer med iteratorer, definieras inte alla operationer för alla typer av iteratorer. a = b + 3; skulle fungera för Iteratorer med slumpmässig åtkomst, men skulle inte fungera för Iteratorer för framåt eller i två riktningar, som fortfarande kan avanceras med 3 positioner med något som b = a; ++b; ++b; ++b; . Så det rekommenderas att du använder specialfunktioner om du inte är säker på vilken typ av iteratorn (till exempel i en mallfunktion som accepterar iterator).

Iteratorbegrepp

C ++ -standarden beskriver flera olika iteratorkoncept. Dessa grupperas efter hur de beter sig i sekvenserna de refererar till. Om du känner till konceptet som en iterator modellerar (uppför sig som) kan du vara säker på beteendet hos den iteratorn oavsett vilken sekvens den tillhör . De beskrivs ofta i ordning från det mest till minst begränsande (eftersom nästa iterator-koncept är ett steg bättre än föregångaren):

• Inputteratorer: Kan endast avlägsnas en gång per position. Kan bara gå framåt, och bara en position åt gången.
• Framåt-Iteratorer: En inmatnings-iterator som kan avhjälpas valfritt antal gånger.
• Dubbelriktad Iteratorer: en framåt iterator som också kan gå bakåt en position i taget.
• Random Access Iterators: En dubbelriktad iterator som kan avancera framåt eller bakåt valfritt antal positioner åt gången.
• Contiguous Iterators (sedan C ++ 17): En iterator med slumpmässig åtkomst som garanterar att underliggande data är sammanhängande i minnet.

Algoritmer kan variera beroende på konceptet som modelleras av iteratorerna de ges. Även om random_shuffle kan implementeras för framåt-iteratorer, kan en mer effektiv variant som kräver iteratorer med slumpmässig åtkomst tillhandahållas.

Iterator drag

Iteratoregenskaper ger ett enhetligt gränssnitt till iterators egenskaper. De låter dig hämta värde, skillnad, pekare, referenstyper och även kategori av iterator:

template<class Iter>
Iter find(Iter first, Iter last, typename std::iterator_traits<Iter>::value_type val)  {
    while (first != last) {
        if (*first == val)
            return first;
        ++first;
    }
    return last;
}

Kategori av iterator kan användas för att specialisera algoritmer:

template<class BidirIt>
void test(BidirIt a, std::bidirectional_iterator_tag)  {
    std::cout << "Bidirectional iterator is used" << std::endl;
}
 
template<class ForwIt>
void test(ForwIt a, std::forward_iterator_tag)  {
    std::cout << "Forward iterator is used" << std::endl;
}
 
template<class Iter>
void test(Iter a)  {
    test(a, typename std::iterator_traits<Iter>::iterator_category());
}

Kategorier av iteratorer är i grund och botten iteratorkoncept, utom Contiguous Iteratorer har inte sin egen tagg, eftersom det visade sig att den bryter kod.

Reversterteratorer

Om vi vill iterera bakåt genom en lista eller vektor kan vi använda en reverse_iterator . En omvänd iterator är gjord av en dubbelriktad iterator eller slumpmässig åtkomst som den håller som ett medlem som kan nås via base() .

För att iterera bakåt använder rbegin() och rend() som iteratorer för slutet av samlingen, respektive början av samlingen.

För att iterera bakåt använder du till exempel:

std::vector<int> v{1, 2, 3, 4, 5};
for (std::vector<int>::reverse_iterator it = v.rbegin(); it != v.rend(); ++it)
{
    cout << *it;
} // prints 54321

En omvänd iterator kan konverteras till en framåt iterator via basfunktionen base() . Förhållandet är att den omvända iteratorn refererar till ett element förbi base() iteratorn:

std::vector<int>::reverse_iterator r = v.rbegin();
std::vector<int>::iterator i = r.base();
assert(&*r == &*(i-1)); // always true if r, (i-1) are dereferenceable
                        // and are not proxy iterators

 +---+---+---+---+---+---+---+
 |   | 1 | 2 | 3 | 4 | 5 |   |
 +---+---+---+---+---+---+---+
   ↑   ↑               ↑   ↑
   |   |               |   |
rend() |         rbegin()  end()
       |                   rbegin().base()
     begin()
     rend().base()

I visualiseringen där iteratorerna markerar positioner mellan element är förhållandet enklare:

  +---+---+---+---+---+
  | 1 | 2 | 3 | 4 | 5 |
  +---+---+---+---+---+
  ↑                   ↑
  |                   |
  |                 end()
  |                 rbegin()
begin()             rbegin().base()
rend()
rend().base()

Vector Iterator

begin returnerar en iterator till det första elementet i sekvensbehållaren.

end returnerar en iterator till det första elementet förbi slutet.

Om vektorobjektet är const , returnerar både begin och end en const_iterator . Om du vill att en const_iterator ska returneras även om din vektor inte är const , kan du använda cbegin och cend .

Exempel:

#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = { 1, 2, 3, 4, 5 };  //intialize vector using an initializer_list

    for (std::vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
        std::cout << *it << " ";
    }

    return 0;
}

Produktion:

1 2 3 4 5

Karta Iterator

En iterator till det första elementet i behållaren.

Om ett kartobjekt är konst-kvalificerat, returnerar funktionen en const_iterator . Annars returnerar det en iterator .

// Create a map and insert some values
std::map<char,int> mymap;
mymap['b'] = 100;
mymap['a'] = 200;
mymap['c'] = 300;

// Iterate over all tuples
for (std::map<char,int>::iterator it = mymap.begin(); it != mymap.end(); ++it)
    std::cout << it->first << " => " << it->second << '\n';

Produktion:

a => 200
b => 100
c => 300

Stream Iterators

Stream iteratorer är användbara när vi behöver läsa en sekvens eller skriva ut formaterad data från en behållare:

// Data stream. Any number of various whitespace characters will be OK.
std::istringstream istr("1\t 2     3 4");
std::vector<int> v;

// Constructing stream iterators and copying data from stream into vector.
std::copy(
    // Iterator which will read stream data as integers.
    std::istream_iterator<int>(istr),
    // Default constructor produces end-of-stream iterator.
    std::istream_iterator<int>(),
    std::back_inserter(v));

// Print vector contents.
std::copy(v.begin(), v.end(),
    //Will print values to standard output as integers delimeted by " -- ".
    std::ostream_iterator<int>(std::cout, " -- "));

Exempelprogrammet kommer att skriva ut 1 -- 2 -- 3 -- 4 -- till standardutdata.

Skriv din egen iterator med stöd av generator

Ett vanligt mönster på andra språk är att ha en funktion som producerar en "ström" av objekt och att kunna använda loopkod för att slinga över den.

Vi kan modellera detta i C ++ som

template<class T>
struct generator_iterator {
  using difference_type=std::ptrdiff_t;
  using value_type=T;
  using pointer=T*;
  using reference=T;
  using iterator_category=std::input_iterator_tag;
  std::optional<T> state;
  std::function< std::optional<T>() > operation;
  // we store the current element in "state" if we have one:
  T operator*() const {
    return *state;
  }
  // to advance, we invoke our operation.  If it returns a nullopt
  // we have reached the end:
  generator_iterator& operator++() {
    state = operation();
    return *this;        
  }
  generator_iterator operator++(int) {
    auto r = *this;
    ++(*this);
    return r;
  }
  // generator iterators are only equal if they are both in the "end" state:
  friend bool operator==( generator_iterator const& lhs, generator_iterator const& rhs ) {
    if (!lhs.state && !rhs.state) return true;
    return false;
  }
  friend bool operator!=( generator_iterator const& lhs, generator_iterator const& rhs ) {
    return !(lhs==rhs);
  }
  // We implicitly construct from a std::function with the right signature:
  generator_iterator( std::function< std::optional<T>() > f ):operation(std::move(f))
  {
    if (operation)
      state = operation();
  }
  // default all special member functions:
  generator_iterator( generator_iterator && ) =default;
  generator_iterator( generator_iterator const& ) =default;
  generator_iterator& operator=( generator_iterator && ) =default;
  generator_iterator& operator=( generator_iterator const& ) =default;
  generator_iterator() =default;
};

levande exempel .

Vi lagrar det genererade elementet tidigt så att vi lättare kan upptäcka om vi redan är i slutet.

Eftersom funktionen för en slutgenerator-iterator aldrig används, kan vi skapa en rad generator-iteratorer genom att bara kopiera std::function gång. En standardkonstruerad generator-iterator jämförs lika med sig själv och med alla andra slutgenerator-iteratorer.