STL에서 실제로 deque는 무엇입니까?
나는 STL 컨테이너를보고 실제로 무엇인지 파악하려고 노력했다. (즉, 사용 된 데이터 구조) deque 는 나를 막았다. 처음에는 양쪽 끝에서 삽입과 삭제를 허용하는 이중 연결 목록이라고 생각했다. 일정한 시간이지만, 나는 연산자 []가 일정한 시간에 행해야 한다는 약속에 어려움을 겪고 있습니다. 연결된 목록에서 임의 액세스는 O (n)이어야합니다.
동적 배열이라면 어떻게 일정한 시간 에 요소 를 추가 할 수 있습니까? 재 할당이 발생할 수 있으며 O (1)은 벡터와 같이 상각 된 비용이라는 점을 언급해야합니다 .
그래서 일정한 시간에 임의의 액세스를 허용하는이 구조가 무엇인지 궁금해하며 동시에 더 큰 새로운 장소로 옮길 필요가 없습니다.
deque는 다소 재귀 적으로 정의됩니다. 내부적으로 는 고정 크기 의 덩어리 덩어리 를 두 번 끝 냅니다. 각 청크는 벡터이며 청크 자체의 큐 (아래 그림에서 "맵")도 벡터입니다.
이 성능 특성의 좋은 분석입니다 그리고 그것은 비교하는 방법 vector에 이상 CodeProject의 .
GCC 표준 라이브러리 구현은 내부적으로 a T**를 사용 하여 맵을 나타냅니다. 각 데이터 블록은 T*일정한 크기로 할당됩니다 __deque_buf_size(에 따라 다름 sizeof(T)).
벡터로 구성된 벡터라고 상상해보십시오. 그들은 표준이 아닙니다 std::vector.
외부 벡터는 내부 벡터에 대한 포인터를 포함합니다. 모든 빈 공간을 끝에 할당하는 대신 재 할당을 통해 용량을 변경 std::vector하면 빈 공간이 벡터의 시작과 끝에서 동일한 부분으로 분할됩니다. 이렇게 허용 push_front및 push_back양쪽이 벡터 상각 O (1) 시간에 발생한다.
내부 벡터 동작은 전면 또는 후면에 따라 변경되어야합니다 deque. 뒷면 std::vector에서는 끝에서 자라며 push_backO (1) 시간에 발생 하는 표준으로 작동 할 수 있습니다 . 앞에서는 반대로 시작해야합니다 push_front. 실제로 이것은 전면 요소에 대한 포인터와 크기와 함께 성장 방향을 추가하여 쉽게 달성됩니다. 이 간단한 수정 push_front으로 O (1) 시간 이 될 수도 있습니다.
모든 요소에 액세스하려면 O (1)에서 발생하는 적절한 외부 벡터 인덱스로 오프셋하고 나누고 O (1) 인 내부 벡터로 인덱싱해야합니다. 이것은 내부 벡터가의 시작 또는 끝에있는 것을 제외한 모든 고정 크기라고 가정합니다 deque.
deque = 더블 엔드 큐
어느 방향 으로든 성장할 수있는 용기.
양단이되는 전형적 A와 구현 vector의 vectors(일정한 시간을 랜덤 액세스를 제공 할 수없는 벡터의리스트). 2 차 벡터의 크기는 구현에 따라 다르지만 일반적인 알고리즘은 바이트 단위로 일정한 크기를 사용하는 것입니다.
(이것은 내가 다른 스레드 에서 제공 한 답변 입니다. 본질적으로 단일을 사용하는 상당히 순진한 구현조차도 vector"일관되지 않은 고정 된 push_ {front, back}"의 요구 사항을 준수 한다고 주장합니다 . , 이것이 불가능하다고 생각하지만, 놀라운 맥락에서 문맥을 정의하는 다른 관련 인용문을 발견했습니다. 내가 참아주세요.이 답변에서 실수를 한 경우 어떤 것을 식별하는 것이 매우 도움이 될 것입니다 나는 정확하게 그리고 내 논리가 무너진 곳이라고 말했다.)
이 답변에서 나는 좋은 구현 을 식별하려고하지 않고 C ++ 표준의 복잡성 요구 사항을 해석하는 데 도움을 주려고합니다. Wikipedia 에 따르면 무료로 제공되는 최신 C ++ 11 표준화 문서 인 N3242 에서 인용하고 있습니다. (최종 표준과 다르게 구성 된 것으로 보이므로 정확한 페이지 번호를 인용하지는 않습니다. 물론 이러한 표준은 최종 표준에서 변경되었을 수도 있지만 실제로는 그렇게 생각하지 않습니다.)
deque<T>를 사용하여 A를 올바르게 구현할 수 있습니다 vector<T*>. 모든 요소는 힙에 복사되고 포인터는 벡터에 저장됩니다. (나중에 벡터에 더).
왜 T*대신에 T? 표준에 따라
"deque의 양쪽 끝에 삽입하면 deque에 대한 모든 반복자가 무효화되지만 deque의 요소에 대한 참조의 유효성에는 영향을 미치지 않습니다. "
(내 강조). T*그것을 만족시키는 데 도움 이 됩니다. 또한이를 충족시키는 데 도움이됩니다.
"deque의 시작 또는 끝에 단일 요소를 삽입하면 항상 ..... T 생성자에 대한 단일 호출이 발생합니다 ."
이제 논란의 여지가 있습니다. 를 사용 vector하여 저장하는 이유 는 T*무엇입니까? 그것은 우리에게 랜덤 액세스를 제공합니다. 잠시 동안 벡터의 복잡성을 잊어 버리고이를 신중하게 만들어 봅시다.
표준은 "포함 된 개체에 대한 작업 수"에 대해 설명합니다. 들어 deque::push_front이 명확 1 정확히 하나 때문에 T개체가 구성되어 기존의 제로 T개체를 읽거나 어떤 방식으로 스캔됩니다. 이 숫자 1은 분명히 상수이며 현재 deque에있는 오브젝트 수와 무관합니다. 이를 통해 다음과 같이 말할 수 있습니다.
'우리의 deque::push_front경우 포함 된 개체 (Ts)에 대한 작업 수는 고정되어 있으며 이미 deque에있는 개체 수와 무관합니다.'
물론, 작업 수는 T*그다지 잘 작동하지 않습니다. (가) 때 vector<T*>너무 큰 성장, 그것은 realloced됩니다 많은 T*들 주위에 복사됩니다. 예,의 작업 수는 T*크게 다르지만 작업 수에는 T영향을 미치지 않습니다.
계산 작업 T과 계산 작업의 차이점을 왜 걱정해야 T*합니까? 표준에 따르면 다음과 같습니다.
이 절의 모든 복잡성 요구 사항은 포함 된 개체에 대한 작업 수로 만 명시됩니다.
를 들어 deque, 포함 된 개체가있는 T아닌 T*, 우리가 어떤 동작을 무시할 수 의미있는 사본 (또는 reallocs)가 T*.
나는 벡터가 deque에서 어떻게 작동하는지에 대해서는별로 말하지 않았다. 아마도 우리는 이것을 원형 버퍼로 해석 할 것입니다 (벡터는 항상 최대 값을 차지하고 capacity()벡터가 가득 찼을 때 모든 것을 더 큰 버퍼로 재 할당합니다) 세부 사항은 중요하지 않습니다.
마지막 몇 단락에서, 우리는 deque::push_front이미 deque에있는 객체 수와 포함 된 객체에 대해 push_front에 의해 수행 된 작업 수 사이의 관계를 분석 T했습니다. 그리고 우리는 그들이 서로 독립적이라는 것을 알았습니다. 표준은 복잡성이 운영시 측면에서 의무화됨에 따라 복잡성이 T일정하다고 말할 수있다.
예. Operations-On-T * -Complexity 는 (로 인해) 상각 vector되지만, 우리는 Operations-On-T-Complexity 에만 관심 이 있으며 이는 일정합니다 (비 암호화).
vector :: push_back 또는 vector :: push_front의 복잡성은이 구현과 관련이 없습니다. 이러한 고려 사항에는 작업이 포함 T*되므로 관련이 없습니다. 표준이 복잡성이라는 '전통적인'이론적 개념을 언급하고 있다면,“포함 된 객체에 대한 작업 수”로 명시 적으로 제한되지 않았을 것입니다. 그 문장을 과도하게 해석하고 있습니까?
개요에서, 당신은 생각할 수있는 dequeA와double-ended queue
데이터 deque는 고정 크기 벡터의 청크에 의해 저장됩니다.
로 가리키는 map(벡터 덩어리이기도하지만 크기가 변경 될 수 있음)
의 주요 부품 코드는 다음 deque iterator과 같습니다.
/*
buff_size is the length of the chunk
*/
template <class T, size_t buff_size>
struct __deque_iterator{
typedef __deque_iterator<T, buff_size> iterator;
typedef T** map_pointer;
// pointer to the chunk
T* cur;
T* first; // the begin of the chunk
T* last; // the end of the chunk
//because the pointer may skip to other chunk
//so this pointer to the map
map_pointer node; // pointer to the map
}
의 주요 부품 코드는 다음 deque과 같습니다.
/*
buff_size is the length of the chunk
*/
template<typename T, size_t buff_size = 0>
class deque{
public:
typedef T value_type;
typedef T& reference;
typedef T* pointer;
typedef __deque_iterator<T, buff_size> iterator;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
protected:
typedef pointer* map_pointer;
// allocate memory for the chunk
typedef allocator<value_type> dataAllocator;
// allocate memory for map
typedef allocator<pointer> mapAllocator;
private:
//data members
iterator start;
iterator finish;
map_pointer map;
size_type map_size;
}
아래 deque에서는 주로 세 부분으로 된 핵심 코드를 제공합니다 .
반복자
구성하는 방법
deque
1. 반복자 ( __deque_iterator)
반복자의 주요 문제는 ++ 일 때-반복자가 다른 청크로 건너 뛸 수 있다는 것입니다 (청크의 가장자리를 가리키는 경우). 예를 들어, 세 개의 데이터 청크가 : chunk 1, chunk 2, chunk 3.
pointer1받는 포인터의 시작 chunk 2때 연산자 --pointer는 말에 포인터 것이다 chunk 1그래서에 관해서 pointer2.
아래에서는 주요 기능을 제공합니다 __deque_iterator.
먼저 덩어리로 건너 뜁니다.
void set_node(map_pointer new_node){
node = new_node;
first = *new_node;
last = first + chunk_size();
}
chunk_size()청크 크기를 계산 하는 함수는 단순화를 위해 8을 반환한다고 생각할 수 있습니다.
operator* 청크로 데이터를 얻다
reference operator*()const{
return *cur;
}
operator++, --
// 증분 형태의 접두사
self& operator++(){
++cur;
if (cur == last){ //if it reach the end of the chunk
set_node(node + 1);//skip to the next chunk
cur = first;
}
return *this;
}
// postfix forms of increment
self operator++(int){
self tmp = *this;
++*this;//invoke prefix ++
return tmp;
}
self& operator--(){
if(cur == first){ // if it pointer to the begin of the chunk
set_node(node - 1);//skip to the prev chunk
cur = last;
}
--cur;
return *this;
}
self operator--(int){
self tmp = *this;
--*this;
return tmp;
}
self& operator+=(difference_type n){ // n can be postive or negative
difference_type offset = n + (cur - first);
if(offset >=0 && offset < difference_type(buffer_size())){
// in the same chunk
cur += n;
}else{//not in the same chunk
difference_type node_offset;
if (offset > 0){
node_offset = offset / difference_type(chunk_size());
}else{
node_offset = -((-offset - 1) / difference_type(chunk_size())) - 1 ;
}
// skip to the new chunk
set_node(node + node_offset);
// set new cur
cur = first + (offset - node_offset * chunk_size());
}
return *this;
}
// skip n steps
self operator+(difference_type n)const{
self tmp = *this;
return tmp+= n; //reuse operator +=
}
self& operator-=(difference_type n){
return *this += -n; //reuse operator +=
}
self operator-(difference_type n)const{
self tmp = *this;
return tmp -= n; //reuse operator +=
}
// random access (iterator can skip n steps)
// invoke operator + ,operator *
reference operator[](difference_type n)const{
return *(*this + n);
}
2. 건설 방법 deque
공통 기능 deque
iterator begin(){return start;}
iterator end(){return finish;}
reference front(){
//invoke __deque_iterator operator*
// return start's member *cur
return *start;
}
reference back(){
// cna't use *finish
iterator tmp = finish;
--tmp;
return *tmp; //return finish's *cur
}
reference operator[](size_type n){
//random access, use __deque_iterator operator[]
return start[n];
}
template<typename T, size_t buff_size>
deque<T, buff_size>::deque(size_t n, const value_type& value){
fill_initialize(n, value);
}
template<typename T, size_t buff_size>
void deque<T, buff_size>::fill_initialize(size_t n, const value_type& value){
// allocate memory for map and chunk
// initialize pointer
create_map_and_nodes(n);
// initialize value for the chunks
for (map_pointer cur = start.node; cur < finish.node; ++cur) {
initialized_fill_n(*cur, chunk_size(), value);
}
// the end chunk may have space node, which don't need have initialize value
initialized_fill_n(finish.first, finish.cur - finish.first, value);
}
template<typename T, size_t buff_size>
void deque<T, buff_size>::create_map_and_nodes(size_t num_elements){
// the needed map node = (elements nums / chunk length) + 1
size_type num_nodes = num_elements / chunk_size() + 1;
// map node num。min num is 8 ，max num is "needed size + 2"
map_size = std::max(8, num_nodes + 2);
// allocate map array
map = mapAllocator::allocate(map_size);
// tmp_start，tmp_finish poniters to the center range of map
map_pointer tmp_start = map + (map_size - num_nodes) / 2;
map_pointer tmp_finish = tmp_start + num_nodes - 1;
// allocate memory for the chunk pointered by map node
for (map_pointer cur = tmp_start; cur <= tmp_finish; ++cur) {
*cur = dataAllocator::allocate(chunk_size());
}
// set start and end iterator
start.set_node(tmp_start);
start.cur = start.first;
finish.set_node(tmp_finish);
finish.cur = finish.first + num_elements % chunk_size();
}
청크 크기가 8 인 i_deque20 개의 int 요소 0~19가 있고 이제 3 개의 요소 (0, 1, 2)를 i_deque다음 과 같이 push_back 한다고 가정 합니다 .
i_deque.push_back(0);
i_deque.push_back(1);
i_deque.push_back(2);
아래와 같은 내부 구조입니다.
그런 다음 push_back을 다시 할당하면 새 청크 할당이 호출됩니다.
push_back(3)
만약 우리 push_front가 prev 이전에 새로운 덩어리를 할당 할 것이다.start
참고 push_back지도 및 청크 모두 채워진 경우 양단 큐에 요소, 그것은 새로운 맵을 할당 원인이, 당신이 이해하기 위의 코드가 충분히있을 수 있습니다 chunks.But을 조정합니다 deque.
표준은 특정 구현 (일정 시간 랜덤 액세스 만)을 요구하지 않지만, 일반적으로 deque는 연속 메모리 "페이지"모음으로 구현됩니다. 필요에 따라 새 페이지가 할당되지만 여전히 임의 액세스 권한이 있습니다. 와 달리 std::vector데이터가 연속적으로 저장된다고 약속하지는 않지만 벡터와 같이 중간에 삽입하려면 많은 재배치가 필요합니다.
Adam Drozdek가 "C ++의 데이터 구조 및 알고리즘"을 읽고 있는데 이것이 유용하다는 것을 알았습니다. HTH.
STL deque의 매우 흥미로운 측면은 구현입니다. STL deque는 링크 된 목록으로 구현되지 않고 데이터 블록 또는 배열에 대한 포인터 배열로 구현됩니다. 스토리지 수에 따라 블록 수가 동적으로 변경되고 그에 따라 포인터 배열의 크기가 변경됩니다.
가운데에는 데이터에 대한 포인터 배열 (오른쪽에 청크)이 있음을 알 수 있으며 가운데의 배열이 동적으로 변경되고 있음을 알 수 있습니다.
이미지는 천 단어의 가치가 있습니다.
참고 URL : https://stackoverflow.com/questions/6292332/what-really-is-a-deque-in-stl
'Programing' 카테고리의 다른 글
| 장고 : 로그인 후 이전 페이지로 리디렉션 (0) | 2020.05.28 |
|---|---|
| Enum의 values () 메서드에 대한 설명서는 어디에 있습니까? (0) | 2020.05.28 |
| 디렉토리를 비교하는 도구 (Windows 7) (0) | 2020.05.28 |
| 까다로운 Google 인터뷰 질문 (0) | 2020.05.28 |
| .git / config 파일에서 줄을 주석 처리 할 수 있습니까? (0) | 2020.05.28 |