수색…
C 반복자 (포인터)
// 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
이 코드는 다음과 같이 각 행에 하나씩 숫자를 출력합니다.
1
2
삼
4
5
속보
const int array[] = { 1, 2, 3, 4, 5 };
이 행은 5 개의 값을 갖는 새로운 정수 배열을 만듭니다. C 배열은 각 값이 연속 블록에 함께 저장되는 메모리에 대한 포인터 일뿐입니다.
const int* first = array;
const int* afterLast = first + sizeof(array) / sizeof(array[0]);
이 행은 두 개의 포인터를 만듭니다. 첫 x 째 포인터에는 h 열 포인터의 값이 제공됩니다.이 값은 h 열의 첫 x 째 요소의 주소입니다. C 배열에서 sizeof 연산자를 사용하면 바이트의 배열 크기가 반환됩니다. 요소의 크기로 나눠서 배열의 요소 수를 제공합니다. 이를 사용하여 배열 다음 의 블록 주소를 찾을 수 있습니다.
for (const int* i = first; i < afterLast; ++i) {
여기서 우리는 iterator로 사용할 포인터를 생성합니다. 그것은 우리가 반복 할 첫 번째 요소의 주소로 초기화됩니다, 우리는만큼 반복 계속거야 i 미만 afterLast 만큼 의미, i 내 주소를 가리키는 array .
std::cout << *i << std::endl;
마지막으로, 루프 내에서 우리는 값 우리의 반복자에 액세스 할 수 있습니다 i 그것을 역 참조가 가리키는됩니다. 역 참조 연산자 * 는 i 의 주소에있는 값을 반환합니다.
개요
반복자는 위치입니다.
반복자는 일련의 요소를 탐색하고 조작하는 수단이며 포인터의 일반화 된 확장입니다. 개념적으로 iterator는 요소가 아니라 위치라는 것을 기억하는 것이 중요합니다. 예를 들어, 다음 순서대로 수행하십시오.
A B C
시퀀스는 3 개의 요소와 4 개의 위치를 포함합니다.
+---+---+---+---+
| A | B | C | |
+---+---+---+---+
요소는 시퀀스 내의 사물입니다. 위치는 의미있는 작업이 시퀀스에 발생할 수있는 장소입니다. 예를 들어, 하나는 요소가 아닌 요소 A의 앞 이나 뒤에 삽입됩니다. 요소 삭제 ( erase(A) )는 먼저 위치를 찾아 지우면됩니다.
반복자에서 값으로
위치에서 값으로 변환하려면 반복기가 참조 해제됩니다 .
auto my_iterator = my_vector.begin(); // position
auto my_value = *my_iterator; // value
반복자는 시퀀스에서 참조하는 값을 역 참조하는 것으로 생각할 수 있습니다. 이는 end() iterator를 순차적으로 참조하지 않아야하는 이유를 이해하는 데 특히 유용합니다.
+---+---+---+---+
| A | B | C | |
+---+---+---+---+
↑ ↑
| +-- An iterator here has no value. Do not dereference it!
+-------------- An iterator here dereferences to the value A.
C ++ 표준 라이브러리에있는 모든 시퀀스와 컨테이너에서 begin() 은 반복자를 첫 번째 위치로 반환하고 end() 는 반복자를 마지막 위치가 아닌 마지막 위치로 반환합니다 (마지막 위치가 아닙니다 !). 결과적으로 알고리즘에서 이러한 반복자의 이름은 종종 first 와 last 레이블이 지정됩니다.
+---+---+---+---+
| A | B | C | |
+---+---+---+---+
↑ ↑
| |
+- first +- last
빈 시퀀스에도 최소한 하나의 위치가 포함되어 있기 때문에 모든 시퀀스에 대한 반복자를 얻을 수도 있습니다.
+---+
| |
+---+
빈 시퀀스에서는 begin() 과 end() 가 같은 위치에 있고 둘 다 역 참조 할 수 없습니다.
+---+
| |
+---+
↑
|
+- empty_sequence.begin()
|
+- empty_sequence.end()
반복자의 다른 시각화는 요소 사이 의 위치를 표시한다는 것입니다.
+---+---+---+
| A | B | C |
+---+---+---+
↑ ^ ^ ↑
| |
+- first +- last
반복기의 참조 해제는 반복자 뒤에 오는 요소에 대한 참조를 리턴합니다. 이보기가 특히 유용한 몇 가지 상황은 다음과 같습니다.
-
insert조작은 요소를 반복자가 가리키는 위치에 삽입하고, -
erase조작은, 건네받은 조작과 같은 위치에 대응하는 반복자를 돌려줍니다. - 반복자와 그 대응하는 역 반복자 는 요소들 사이의 같은 위치에 위치한다.
유효하지 않은 반복자
iterator는 (작업 과정에서) 위치가 더 이상 시퀀스의 일부가 아닌 경우 무효화 됩니다. 무효화 된 반복자는 유효한 위치에 재 할당 될 때까지 참조 해제 될 수 없습니다. 예 :
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
C ++ 표준 라이브러리의 많은 알고리즘과 시퀀스 멤버 함수에는 반복자가 무효화 될 때 적용되는 규칙이 있습니다. 각각의 알고리즘은 iterator를 다루는 (그리고 무효 화하는) 방식이 다릅니다.
반복자로 탐색하기
아시다시피 반복자는 시퀀스를 탐색하는 데 사용됩니다. 그렇게하기 위해서 반복자는 순서 전체에서 그 위치를 이동시켜야한다. 반복자는 순서대로 진행할 수 있고 일부는 뒤로 진행할 수 있습니다.
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.
, 표준의 두번째 인수 참고 : 거리가 첫 번째 행에 도달 할 수 있어야 (즉, 또는 first 작거나보다되어야 second ).
반복자를 사용하여 산술 연산자를 수행 할 수 있지만 모든 유형의 반복자에 대해 모든 연산이 정의되는 것은 아닙니다. a = b + 3; Random Access Iterators에서 작동하지만 Forward 또는 Bidirectional Iterators에서는 작동하지 않을 것입니다. Forward 또는 Bidirectional Iterator는 여전히 b = a; ++b; ++b; ++b; 와 같은 것으로 3 단계로 진행할 수 있습니다 b = a; ++b; ++b; ++b; . 따라서 iterator 유형이 확실하지 않은 경우 (예 : iterator를 허용하는 템플릿 함수에서) 특수 함수를 사용하는 것이 좋습니다.
반복자 개념
C ++ 표준은 여러 가지 반복기 개념을 설명합니다. 이들은 참조하는 순서대로 행동하는 방식에 따라 그룹화됩니다. 반복자가 모델링 한 개념 (동작이 유사 함)을 알고 있으면 해당 반복 순서에 관계없이 해당 반복자의 동작을 보장 할 수 있습니다. 그것들은 종종 다음 순서 반복자 개념이 전임자보다 더 나은 단계이기 때문에 가장 제한이 적은 순서대로 설명됩니다.
- 입력 반복자 : 위치별로 한 번만 참조 해제 할 수 있습니다. 한 번에 한 포지션에서만 진행할 수 있습니다.
- Forward Iterators : 반복적으로 역 참조 될 수있는 입력 반복자.
- 양방향 반복자 : 한 번에 한 위치 씩 뒤로 이동할 수있는 앞으로 반복자.
- 랜덤 액세스 반복자 (Random Access Iterators) : 한 번에 여러 포지션을 앞으로 또는 뒤로 이동할 수있는 양방향 반복자.
- 인접 반복자 (C ++ 17 이후) : 기본 데이터가 메모리에서 연속적임을 보장하는 랜덤 액세스 반복자.
알고리즘은 주어진 반복자가 모델링 한 개념에 따라 달라질 수 있습니다. 예를 들어, 순방향 반복자에 대해 random_shuffle 을 구현할 수 있지만 임의 액세스 반복자를 필요로하는보다 효율적인 변형이 제공 될 수 있습니다.
반복자 특성
반복자 특성은 반복자의 속성에 대한 일관된 인터페이스를 제공합니다. 그들은 값, 차이, 포인터, 참조 유형 및 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;
}
이터레이터의 범주는 알고리즘을 전문화하는 데 사용할 수 있습니다.
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());
}
반복자의 범주는 기본적으로 반복자 개념입니다. 단, 연속 반복자는 코드를 중단 한 것이므로 자체 태그가 없습니다.
역 반복기
목록이나 벡터를 거꾸로 반복하려는 경우 reverse_iterator 사용할 수 있습니다. 역방향 반복자는 base() 통해 액세스 할 수있는 멤버로 유지되는 양방향 또는 임의 액세스 반복기에서 만들어집니다.
역순으로 반복하려면 rbegin() 및 rend() 를 콜렉션의 끝과 콜렉션의 시작에 대한 반복자로 사용하십시오.
예를 들어, 역순으로 반복하려면 다음을 사용하십시오.
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
reverse iterator는 base() 멤버 함수를 통해 forward iterator로 변환 될 수 있습니다. 관계는 역방향 반복기가 base() 반복자를지나 한 요소를 참조한다는 것입니다.
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()
반복자가 요소 사이의 위치를 표시하는 시각화에서 관계는 더 간단합니다.
+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+
↑ ↑
| |
| end()
| rbegin()
begin() rbegin().base()
rend()
rend().base()
벡터 반복자
begin 은 시퀀스 컨테이너의 첫 번째 요소에 대한 iterator 를 반환합니다.
end 는 end 요소를지나 첫 번째 요소에 iterator 를 반환합니다.
벡터 객체가 const 이면 begin 과 end 모두 const_iterator 반환합니다. 벡터가 const 가 아닐지라도 const_iterator 를 반환하기를 cbegin 과 cend 사용할 수 있습니다.
예:
#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;
}
산출:
1 2 3 4 5
지도 반복자
컨테이너의 첫 번째 요소에 대한 반복자입니다.
맵 객체가 const로 정규화 된 const_iterator 함수는 const_iterator 반환합니다. 그렇지 않으면 iterator 반환 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';
산출:
a => 200
b => 100
c => 300
스트림 반복자
스트림 이터레이터는 시퀀스를 읽거나 컨테이너에서 형식이 지정된 데이터를 인쇄 할 때 유용합니다.
// 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, " -- "));
예제 프로그램은 표준 출력에 1 -- 2 -- 3 -- 4 -- 인쇄합니다.
자체 생성자 지원 반복자 작성
다른 언어의 일반적인 패턴은 객체의 "스트림"을 생성하고 루프 코드를 사용하여 루프를 돌릴 수있는 기능을 갖추고 있습니다.
우리는 이것을 C ++로 모델링 할 수있다.
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;
};
라이브 예제 .
생성 된 요소를 일찍 저장하여 우리가 이미 끝에 있는지 쉽게 알 수 있습니다.
종단 생성자 iterator의 함수는 사용되지 않으므로 std::function 한 번만 복사하여 생성자 반복자를 만들 수 있습니다. 기본 생성자 생성자 iterator는 그 자체와 다른 모든 end-generator-iterator와 비교합니다.