아래 언급 된 목적을 해결되도록 (++ C에서)

Question

는 적절한 데이터 구조를 제안 ++ C에 적합한 데이터 구조를 검색 :

1. 끝까지 요소를 삽입한다.
2. 끝에있는 요소를 읽고 삭제하십시오.
3. 요소를 처음부터 읽고 삭제합니다.
4. 특정 요소가 있는지 알아보십시오.

지금은 벡터를 사용하고 있지만 특정 요소가 있는지 찾는 작업은 벡터에서 시간이 많이 걸리며 요소는 정렬되지 않습니다.

벡터를 구현하는 데 더 좋은 데이터 구조가 있습니까? 예. 그렇다면 어느 것이고 예를 들어주십시오.

Answer 1

기본적으로 해시 테이블 인 std::set 또는 std::unordered_set을 사용하고 요소 간 순서를 유지할 수 있습니다. 이것은 처음부터 끝까지 O (log (n)) 또는 amortized O (1) 조회 복잡성과 일정한 삽입/삭제를 제공합니다. Java에서는 이것을 LinkedHashSet이라고합니다. 안타깝게도 STL은 이러한 종류의 데이터 구조를 기본적으로 제공하지 않지만 set/unordered_set 또는 map/unordered_map 위에 쉽게 구현해야합니다.

template <typename T> 
class linked_set { 
private: 
    // Comparator of values with dereferencing. 
    struct value_deref_less { 
    bool operator()(const T *lhs, const T *rhs) const { 
     return *lhs < *rhs; 
    } 
    }; 

    typedef std::set<const T*, value_deref_less> Set; 
    Set set_;    // Used for quick lookup 
    std::deque<T> store_; // Used for ordered storage. deque is used instead of 
         // vector because the former doesn't invalidate 
         // pointers/iterators when elements are pushed. 

public: 
    void push_back(const T& value) { 
    store_.push_back(value); 
    set_.insert(&store_.back()); 
    // TODO: handle the case of duplicate elements. 
    } 

    // TODO: better provide your own iterator. 
    typedef typename Set::iterator iterator; 

    iterator find(const T& value) { return set_.find(&value); } 

    // ... 
}; 

Answer 2

std::deque을 사용하십시오. 이것은 양단 큐이며, std::stack과 같은 표준 인터페이스의 컨테이너로도 사용됩니다.

일반적으로 준 링크 목록 구현을 사용하며 가장자리의 삽입 및 삭제시 O (1) 시간 복잡도를 상각합니다.

Answer 3

로그 복잡성이 적합한 지 확인하려면 std::map으로 시작해야합니다.

B + Tree는 좀 더 복잡하고 오픈 소스 구현을 찾기 위해 독자적인 구현이나 연구가 필요합니다. 그러나 std::map이 여전히 부적절한 것으로 판명 된 경우 요구 사항과 인용 지점을 고려한 합리적인 선택입니다 (검색).

예를 들어 요소의 값을 std::list의 반복기에 매핑합니다. 모든 작업은 std::map으로 O (lg n)가됩니다.

Answer 4

vector을 유지할 수도 있지만 빠른 쿼리에는 std::set을 사용할 수 있습니다.

삽입 된 첫 번째/마지막 요소가 실제로는 알 수 없으므로 세트는 시작/끝에서 요소를 삭제하기에 충분하지 않습니다. 이러한 요소에 대한 참조를 유지할 수는 있지만 삭제를 지원하려면 다음 컨테이너를 필요로하므로 컨테이너가 하나 더 줄어들어 저하됩니다.

Answer 5

하는 당신은 당신이 제한 적어도 경우, 동일한 컨테이너에 양측에서 빠른 삽입과 빠른 검색 모두를 가질 수 없습니다 : 여기

는 아이디어를 보여 코드 조각이다 STL에 대한 가능성. 더 많은 이국적인 비표준 컨테이너가 도움이 될 수 있습니다.

그러나 일반적으로 이러한 경우에 선택하는 방법은 두 개의 컨테이너를 사용하는 것입니다. 요소를 저장하기 위해 명백한 옵션은 std :: deque입니다.검색하려면 std::map<K,V>을 만들고 V는 양면 큐의 반복자입니다. deques의 삽입/삭제가 관련되지 않은 반복자를 무효화하지 않기 때문에 항상 맵과 양면 큐를 동기화하는 것을 기억한다면 (예를 들어 양키 큐를 삽입하거나 삭제할 때 맵에서도 수행하십시오) . 반복자를 사용하는 대신에 더 간단하고 안전한 옵션 - 맵에서 검색 한 후에 발견 된 요소 만 있으면 (근처 요소 등을 방문 할 필요가 없음) - 양면 점과 맵 모두에 있어야합니다. 실제 객체 (특히 shared_ptr)에 대한 스마트 포인터. 다시 말하지만, 당신은 조심해야합니다 둘 다 동기화 유지; 동기화가 느슨한 경우 큰 재앙이되지는 않지만, 물론 프로그램의 일관성이 손상 될 것입니다.

struct MyItem 
{ 
    std::string name; 
    int something; 
    int another; 
    MyItem(const std::string &name_, int something_, int another_) 
     :name(name_), something(something_), another(another_) {} 
}; 

class MyContainer 
{ 
    public: 
     typedef std::shared_ptr<MyItem> MyItemPtr; 

     void push_front(MyItemPtr item) 
     { 
      deque.push_front(item); 
      assert(map.find(item->name) == map.end()); 
      map[item->name] = item; 
     } 
     void push_back(MyItemPtr item) 
     { 
      deque.push_back(item); 
      assert(map.find(item->name) == map.end()); 
      map[item->name] = item; 
     } 
     MyItemPtr pop_front() 
     { 
      item = deque.front(); 
      deque.pop_front(); 
      map.erase(item->name); 
      return item; 
     } 
     MyItemPtr pop_back() 
     { 
      item = deque.back(); 
      deque.pop_back(); 
      map.erase(item->name); 
      return item; 
     } 
     MyItemPtr find(const std::string &name) 
     { 
      std::map<std::string, MyItemPtr>::iterator iter = map.find(name); 
      if (iter == map.end()) 
       return MyItemPtr(); 
      else 
       return iter->second; 
     } 

    private: 
     std::deque<MyItemPtr> deque; 
     std::map<std::string, MyItemPtr> map; 
}; 

를 사용하려면 :

MyContainer container; 

MyContainer::MyItemPtr a(new MyItem("blah", 1, 2)); 
container.push_back(a); 
MyContainer::MyItemPtr b(new MyItem("foo", 5, 6)); 
container.push_front(b); 

MyContainer::MyItemPtr f = container.find("blah"); 
if (f) 
    cout << f->name << ", " << f->something << ", " << f->another; 

Answer 6

을 삽입 많은이있는 경우/연결리스트가 더 적합 할 것입니다 삭제합니다.
링크 된 목록 (단일 또는 이중)은 상당한 오버 헤드 (일반적으로 포인터의 크기이지만 구현은 다양 함)를 가지므로주의하십시오.

표준 템플릿 라이브러리는 std :: list를 제공합니다.