stl set_symmetric_difference的时间复杂度

Question

我在读stl 差异的时间复杂性。

上面写着：

直到线性in 2*(count1+count2)-1 (其中countX是firstX和lastX之间的距离)：比较和赋值元素。

我对"countX是firstX和lastX之间的距离“这句话感到困惑。

请举例说明。

Answer 1

我对"countX是firstX和lastX之间的距离“这句话感到困惑。

从链接到的同一页面上的示例中：

first1, last1 将迭代器输入到第一个排序序列的初始和最终位置。>使用的范围是[ first1，last1)，它包含first1 >和last1之间的所有元素，包括first1指向的元素，而不是last1指向的元素。 first2, last2 将迭代器输入到第二排序序列的初始和最终位置。使用的范围是[first2，last2]。

因此，count是表示数据结构中的第一个和最后一个元素的迭代器排序元素之间的std::distance (即跳数)(示例中的数组)。对于第一个(排序：5 10 15 20 25)，为5。

至于std::distance

线性的。 但是，如果InputIt额外地满足了RandomAccessIterator的要求，那么复杂性是恒定的。