`std::set`에 어떤 문제가 있나요?

StackOverflow https://stackoverflow.com/questions/5397616

문제

~ 안에 다른 주제 해결하려고 했는데 이것 문제.문제는 중복된 문자를 제거하는 것이었습니다. std::string. 

std::string s= "saaangeetha";

순서가 중요하지 않아서 정리했어요 s 먼저 사용한 다음 사용 std::unique 마침내 크기를 조정하여 원하는 결과: 

aeghnst

맞아요!

이제 동일한 작업을 수행하고 싶지만 동시에 문자 순서가 그대로 유지되기를 원합니다.즉, 나는 다음과 같은 출력을 원합니다.

sangeth

그래서 나는 썼다 이것:

template<typename T>
struct is_repeated
{
    std::set<T>  unique;
    bool operator()(T c) { return !unique.insert(c).second; }
}; 
int main() {
    std::string s= "saaangeetha";
    s.erase(std::remove_if(s.begin(), s.end(), is_repeated<char>()), s.end()); 
    std::cout << s ;
}

다음과 같은 출력이 제공됩니다.

saangeth

그건, a 다른 반복은 사라졌지만 반복됩니다.코드에 어떤 문제가 있나요?

어쨌든 나는 내 코드 변경 약간:(댓글 참조)

template<typename T>
struct is_repeated
{
    std::set<T> & unique;  //made reference!
    is_repeated(std::set<T> &s) : unique(s) {} //added line!
    bool operator()(T c) { return !unique.insert(c).second; }
}; 
int main() {
    std::string s= "saaangeetha";
    std::set<char> set; //added line!
    s.erase(std::remove_if(s.begin(),s.end(),is_repeated<char>(set)),s.end()); 
    std::cout << s ;
}

산출:

sangeth

문제가 사라졌습니다!

그렇다면 첫 번째 해결책에는 무엇이 문제인가요?

또한 멤버 변수를 만들지 않으면 unique 참조 유형 문제는 해결되지 않는다.

무엇이 문제인가? std::set 또는 is_repeated 펑터?문제가 정확히 어디에 있습니까?

나는 또한 다음과 같은 경우에 참고합니다. is_repeated functor가 어딘가에 복사된 다음 해당 함수의 모든 구성원도 복사됩니다.여기서는 문제가 보이지 않습니다!

도움이 되었습니까?

해결책

GCC(libstdc++)에서, remove_if 본질적으로 다음과 같이 구현됩니다.

    template<typename It, typename Pred>
    It remove_if(It first, It last, Pred predicate) {
      first = std::find_if(first, last, predicate);
    //                                  ^^^^^^^^^
      if (first == last)
         return first;
      else {
         It result = first;
         ++ result;
         for (; first != last; ++ first) {
           if (!predicate(*first)) {
    //          ^^^^^^^^^
              *result = std::move(*first);
              ++ result;
           }
         }
      }
    }

조건자가 전달되었습니다. 가치 기준 에게 find_if, 따라서 구조체와 집합이 내부에서 수정되었습니다. find_if 호출자에게 다시 전파되지 않습니다.

첫 번째 복제본이 다음에 나타나기 때문에:

  saaangeetha
//  ^

처음의 "sa" 이후에도 보관됩니다 find_if 부르다.한편, predicate의 세트가 비어 있습니다( find_if 현지입니다).따라서 이후 루프는 3번째를 유지합니다. a.

   sa | angeth
// ^^   ^^^^^^
// ||   kept by the loop in remove_if
// ||
// kept by find_if

다른 팁

Functor는 Functor의 복사본이 원본 Functor와 동일한 방식으로 설계되어야 합니다.즉, 하나의 펑터를 복사한 다음 일련의 작업을 수행하는 경우 어떤 펑터를 사용하든지 또는 두 펑터를 인터리브하더라도 결과는 동일해야 합니다.이는 STL 구현에 펑터를 복사하고 적절하다고 판단되는 대로 전달할 수 있는 유연성을 제공합니다.

