음악, 삶, 개발
20. Container and Iterators 본문
Write programs that do one thing and do it well. Write programs to work together
- Doug McIlroy
20.1 Storing and processing data
C 프로그래머 Jack 과 C++ 프로그래머 Jill 이 있다.
이 둘은 자동차의 속력를 float 으로 재보기로했다.
Jack 은 array 에, Jill 은 vector 에 각각 값을 저장하기로했다.
이 둘은 코드를 작성했다.
double* get_from_jack(int* count);
vector<double>* get_from_jill();
void fct() {
int jack_count = 0;
double* jack_data = get_from_jack(&jack_count);
vector<double>* jill_data = get_from_jill();
// process
delete[] jack_data;
delete jill_data;
}가정은 data 는 free store 에, 그리고 사용후 반드시 delete 해야한다.
다른 가정은 우리는 Jack 과 Jill 의 code 를 rewrite 할수없다.
20.1.1 Working with data
위의 코드에서, 각 data 값이 가질수있는 가장 높은 값을 구하는 code 를 추가해보자.
double* get_from_jack(int* count);
vector<double>* get_from_jill();
void fct() {
int jack_count = 0;
double* jack_data = get_from_jack(&jack_count);
vector<double>* jill_data = get_from_jill();
double h = -1;
double* jack_high; // jack_high will point to the element with the highest value.
double* jill_high; // jill_high will point to the element with the highest value.
for (int i = 0; i < jack_count; ++i) {
if (h < jack_data[i]) {
jack_high = &jack_data[i]; // save address of largest element.
h = jack_data[i]; // update "largest element"
}
}
h = -1;
for (int i = 0; i < jill_data->size(); ++i) {
if (h < (*jill_data)[i]) {
jill_high = &(*jill_data)[i]; // save address of largest element.
h = (*jill_data)[i]; // update "largest element"
}
}
std::cout << "Jill'S max : " << *jill_high << "; Jack's max : " << *jack_high;
delete[] jack_data;
delete jill_data;
}참고 : *jill_data[i] 는 *(jill_data[i]) 를 의미한다.
따라서 위 코드의 의도대로는 (*jill_data)[i] 로 써야한다.
20.1.2 Generalizing code
이해 안가서 생략. (추후 읽기)
20.2 STL ideals
STL 은 매우 좋다는 이야기. (이걸 매우 길게 이야기했음)
iostream 이나 C-style 함수들은 STL 이 아니라고함.
20.3 Sequences and iterators
sequence : 데이터의 모음 (a collection of data)
iterator : sequence 의 element 를 식별(identify) 하는 객체.
sequence 는 시작(begin) 과 끝(end) 를 가지고있다.
우리는 각 element 의 값을 읽거나 (read) 씀으로써 (write) sequence 를 시작부터 끝까지 순회(traverse)할수있다.
우리는 2개의 iterator 로 sequence 의 시작과 끝을 식별(identify) 할수있다.
sequence 를 그림으로 표현하면 아래와 같다.
위 그림에서, begin 과 end 는 iterator 이다.
STL sequence 는 half-open 이라고도 부른다.
begin 에 의해 식별되는 element 는 sequence 에 속해있지만,
end iterator 는 sequence 의 end 의 다음 위치를 가리킨다.(one beyond the end of the sequence)
따라서 일반적인 sequence range 의 기보법(notation)은 [begin:end) 이다. (half-open)
위 그림의 화살표는 우리가 어떤 element 를 가리키는 iterator 가 있다면,
그 다음 interator 도 가질수있음을 의미한다.
그래서 iterator 가 정확히 모냐?iterator 는 다소 추상적인 개념이다.
-
iterator 는 sequence 의 element (또는 마지막 element 의 다음) 을 가리킨다. (또는 참조하다, 즉 point to or refer to )
-
우리는 두개의 iterator 를 == 와 != 을 사용하여 비교할수있다.
-
iterator 가 가리키는 element 의 값을 * (dereference) 연산자를 통해 참조할수있다.
-
다음 element 를 가리키는 iterator 를 ++ 를 사용하여 얻을수있다.
예를 들어, p 와 q 가 동일한 sequence 의 element 를 가리키는 iterator 라고 가정해보자.
그럼 아래와 같은 연산을 할수있다.
iterator 는 pointer 와 연관성이 있다.
array 의 element 를 가리키는 pointer 는 iterator 이다.
하지만 모든 iterator 가 pointer 인것은 아니다.
예를 들어, [begin:end) 의 바깥을 가리키려할때, range-check 을 해주는 iterator 를 만들수있다.
추후 몇가지 예를 볼것이다.
iterator 는 우리의 code(algorithm) 을 data 로 연결하는데 사용된다.
code 의 작성자는 iterator 에 대해서는 알고있지만, 어떻게 iterator 가 data 를 받아오는지에 대해
알 필요가 없고,
data 의 제공자는 어떻게 data 가 사용자에게 저장되는지 detail 을 노출하는대신에,
iterator 를 제공한다.
이와 같이 함으로써, algorithm 과 container 의 독립성을 유지할수있다.
STL algorithm 과 container 가 잘 작동하는 이유는, 그들은 서로에 대해 모르기때문이다.
대신에, 둘다 2개의 iterator 로 정의된 sequence 그 무엇인지 알고있다.
나의 algorithm 은 data 를 접근하고 저장하는 다양한 방법에 대해 전혀 알 필요가 없다.
단지 iterator 에 대해서 알면 된다.
거꾸로, 내가 data 제공자라면, 다양한 사용자를 위해 다른 code 들을 여러번 작성할 필요없이,
내 data 를 위한 iterator 를 제공하면 된다.
대부분의 경우, iterator 는 *, ++, ==, != 연산자를 사용하여 정의된다.
STL framwork 는 10개의 container 와, 60 algorithm 을 가지고있으며,
이 둘은 iterator 를 통해 연결된다. (챕터 21에서 자세히)
20.3.1 Back to the example
STL seuqnce 의 개념을 사용하여, "가장 큰 값을 가진 element 를 찾아라" 를 구현해보자.
template<typename Iterator>
Iterator high(Iterator first, Iterator last) {
// return an iterator to the element in [first:last) that has the highest value
Iterator high = first;
for (Iterator p = first; p!= last; ++p) {
if (*high < *p) {
high = p;
return high;
}
}
}
위와 같이 정의후, 아래와 같이 사용할수있다.
double * get_from_jack(int* count);
vector<double>* get_from_jill();
void fct() {
int jack_count = 0;
double* jack_data = get_from_jack(&jack_count);
vector<double>* jill_data = get_from_jill();
double* jack_high = high(jack_data, jack_data + jack_count);
vector<double>& v = *jll_data;
double* jill_high = high(&v[0], &v[0] + v.size());
std::cout << "Jill's high " << *jill_high << "; Jack's high " << *jack_high << std::endl;
delete [] jack_data;
delete jill_data;
}20.4 Linked lists
앞서 본것처럼 sequence 의 모습은 아래와 같았다.
vector 의 memory 안에 모습은 아래와 같다.
위의 그림처럼, subscript 0 은 iterator begin() 과 동일하고,
size() 는 end() 와 동일하다.
vector 의 element 들은 memory 안에서 연속적이다.
STL sequence diagram 에 의해 제안된 data 구조를 linked list 라고 한다.
추상화 모델안에 arrow 는 pointer 로 구현된다.
linked list 의 element 는 element 혹은 pointer 들로 구성된 link 에 속해있다.
link 가 하나의 pointer 만을 가진 linked list 를 singly-linked list 라고 하며,
link 가 previous link 와 next link 를 모무 pointer 로 가지고있다면 doubly-linked list 라고 한다.
C++ standard library 에서는 list 라는 이름으로 제공된다.
아래와 같은 그림으로 표현할수있다.
code 로 표현하면 아래와 같다.
template<typename Elem>
struct Link {
Link* prev; // previous link
Link* succ; // next link
Elem val; // the value
};
template<typename Elem>
struct list {
Link<Elem>* first;
Link<Elem>* last; // one beyond the last link
}Link 의 모습은 아래와 같다.
list 에서는, 이미 존재하는 element 를 파괴하지않고, element 를 insert 하거나 delete 할수있다.
list 를 사용하고자한다면, 꼭 당신이 고려하는 연산들을 위의 그림들과 같이 그려보도록 하라.
Linked list 는 100번말보다 한번의 그림이 낫다.
20.4.1 List operations
어떠한 연산이 list 를 위해 필요한가?
- subscripting 을 제외한 vector 를 위한 연산 (constructors,size, etc..)
- Insert (element 를 추가하기), erase (element 를 제거하기)
- element 를 참조하고 list 를 순회할수있는 도구 : iterator
STL 에서 iterator type 은 class 의 member 이다.
template<typename Elem>
class list {
public :
class iterator; // member type : iterator
iterator begin();
iterator end();
iterator insert(iterator p, const Elem& v); // insert v into list after p
iterator erase(iterator p); // remove p from the list
void push_back(const Elem& v); // insert v at end
void push_front(const Elem& v); // insert v at front
void pop_front(); // remove the first element
void pop_back(); // remove the last element
Elem& front(); // the first element
Elem& back(); // the last element
private :
};위의 list 는 std::list 와 다르지만, 어떻게 std::list 가 구현되었는지 설명하기 위함이다.
(std::list 를 Appendix B 에서 자세히 다룬다)
iterator 는 list 의 중심에 있다.
iterator 는 insert, remove, navigate(subscripting 하지않고) 하기위해 사용된다.
위와 같은 코드의 style 이 standard library algorithm 의 핵심이다.
왜 list 는 subscript 하지않는가? 그렇게 할수있지만, 매우 매우 느릴것이다.
만약 lst[1000] 을 하려한다면, 첫번째 element 부터 1000 element까지 도달하기위해
그 중간에 있는 모든 element 를 가는동안 다 방문하기때문이다.
따라서 std::list 는 subscript syntax 를 제공하지않는다.
위의 코드에서 iterator 를 nested class member 로 가진 이유는,
오직 list 내에서는 사용되는 class 이기때문이다. 따라서 global 일 필요가 없다.
또한 저렇게 nested class 로 iterator 를 사용함으로써,
다른 class 에서도 똑같이 iterator 라는 이름을 사용할수있는것이다.
list<T>::iterator;
vector<T>::iterator;
map<K, V>::iterator;20.4.2 Iteration
list iterator 은 *, ++, ==, != 를 제공해야한다.
또한 std::list 는 doubly-linked list 이기때문에, backward 를 iterating 하기위한 - 또한 제공해야한다.
template<typename Elem>
class list<Elem>::iterator {
public :
iterator(Link<Elem>* p) : curr{p} {}
iterator& operator++() { curr = curr->succ; return *this; } // forward
iterator& operator-() { curr = curr->prev; return *this; } // backword
Elem& operator*() { return curr->val; } // get value (derefernce)
bool operator==(const iterator& b) const { return curr == b.curr; }
bool operator!=(const iterator& b) const { return curr! = b.curr; }
private :
Link<Elem>* curr; // current link
}만약 list 가 empty 하다면 어떻게 되는것인가?
begin() 과 end() == 라면?
이런 이유로 list 가 설계될때 end() 를 last element 로 하지않은것이다.
아래와 같이 작성할수있다.
list<int>::iterator p = high(lst.begin(), lst.end());
if (p == lst.end()) {
std::cout << "the list is empty";
}
else {
std::cout << "the highest value is " << *p << std::endl;
}20.5 Generalizing vector yet again
std::vector 에서는 begin() 과 end() iterator 가 존재한다.
직접 구현해보자.
template<typename T>
class vector {
public :
using size_type = usigned long;
using value_type = T;
using iterator = T*;
using const_iterator = const T*;
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
size_type size();
}list 를 구현해보자.
template<typename T>
class list {
public :
class Link;
using size_type = unsigned long;
using value_type = T;
class iterator;
class const_iterator;
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
size_type size();
};using 은 C+11 에서 등장했는데, C 와 C++ 에서 typedef 로 알려진 기능을 일반화시켜주기위한 기보법이다.
20.5.1 Container traversal
vector 에서는 size() 를 통해 vector 의 첫번째 element 부터 마지막까지 순회(traverse) 할수있다.
void f(const vector<double>& v) {
for (int i = 0; i < v.size(); ++i) {
std::cout << v[i] << std::endl;
}
}위와 같은 subscripting 을 list 는 제공하지않는다.
하지만 vector 와 list 둘다 range-for-loop 이 가능하다.
void f(const vector<double& v, const list<double>& lst) {
for (double x : v) {
std::cout << x << std::endl;
}
for (double x : lst) {
std::cout << x << std::endl;
}
}range-for-loop 은 내부적으로 begin() 과 end() 를 사용하고있다.
range-for-loop 은 사실 sequence 를 iterator 로 loop 하는 문법적인 sugar 이다.
20.5.2 auto
아래와같은 code 를 작성했다고 가정해보자.
template<typename T>
void user(vector<T>& v, list<T>& lst) {
for (vector<T>::iterator p = v.begin(); p! = v.end(); ++p) {
std::cout << *p << std::endl;
}
list<T>::iterator q = find(lst.begin(), lst.end(), T{42});
} 이런 code 를 작성할때 가장 열받는것은, compiler 는 이미 list 를 위한 iterator type 과
vector 를 size_type 을 알고있다.
compiler 가 이미 알고있는것을 다시 말해줘야하는가?
위와 같은 code 는 오타를 유발하고, 실수할 가능성을 만든다.
다행히, auto 라는 variable 을 사용하면 된다.
template<typename T>
void user(vector<T>& v, list<T>& list) {
for(auto p = v.begin(); p! = v.end(); ++p) {
std::cout << *p << std::endl;
}
auto q = find(lst.begin(), lst.end(), T{42});
}auto 는 초기화를 포함하는 모든 정의에 사용할수있다.
auto x = 123;
auto c = 'y';
auto& r = x;
auto y = r;하지만 string literal 의 type 은 const char* 라서, auto 를 사용할때 주의해야한다.
auto s1 = "Lee"; // s1 is a const char*
string s2 = "Lee"; // s2 is a string우리가 원하는 type 이 뭔지 정확히 알고있을때, auto 를 사용할수있다.
auto 의 가장 흔한 사용은 range-for-loop 안에서 loop variable 로써 사용하는것이다.
template<typename C>
void f(const C& cont) {
for (const auto& x : cont) {
std::cout << x << std::endl;
}
}element 가 너무 커서 copy 하는게 비쌀때는 auto& 를 사용한다.
그리고 element 를 수정하지않고자할때는 앞에 const 를 붙힌다. 따라서 const auto&
20.6 An example : a simple text editor
20.6.1 Lines
20.6.2 Iteration
20.7 vector, list, and string
생략.
20.7.1 insert and erase
std::vector 는 container 를 위한 우리의 가장 default 선택지이다.
대안(alternative) 은 우리가 정말 필요할때만 필요한것이다.
vector 에서 insert() 나 erase() 를 매우 많은 element들 또는 매우 큰 element 로 할때의 비용이 많이 들수있다.
사실 이런 부분에 대해서는 너무 걱정하지않아도 된다.
전문가들조차도 performance 에 대해 예측하는것은 매우 힘든일이다.
vector 를 사용할시 주의할점은 만약 insert 나 erase 같은 연산을할것이라면,
vector 의 element 가 iterator 나 pointer 여서는 안된다.
만약 element 가 move 한다면, 당신의 iterator 또는 pointr 가 이상한 element 를 또는 no element 를 가리킬것이기때문이다.
이런 점에서는 list 가 vector 보다 advantage 가 있다.
만약 프로그램의 여기저기에서 우리가 point 할 객체, 또는 매우 큰 객체의 collection 이 필요하다면 list 를 사용하라.
insert 와 erase 에 대해, vector 와 list 를 비교해보면 아래와 같은 그림이다.
20.8 Adapting our vector to the STL
요약하면,
만약 100000 element 가 있는 container 가 필요하다면 list 나 map 을 사용하라.
하지만 현대 컴퓨터는 매우 좋다. 따라서, 작은 small elements 들이라면 list 를 피하고 vector 를 써야한다.
20.9 Adapting built-in arrays to the STL
생략.
20.10 Container overview
아래는 STL 이 제공하는 container 목록이다.
위의 container 들에 대해 더 자세히 알고자한다면 아래의 책을 참고하라.
The C++ Standard Library : A Tutorial and Reference (2012)
The C++ Primer 5th edition (2005)
The C++ Programming Language 4th edition
또는 이 사이트
내가 이 책에서, 위의 container 들을 다 설명하지않아서 속은 기분인가?
그건 가능하지않다. 프로그래밍은 누군가가 모든 도구와 기술을 파악하기에는 너무 큰 세계이다.
프로그래머로써, 당신은 늘 새로운 정보를 탐구하는 습관을 가져야한다.
프로그래밍은 dynmaic 하고, 늘 급격하게 무언가가 변하는 곳이다.
따라서, 당신이 알고있는것에 만족하고 안주하는것은 낙오되는 지름길이다.
"Look it up" (찾아봐!) 는 대부분의 문제에 가장 완벽한 대답이다.
결론적으로 container 란 무엇인가?
STL container 의 정의는 아래와같다.
- sequence of elements [begin():end())
- element 를 copy 하는 연산을 제공. (assignment 와 copy constructor 를 통해)
- element type 을 value_type 으로 명명
- iterator 라는 iterator type 을 가지고있음. *, ++, ==, != 를 제공.
- list 는 추가적으로 moving backward (뒤로가기) 하기위해 ㅡ (bidirectional iterator)을 제공.
- vector 는 추가적으로 ㅡ, [ ], + 를 제공함 (random-access iterator)
- inerst(), erase(), front(), back(), push_back(), pop_back(), size() 를 제공함. (vector 와 map 은 subscripting 제공)
- element 를 서로 비교할수있는 비교 연산자 ==, !=, <, <=, >, >= 를 제공.
detail 은 Appendix B 를 참고하고, 이보다 더 원하면 The C++ Programming Language 책을 읽어라.
추가적으로, 개인과 각 조직들이 만든 자기들만의 container 들이 많이 있따.
의심이 가면 vector 를 사용하라.
확실히 vector 를 사용할 이유가 있지않는한 vector 를 사용하라.
20.10.1 Iterator categories
만약 당신이 단순한 연산을 한고자한다면 iterator 들은 서로 교환가능(interchangeable) 하다.
하지만 그외에는 아래와같은 iterator 들 또한 필요할수것이다.
random-acess iterator 는 bidirectional iterator 이고,
bidirectional iterator 는 forward iterator 이다.
output iterator 나 input iterator 가 사용되어야할곳에 forward iterator 를 사용할수있다.
Review
- Why does code writtin by difference people look different? Give examples.
- What are simple questions we ask of data?
- What are a few diffferent ways of storing data?
- What basic operations can we do to a collection of data items?
- What are some ideals for the way we store our data?
- What is an STL sequence?
- What is an STL iterator? What operations deos it support?
- How do you move an iterator to the next element?
- How do you move an iterator to the previous element?
- What happens if you try to move an iterator past the end of a sequence?
- What kinds of iterators can you move to the previous element?
- Why is it useful to seperate data from algorithms?
- What is the STL?
- What is linked list? How does it fundamentally differ from a vector?
- What is a link (in a linked list)?
- What does insert() do? What does erase() do?
- How do you know if a sequence is empty?
- What operations does an iterator for a list provide?
- How do you iterate over a container using the STL?
- When would you use a string rather than a vector?
- When would you use a list rather than a vector?
- What is a container?
- What should begin() and end() do for a container?
- What containers does the STL provide?
- What is an iterator category? What kinds of iterators does the STL offer?
- What opertions are provided by a random-access iterator, but not a bidirectional iterator?
Terms
- algorithm
- array container
- auto
- begin()
- container
- contiguous
- doubly-linked list
- element
- empty sequence
- end()
- erase()
- insert()
- iteration
- iterator
- linked list
- sequence
- singly-linked list
- size_type
- STL
- traversal
- using
- type alias
- value_type
