如何從stl :: vector或list中選擇一個子集？

Question

C++大師：

有相當一些有用的c + + stl算法，如查找或搜索。但是，他們似乎只返回一個interator。

如果我想爲STL容器做一個SQL樣式'選擇'會怎樣？例如，一個矢量（可能會擴展到列表或地圖）。像

std::pair<vector::iterator, vector::iterator> select(std::vector::iterator begin, std::vector::iterator end, Comparor equal_to) 

輸出應該是一個範圍，像一個std ::對，這是類同的升壓::多指標

方法的返回值是有這樣的事在stl？或任何可靠的類似文件？

Answer 1

主要通過兩種途徑：

1）您的評論說上面寫指着）的結果爲迭代器的容器（迭代器的東西。那將是這個樣子：

template <typename ForwardIterator, typename OutputIterator, typename UnaryPredicate> 
void select_iterators(ForwardIterator first, ForwardIterator last, 
         OutputIterator out, UnaryPredicate pred) { 
    while (first != last) { 
     if pred(*first) *out++ = first; 
     ++first; 
    } 
} 

然後你把它想：

vector<Foo> myfoos; 
vector<vector<Foo>::iterator> results; 
select_iterators(myfoos.begin(), myfoos.end(), std::back_inserter(results), some_comparator); 

其實你可以在其它的算法來定義select_iterators，使用copy_if和boost::counting_iterator，但我不認爲當直接實施如此簡單時，這是值得的。它看起來像：

template <typename ForwardIterator, typename OutputIterator, typename UnaryPredicate> 
void select_iterators(ForwardIterator first, ForwardIterator last, 
         OutputIterator out, UnaryPredicate pred) { 
    std::copy_if(
     boost::make_counting_iterator(first), 
     boost::make_counting_iterator(last), 
     out, 
     [&](ForwardIterator it) { return pred(*it); } 
    ); 
} 

2）替代了前測試所有的價值觀和地方將結果寫的，定義每次遞增，直到找到下一場比賽的時間比原先的範圍內推進的迭代器。 Boost提供了兩種這樣做的方式，boost::filter_iterator和boost::adaptors::filter。所以，你可以寫：

auto results = boost::adaptors::filter(myfoos, some_comparator); 

那麼無論你想與你的結果，這樣做，你可以遍歷從results.begin()到results.end()就好像它是一個容器。它不是一個容器，它不能滿足整個容器的界面。它滿足由Boost定義的名爲Range的接口，該接口相當於「可以迭代」。它實際上只是myfoos的過濾視圖，因此沒有Foo對象被複制或移動。

Answer 2

你可能會尋找boost::range

一個boost::range實際上是一對迭代定界範圍的容器的元素組成。該庫包含各種算法，這些算法返回範圍（如容器中的等效值範圍，用戶提供的等價函子）的範圍。

Answer 3

如果你可以修改你的矢量std::partition將是選擇。在這裏你會如何稱呼它：

std::vector<int>::iterator p = 
    std::partition(v.begin(), v.end(), you_predicate); 

你v.begin()和p之間的答案所在。

Answer 4

template<typename ForwardIterator, typename OutputIterator, typename UnaryPredicate> 
    void find_elements(ForwardIterator first, ForwardIterator last, OutputIterator out, UnaryPredicate pred) 
    { 
     while(first != last) 
     { 
      if(pred(*first)) 
       *out++ = first; 
      ++first; 
     } 
    } 

事情要記住：

1）你說，你希望你的容器是iterator而非const_iterator。該類型將與傳遞給函數的開始和結束範圍相同。例如，如果您使用vector::cbegin和vector::cend，則該類型將爲容器的const_iterator，如果您使用不同的迭代器（例如vector::begin和vector::cend），則該類型將不會編譯爲const_iterator。

2.）矢量經常失去它們的迭代器有效性，所以要小心使用這些迭代器。例如，如果添加到向量中，則此函數返回的每個迭代器都可能無效。要防止出現這種情況，請使用不同的容器（例如列表）或使用vector::reserve。

3.）前向迭代器必須是支持++的東西，並且在取消引用時，具有與InputIterator相同的類型（例如vector<int>::iterator）。在遞增它之後，它也必須保持有效的迭代器，否則該函數將毫無意義。輸出迭代器必須到足夠空間的地方來容納所有發現的迭代器pred。如果您事先不知道該空間，則可以使用<iterator>中的std::back_inserter與定義了container::push_back的容器，並且該容器將根據需要增長。

這是一個測試你的功能，瞭解它是如何工作的。

int main() 
{ 
    vector<string> ss = {"hi", "yog", "engils", "pog"}; 

    // Define a predicate 
    auto isSizeThree = [](string const &s) 
    { 
     return s.size() == 3; 
    }; 

    // example one: Somehow I know how many satisfy the predicate. I just don't know where they are. 
    vector<vector<string>::iterator> answer(2); 
    find_elements(begin(ss), end(ss), begin(answer), isSizeThree); 

    // Check answer 
    cout << "Test 1" << endl; 
    for(auto entry : answer) 
     cout << *entry << endl; 

    // Example two: I don't know how many there will be (more typical). If I use a continer with stuff in it - it will stack right on the back of it! 
    find_elements(begin(ss), end(ss), back_inserter(answer), isSizeThree); 

    // Check answer (has the answer from test 1 still in it) 
    cout << "Test 2" << endl; 
    for(auto entry : answer) 
     cout << *entry << endl; 

    // Example Three: Same as test 2 but clear the ansewr vector first. 
    answer.clear(); 
    find_elements(begin(ss), end(ss), back_inserter(answer), isSizeThree); 

    // Check answer 
    cout << "Test 3" << endl; 
    for(auto entry : answer) 
     cout << *entry << endl; 
}