STL 集合部分操作

3.28更新

在EOJ 1641 集合栈计算机中，使用并集和补集时候，第五个参数使用x.begin()会报错：assignment of read-only location，而使用inserter(x,x.begin())就不会。没有声明过什么const，不知道为什么。

如果x是vector，那么需要预留大小，否则将会segmentation fault，这个下面已经提到。

上面题目中是set，查阅得到这句话：“由于set内部是默认排序的，所以我们不能直接改变set关键字的值(set中的关键字是只读的)”

inserter的文档：

Constructs an insert iterator that inserts new elements into x in successive locations starting at the position pointed by it.

An insert interator is a special type of output iterator designed to allow algorithms that usually overwrite elements (such ascopy) to instead insert new elements automatically at a specific position in the container.

The type of x needs to have aninsert member function (such as most standard containers).

Using the assignment operator on the returned iterator (either dereferenced or not), causesinsert to be called on the container, attempting to insert one element at the current insert position with the value assigned. This effectively expands the container by one element when successful.

The returned iterator supports all other typical operations of output iterators but have no effect: all values assigned are inserted at the current insert position - which is it after this function is called, and is incremented after each new insertion caused by an assignment to the iterator.

同时，set_intersection的文档提中，第五个参数是

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
bool cmp(int a,int b){return a<b;}
int main()
{
    int T=11;
    set<int> j;
    set<int> s= {10,15,20,25},k={10,20,40,50};
    set<int>::iterator it;
    set_intersection(s.begin(),s.end(),k.begin(),k.end(),inserter(j,j.begin()));
    for(int x:j)    cout<<x<<" ";
    return 0;
}

输出结果：10，20//如果改成j.begin()出现前文提到的错误。

同时，添加*j.begin()=1;也会出现上述错误，问题应该出在set_intersection对第五个参数处理的方法上

template <class InputIterator1, class InputIterator2, class OutputIterator>
  OutputIterator set_intersection (InputIterator1 first1, InputIterator1 last1,
                                   InputIterator2 first2, InputIterator2 last2,
                                   OutputIterator result)
{
  while (first1!=last1 && first2!=last2)
  {
    if (*first1<*first2) ++first1;
    else if (*first2<*first1) ++first2;
    else {
      *result = *first1;//这里
      ++result; ++first1; ++first2;
    }
  }
  return result;
}

而inserter应该相当于一次insert，通过调用insert()成员函数来插入元素，并由用户指定插入位置，不至于尝试更改键值这种操作。

template <class Container, class Iterator>
  insert_iterator<Container> inserter (Container& x, Iterator it);xContainer on which the iterator will insert new elements.
Container should be a container class with memberinsert defined.itIterator pointing to the insertion point.

This shall be a mutable iterator (not a const iterator).

 

---

 

set_intersection

default (1)	template <class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_intersection (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
custom (2)	template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> OutputIterator set_intersection (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);

求两个(已排序)集合的交集。

构造一个排序的范围，从result的位置开始，然后是两个排序范围的集合的交集[first1,last1]和[first2,last2)。

两个集合的交集只由两个集合中的元素组成。由函数复制的元素总是以相同的顺序从第一个范围开始。

默认升序排列，也可以用comp自定义。两个元素，a和b被认为是相等的，如果(!(a<b) && !(b<a)或if (!comp(a,b) && !comp(b,a))。

范围内的元素已经按照相同的标准(操作符<或comp)排序。结果的范围也根据这个排序。

 

1.    　前四个参数，可以是迭代器(vector,set)的首尾，也可以是数组的首尾，只要是有序的区间均可注意区间均为左闭右开。

2.　　第五个参数，可以是vector（注意一定要预留大小！用it取得set_intersection的返回值后再resize），也可以是数组。

3.　　compare函数自己编写

// set_intersection example
#include <iostream>     // std::cout
#include <algorithm>    // std::set_intersection, std::sort
#include <vector>       // std::vector

int main () {
  int first[] = {5,10,15,20,25};
  int second[] = {50,40,30,20,10};
  std::vector<int> v(10);                      // 0  0  0  0  0  0  0  0  0  0
  std::vector<int>::iterator it;

  std::sort (first,first+5);     //  5 10 15 20 25
  std::sort (second,second+5);   // 10 20 30 40 50

  it=std::set_intersection (first, first+5, second, second+5, v.begin());
                                               // 10 20 0  0  0  0  0  0  0  0
  v.resize(it-v.begin());                      // 10 20

  std::cout << "The intersection has " << (v.size()) << " elements:
";
  for (it=v.begin(); it!=v.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '
';

  return 0;
}

set_union

求并集，方法和注意点与上面相同

set_difference

求差集，同上

merge

// merge algorithm example
#include <iostream>     // std::cout
#include <algorithm>    // std::merge, std::sort
#include <vector>       // std::vector

int main () {
  int first[] = {5,10,15,20,25};
  int second[] = {50,40,30,20,10};
  std::vector<int> v(10);

  std::sort (first,first+5);
  std::sort (second,second+5);
  std::merge (first,first+5,second,second+5,v.begin());

  std::cout << "The resulting vector contains:";
  for (std::vector<int>::iterator it=v.begin(); it!=v.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '
';

  return 0;
}

合并两个有序区间