침입 목록

침입 목록

나는 온라인에서 그들에 대한 너무 많은 정보를 찾을 수 없었다.그것들은 무엇이며 일반적으로 언제 사용되나?

고마워요.

얼마나 많은 사람들이 이것을 완전히 잘못 알고 있는지 놀랍다(지지의 대답 등).사람들은 일이 정말 간단할 때 지나치게 불평하는 것 같다.

침입식 링크 목록에는 명시적인 '노드' 구조체/클래스가 없다.대신 'Data' 구조체/클래스 자체는 링크된 목록의 다른 데이터에 대한 다음 및 사전 포인터/참조를 포함한다.

예: (내부적인 링크된 목록 노드):

struct Data { 
   Data *next; 
   Data *prev; 
   int fieldA; 
   char * fieldB; 
   float fieldC; 
}  

다음 및 이전 포인터가 어떻게 나란히 앉아 필드A와 같은 엔터티의 개인 데이터 필드를 침범하는지 주목하십시오.이러한 '위반'은 표준 연계 목록에 의해 시행되는 우려의 분리를 '위반'하지만(아래 참조) 특정 노드를 찾기 위한 목록 보행량을 크게 줄일 뿐만 아니라 메모리 할당량을 낮춘다는 장점이 있다.

침입식 링크 리스트에서, '링크된 리스트' 자체는 가상인 경우가 많으며, 일반적으로 링크된 리스트 구조체/클래스를 만들 필요가 전혀 없다.

대신 일부 소유자/관리자의 첫 번째 데이터 항목에 대한 헤드 포인터를 간단히 저장할 수 있다.또한 필요에 따라 포인터를 업데이트하기 위한 추가/제거 기능도 포함되어 있다.자세한 내용은 https://gameprogrammingpatterns.com/spatial-partition.html을 참조하십시오.

다음/사전 포인터의 한 쌍을 가지면 각 개체가 하나의 목록에만 속할 수 있다는 것을 나타낸다.그러나 물론 필요에 따라 여러 쌍의 다음/사전 포인터(next/prev pointer)를 추가(또는 다음/사전 포인터 배열을 정의)하여 여러 목록의 개체를 지원할 수 있다.

비침해적(즉, 표준) 연결 목록에서 다음/사전 포인터는 전용 '노드' 엔티티의 일부분이며 실제 데이터 엔티티는 단순히 해당 노드의 필드일 뿐이다.

예: (비침입적인 연결 목록 노드 및 데이터):

struct Data { 
   int fieldA; 
   char * fieldB; 
   float fieldC; 
}  

struct Node { 
   Node *next; 
   Node *prev; 
   Data *data; 
}  

다음/이전 포인터가 실제 데이터 엔터티에 침입하지 않고 우려의 분리가 유지되는 방법에 주목하십시오.

업데이트:

당신은 https://www.data-structures-in-practice.com/intrusive-linked-lists/과 같은 다른 사이트들이 '데이터' 구조체/클래스의 단일 침입 필드인 다음/하드 포인터를 포함하는 'List' 구조체(실제 노드)를 사용하는 것을 볼 수 있다.

This does hide the next/prev pointers from the Data, however it suffers from the need to perform pointer arithmetic simply to access the actual Data associated with the List (Node).

This approach adds needless complexity in my option (over simply embedding next/prev fields directly) just for the the dubious goal of hiding the next/prev pointers. If you need intrusive lists, keep them simple as possible. (Also, in managed memory languages it is difficult or impossible to do pointer arithmetic anyway.)

An intrusive list is one where the pointer to the next list node is stored in the same structure as the node data. This is normally A Bad Thing, as it ties the data to the specific list implementation. Most class libraries (for example, the C++ Standard Library) use non-intrusive lists, where the data knows nothing about the list (or other container) implementation.

I actually like the intrusive model.

1. It's better on memory (not many small allocations for things to point at other things)
2. It allows you to have an object that exist in multiple containers at once.
3. 하나의 검색 모드(해시)를 가진 요소를 찾을 수 있지만, 다음 요소를 어휘소 순서로 찾을 수 있다.
   • 이것은 #2와 같은 것은 아니지만, 부스트의 로는 성취할 수 있다. 그러나 유의하라.multi_index_container침입용기와는 무관한 어떤 단점을 가지고 있다.

Intrusive is GOOD

...you just need to know what you are doing (which is true for any container).

Intrusives lists are lists where objects are themselves heads or cells of lists. They are good or bad things depending of context.

Inside some defined module (unsecable group of classes working together) it may be the BEST mean to tie relationships between classes. They allow no-cost direct and full management of common relationships like unicity (ex: apples does not apears two times in appletrees, and this does not need any key for this, and apples does not belong to two distincts trees), they are navigable in both directions (direct accès to appletree given an apple and to apples given some appletree). All basic operations are O(1) (no search in some external container).

침입 목록은 두 모듈 사이에서 매우 나쁘다.왜냐하면 그들은 함께 묶일 것이고, 모듈 정당화는 코드 독립성 관리이기 때문이다.

다음은 목록에도 유효한 간략한 설명:

I. 침입 컨테이너.

저장할 객체는 컨테이너에 통합할 수 있도록 추가 정보를 포함하고 있다.예:

구조체 노드{노드* 다음, // 추가노드* 사전; // 정보T 데이터;}

1. 찬성:

• 물건을 직접 보관한다.


• 기억력 관리는 필요 없어


• 반복이 빠르다.
• 특례 보장
• 객체 삽입 및 삭제 시 예측 가능성.(추가 메모리 관리 필요 없음)
• 기억력이 좋아지다

2. 반대:

• 컨테이너 통합을 위한 추가 데이터 포함.(모든 스토어 유형은 컨테이너 요구 사항에 맞게 조정(수정)되어야 한다.)
• 저장된 개체의 내용을 변경할 때 가능한 부작용에 주의하십시오.(특히 연관 용기의 경우)
• 컨테이너와 독립적으로 삽입된 객체의 수명 관리.
• 컨테이너에서 객체를 삭제하기 전에 폐기할 수 있으며, 이는 반복기 무효화로 이어질 수 있다.
• 침입 컨테이너는 복사 불가 및 할당 불가.

II. 비인기용기(C++ 표준용기)

개체는 "알고" 있지 않으며 저장될 용기에 대한 세부 정보를 포함하고 있다.예:

구조체 노드{T 데이터;}

1. 찬성:

• 컨테이너 통합에 관한 추가 정보는 포함하지 않는다.
• 컨테이너에 의해 관리되는 개체의 수명.(더 복잡하지 않음

2. 반대:

• 사용자가 전달한 값의 복사본을 저장한다.(인플레이스 시공 가능)
• 물체는 하나의 용기에만 속할 수 있다.(또는 콘타이저는 물체에 포인터를 저장해야 한다.)
• 복사본의 보관 비용(각 할당에 대한 부기)
• 비복사 가능 또는 비복사 가능 객체는 비침해 용기에 저장할 수 없다.
• 파생 객체를 저장할 수 없고 원래의 유형을 유지할 수 없음.(변형 - 다형성)

참조URL: https://stackoverflow.com/questions/3361145/intrusive-lists