39

在调试某些东西时,我看到了 STL vector::empty() 实现:

bool empty() const
        {return (size() == 0); }

我相信,每当我们探测向量的空性时,总是建议使用空的大小()。但是看到这个实现,我想知道,这样做有什么好处?相反,在调用 empty 时会产生函数调用开销,因为它在内部调用 size()==0。

我认为 empty() 在列表的情况下可能会有所帮助,因为 size() 不能保证列表中的恒定时间。为了验证我的假设,我检查了列表实现,令人惊讶的是,在列表中也发现了相同的实现,

return (size() == 0);

我现在有点困惑。如果 empty 内部使用 size() 那么我们为什么更喜欢 empty 而不是 size() ?

4

9 回答 9

45

因为如果你从 std::vector 切换到 std::list 或其他容器,它可能会有所不同。

例如std::list::sizetakeO(n)和 not的一些实现O(1)

于 2009-04-13T06:41:20.907 回答
27

每次使用时都需要写出条件size()。使用起来很方便empty()。当然,前提是您不切换容器。正如其他人指出的那样,是否使用取决于size()实现empty()。但是,该标准确实保证:empty()是所有标准容器的恒定时间操作。

于 2009-04-13T06:51:14.127 回答
11

好吧,正如你所说,这只是一个实现细节。std::list可以使用存储的大小(恒定时间size()但线性时间splice())或不使用(恒定时间splice()但线性时间size())来实现。通过选择使用empty(),您可以避免在不需要知道大小的情况下押注于实现细节。

于 2009-04-13T06:42:36.270 回答
7

遵循标准,应首选 empty(),因为它具有恒定的时间复杂度,而与容器类型无关。

在 C++03 标准中,第 23.1 章,表 65:容器要求

Operation:   empty()
Return_type: convertible to bool
Semantics:   equivalent to size()==0
Complexity:  constant

似乎在您的 STL 实现中,他们将语义视为真正的实现而忽略了复杂性要求,或者 size() 是实现中的常量时间(存储字段)。

如果 size() 不是恒定时间,请联系您的供应商以了解 std::list<>::empty() 不满足标准容器要求。

于 2009-04-13T07:31:45.980 回答
7

第一,当您想知道某物是否为空时使用调用的函数empty()使代码更具可读性,这意味着您不必担心实现细节。这也意味着您的代码可以更容易地适应具有其他特性的其他类型的容器。

第二,这只是一个 STL 实现。我的 GNU C++ 看起来像这样:

bool
empty() const
{ return begin() == end(); }

这最终将导致指针比较,而使用 size() 将导致减法(在此实现中)。

第三,它不太可能产生额外函数调用的开销,因为empty()-function 可能是内联的(在两个实现中)。

于 2009-04-13T09:03:32.127 回答
5

empty() 对所有容器类都有 O(1) 的实现。size() 只能为某些容器提供 O(n) 的实现;这就是为什么首选 empty() 的原因。

于 2009-04-14T03:05:45.377 回答
1

除了上面给出的原因,它也可以说比 foo.size() == 0 和/或 !foo.size()

于 2009-04-13T07:38:09.867 回答
0

除了非常有效的可读性点之外,您所经历的只是一种特定实现的工件,而不是唯一可能的工件。

也就是说,在向量和列表情况下,或者实际上任何其他容器中,都没有理由或要求根据 size() 来实现 empty()。如果有更好的替代方案,则应该使用它们,除非库的作者不称职,或者更合理地说是懒惰。

至于列表和 size() 的 O(1)-ness,或者缺少它,您应该考虑到该列表可能将 size() 实现为 O(1) 或 splice(),但不能同时实现两者(思考关于原因是一个有趣的练习。)因此,在您的情况下,您检查的库可能已将 size() 实现为 O(1)(在这种情况下 splice() 将是 O(n)),因此可以实现 empty()就 size() 而言,不会牺牲性能,否则,这将是一个非常糟糕的库。

于 2009-04-13T13:57:34.587 回答
0

更喜欢使用 empty() 而不是 size() 因为,每个容器可能以不同的方式实现 empty() 来获得恒定时间操作。

例子:

vector 实现为: bool empty() const { // 测试序列是否为空 return (size() == 0); }

列表实现为:

        bool empty() const
    {   // test if sequence is empty
    return (_Mysize == 0);
    }
于 2013-11-19T13:29:38.790 回答