첫 번째 펑터의 경우 이 주장은 유지되지 않습니다. 펑터를 복사한 다음 호출하면 저장된 세트에 대한 변경 사항이 원본 펑터에 반영되지 않아 복사본과 원본이 다르게 수행되기 때문입니다.마찬가지로, 두 번째 펑터를 가져와 참조로 세트를 저장하지 않도록 설정하면 펑터의 두 복사본이 동일하게 동작하지 않습니다.

하지만 최종 버전의 펑터가 작동하는 이유는 세트가 참조로 저장된다는 사실이 tue 펑터의 복사본이 서로 동일하게 동작한다는 것을 의미하기 때문입니다.

도움이 되었기를 바랍니다!

실제로 대답은 아니지만 고려해야 할 또 다른 흥미로운 정보로서 원래 펑터를 사용하더라도 작동합니다.

#include <set>
#include <iostream>
#include <string>
#include <algorithm>
#include <iterator>

template<typename T>
struct is_repeated {
    std::set<T>  unique;
    bool operator()(T c) { return !unique.insert(c).second; }
}; 
int main() {
    std::string s= "saaangeetha";
    std::remove_copy_if(s.begin(), s.end(), 
                        std::ostream_iterator<char>(std::cout), 
                        is_repeated<char>());
    return 0;
}

편집하다:나는 이것이 이 동작에 영향을 미치지 않는다고 생각하지만 펑터의 사소한 실수도 수정했습니다(operator()는 분명히 T 유형의 매개변수를 취해야 합니다. char).

문제는 is_repeated functor는 구현 내부 어딘가에 복사됩니다. std::remove_if.이 경우 기본 복사 생성자가 사용되며 이는 차례로 다음을 호출합니다. std::set 복사 생성자.넌 결국 2개로 끝나 is_repeated 펑터는 독립적으로 사용될 수 있습니다.그러나 둘 다의 세트는 별개의 객체이므로 상호 변경 사항을 볼 수 없습니다.분야를 바꾸면 is_repeated::unique 참조에 추가하면 복사된 펑터는 이 경우에 원하는 원본 세트를 계속 사용합니다.

Functor 클래스는 순수 함수여야 하며 자체 상태가 없어야 합니다.Scott Meyer의 항목 39를 참조하세요. 효과적인 STL 이에 대한 좋은 설명이 있는 책.그러나 요점은 functor 클래스가 알고리즘 내에서 1회 이상 복사될 수 있다는 것입니다.

다른 대답은 정확합니다. 문제는 사용중인 펑터가 그렇지 않다는 것입니다. 복사 가능 안전한.특히, gcc(4.2)와 함께 제공되는 STL은 다음을 구현합니다. std::remove_if 의 조합으로 std::find_if 삭제할 첫 번째 요소를 찾고 그 뒤에 std::remove_copy_if 작업을 완료합니다. 

template <typename ForwardIterator, typename Predicate>
std::remove_if( ForwardIterator first, ForwardIterator end, Predicate pred ) {
   first = std::find_if( first, end, pred ); // [1]
   ForwardIterator i = it;
   return first == last? first 
          : std::remove_copy_if( ++i, end, fist, pred ); // [2]
}

[1]의 복사본은 발견된 첫 번째 요소가 펑터의 복사본에 추가되고 첫 번째 'a'가 망각됨을 의미합니다.펑터는 [2]에도 복사되며, 해당 복사본의 원본은 빈 펑터이기 때문에 그렇지 않은 경우에도 괜찮을 것입니다.

구현 여부에 따라 remove_if 술어의 사본을 만들 수 있습니다.펑터를 리팩터링하고 무상태로 만들거나 다음을 사용하세요. 부스트.참조 "일반적으로 인수의 복사본을 가져오는 함수 템플릿(알고리즘)에 대한 참조를 전달하기 위해" 다음과 같이:

#include <set>
#include <iostream>
#include <string>
#include <algorithm>
#include <iterator>

#include <boost/ref.hpp>
#include <boost/bind.hpp>

template<typename T>
struct is_repeated {
    std::set<T>  unique;
    bool operator()(T c) { return !unique.insert(c).second; }
}; 

int main() {
    std::string s= "saaangeetha";
    s.erase(std::remove_if(s.begin(), s.end(), boost::bind<bool>(boost::ref(is_repeated<char>()),_1)), s.end());
    std::cout << s;

    return 0;
}
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top