중복 : 나는 그것이 중복 삽입 할 수 있습니다뿐만 아니라 항목이 삽입 된 순서를 알고하지 않습니다에서 설정 같은 역할을하는 데이터 구조를 찾고 있어요Choosing a STL container with uniqueness and which keeps insertion ordering중복을 허용하지 않고 입력 순서를 유지하는 데이터 구조가 있습니까?
. 기본적으로 집합과 목록/벡터의 조합입니다.
목록/벡터를 사용하여 중복 된 항목을 직접 확인하지만 구조의 크기가 커질 수 있으므로 복제 확인이 빨리 필요합니다.
Boost.MultiIndex을 살펴보십시오. 이것에 대한 래퍼를 작성해야 할 수도 있습니다.
벡터와 세트를 래핑하는 클래스를 작성하는 것이 확실한 해결책으로 보일 것입니다. 원하는 작업을 수행하는 C++ 표준 라이브러리 컨테이너가 없습니다.
나는 단지 두 개의 데이터 구조를 사용한다. 하나는 순서와 하나는 신원 정보이다. (어떤 작업을 가장 빨리 할 것인지에 따라 값을 저장하는 경우 하나를 가리킬 수 있음)
OrderedDictionary의 작업과 비슷하게 들립니다.
빠른 중복 검사가 여기에 중요합니다. 어쩌면지도/사전의 일부 유형을 사용하고 삽입 순서를 실제 데이터로 추적 할 수 있습니다. 그래서 열쇠는 당신이 밀어 넣고있는 "데이터"입니다 (그리고 나서 해시되고, 중복 키를 허용하지 않습니다). 그리고지도의 현재 크기를 "데이터"로 넣습니다. 물론 이것은 삭제되지 않은 경우에만 작동합니다. 필요하다면, 삽입 할 때마다 증가하는 외부 변수를 갖게되고, 상대 순서는 삽입 된 시점을 알려줍니다.
예쁜 것은 아니지만 구현하기가 어렵지는 않습니다.
Boost.Bimap 삽입 순서를 색인으로 사용해야합니다 (예 : boost :: bimap < size_t, Foo>). 데이터 구조에서 개체를 제거하는 경우 다음 삽입 순서 값을 개별적으로 추적해야합니다.
여기서 ANSI C++을 사용한다고 가정하면 필자는 직접 작성하거나 구성 및 위임을 사용하여 데이터 저장을위한 맵과 삽입 순서에 대한 키 벡터를 래핑합니다. 데이터의 특성에 따라 삽입 색인을지도 키로 사용하고 벡터 사용을 피할 수 있습니다.
Java는 순서가 지정된 세트 형식입니다. 나는 C++이 가지고있는 것은 아니지만 자신을 구현하는 것이 어렵지 않습니다. Sun 클래스가 Java 클래스에서 한 것은 해시 테이블을 확장하여 각 항목을 해시 테이블에 동시에 삽입하고 이중 링크 목록에 보관하는 것이 었습니다. 특히 링크 된 목록을 구성하는 데 사용되는 항목을 미리 할당하는 경우 오버 헤드가 거의 없습니다.
내가 어디에 있든, 개인 벡터를 사용하여 항목을 저장하거나 클래스의 해시 테이블을 직접 구현하는 클래스를 작성합니다. 어떤 항목이 세트에 삽입 될 때, 그것이 해시 테이블에 있는지 확인하고, 그 안에 항목이 있으면 그 안에있는 항목을 선택적으로 바꿉니다. 그런 다음 해시 테이블에서 이전 항목을 찾고 새 요소를 가리 키도록 목록을 업데이트하면 완료됩니다.
새 요소를 삽입하려면 목록에서 새 요소를 사용해야한다는 점을 제외하고는 이전 요소를 다시 사용할 수 없습니다.
항목을 삭제하려면 목록을 가리키고 목록 요소를 비 웁니다.
관심있는 요소가 요소에서 직접 나오는 링크 된 목록의 일부를 가져와야하므로 이동하거나 이동할 때마다 체인을 걷지 않아도됩니다. 요소를 변경하십시오.
프로그램 실행 중에 이러한 항목이 많이 변경 될 것으로 예상되는 경우 목록 항목의 목록을 유지하여 매번 메모리를 할당하는 대신이 목록의 머리를 차지할 수 있습니다 새로운 요소를 추가해야합니다.
춤 링크 알고리즘을 살펴볼 수 있습니다.
중복 질문의 Greg 솔루션에 래퍼가 필요하지 않은 것 같습니다. 가장 고통스러운 방향으로 나를 가르쳐 주셔서 감사합니다. –