std :: inserter với bộ - chèn để bắt đầu() hoặc kết thúc()?

Question

Tôi có một số mã mà trông như thế này:

std::set<int> s1, s2, out; 

// ... s1 and s2 are populated ... 

std::set_intersection(s1.begin(), s1.end(), 
         s2.begin(), s2.end(), 
         std::inserter(out, out.end())); 

Tôi đã chèn đọc có thể được thực hiện trong thời gian liên tục khấu hao nếu giá trị được chèn vào tập ngay sau iterator được coi là một "gợi ý". Điều này rõ ràng sẽ mang lại lợi ích khi chạy giao lộ được thiết lập, đặc biệt là vì mọi thứ được ghi vào out đã được sắp xếp theo thứ tự sắp xếp.

Làm cách nào để đảm bảo hiệu suất tối ưu này? Khi tạo std::inserter, out bị trống để out.begin() == out.end() vì vậy tôi không thể thấy nó có khác biệt gì dù tôi chỉ định out.begin() hoặc out.end() làm gợi ý. Tuy nhiên, nếu điều này được giải thích khi chèn mọi phần tử tại begin(), có vẻ như tôi sẽ không nhận được hiệu suất thuật toán tối ưu. Điều này có thể được thực hiện tốt hơn?

Answer 1

Bạn có thể sử dụng hàm tùy chỉnh thay vì std::inserter và gọi lại out.end() mỗi lần chèn phần tử mới.

Hoặc, nếu giá trị của bạn được sắp xếp giảm dần, out.begin() sẽ không sao.

Answer 2

Tôi đã chọn câu trả lời của Alexander Gessler là câu trả lời 'chính xác', bởi vì nó dẫn tôi đến giải pháp này, mà tôi nghĩ tôi sẽ đăng bài. Tôi đã viết một last_inserter(), đảm bảo rằng vị trí chèn luôn là một biến lặp cho phần tử cuối cùng (hoặc bắt đầu() nếu trống), vì set muốn một trình lặp đến phần tử trước vị trí chèn thực tế cho hiệu suất tốt nhất không kết thúc() - đó sẽ là một sau vị trí chèn thực tế).

Việc sử dụng theo các ví dụ ban đầu là như thế này:

std::set<int> s1, s2, out; 

// ... s1 and s2 are populated ... 

std::set_intersection(s1.begin(), s1.end(), 
         s2.begin(), s2.end(), 
         last_inserter(out)); // note no iterator provided 

Điều này đảm bảo rằng các gợi ý chèn luôn luôn là một iterator tới phần tử cuối cùng, hy vọng cung cấp hiệu suất hợp cụ tốt nhất khi sử dụng một iterator đầu ra vào một thiết lập với một phạm vi được sắp xếp, như trên.

Dưới đây là triển khai của tôi. Tôi nghĩ rằng đó là nền tảng cụ thể để thực hiện STL Visual C++ 2010, bởi vì nó dựa rất nhiều vào hiện tại insert_iterator, và tôi chỉ có thể làm cho nó hoạt động bằng cách bắt nguồn từ std::_Outit. Nếu có ai biết làm thế nào để làm cho di động này, cho tôi biết:

// VC10 STL wants this to be a checked output iterator. I haven't written one, but 
// this needs to be defined to silence warnings about this. 
#define _SCL_SECURE_NO_WARNINGS 

template<class Container> 
class last_inserter_iterator : public std::_Outit { 
public: 
    typedef last_inserter_iterator<Container> _Myt; 
    typedef Container container_type; 
    typedef typename Container::const_reference const_reference; 
    typedef typename Container::value_type _Valty; 

    last_inserter_iterator(Container& cont) 
     : container(cont) 
    { 
    } 

    _Myt& operator=(const _Valty& _Val) 
    { 
     container.insert(get_insert_hint(), _Val); 
     return (*this); 
    } 

    _Myt& operator=(_Valty&& _Val) 
    { 
     container.insert(get_insert_hint(), std::forward<_Valty>(_Val)); 
     return (*this); 
    } 

    _Myt& operator*() 
    { 
     return (*this); 
    } 

    _Myt& operator++() 
    { 
     return (*this); 
    } 

    _Myt& operator++(int) 
    { 
     return (*this); 
    } 

protected: 
    Container& container; 

    typename Container::iterator get_insert_hint() const 
    { 
     // Container is empty: no last element to insert ahead of; just insert at begin. 
     if (container.empty()) 
      return container.begin(); 
     else 
     { 
      // Otherwise return iterator to last element in the container. std::set wants the 
      // element *preceding* the insert position as a hint, so this should be an iterator 
      // to the last actual element, not end(). 
      return (--container.end()); 
     } 
    } 
}; 

template<typename Container> 
inline last_inserter_iterator<Container> last_inserter(Container& cont) 
{ 
    return last_inserter_iterator<Container>(cont); 
} 

Answer 3

Theo http://gcc.gnu.org/onlinedocs/gcc-4.8.0/libstdc++/api/a01553_source.html

insert_iterator& 
operator=(typename _Container::value_type&& __value) 
{ 
    iter = container->insert(iter, std::move(__value)); 
    ++iter; 
    return *this; 
} 

đâu iter ban đầu chỉ vào các iterator bạn truyền cho std::inserter. Vì vậy, lặp sẽ luôn luôn trỏ đến một trong quá khứ giá trị bạn vừa chèn và nếu bạn đang chèn theo thứ tự, nên được tối ưu hiệu quả.