C++ STL数据结构与Java相比较

12

我目前正在学习C++,试图熟悉与之配套的标准数据结构,但它们都显得很简陋。例如,列表(list)中没有像Java中我所熟悉的get(index)这样的简单访问器。而pop_back和pop_front这样的方法也不会返回列表中的对象。因此,你需要这样做:

Object blah = myList.back();
myList.pop_back();

与其使用简单的代码: Object blah = myList.pop_back();

在Java中,几乎每个数据结构都会返回对象,因此你不必进行这些额外的调用。为什么C++的STL容器设计成这样?在C++中,像我在Java中做的这样的常见操作不那么常见吗?

编辑:对不起,我想我的问题表述得很差,导致被踩得很多,但肯定有人可以修改它。澄清一下,我想知道STL数据结构与Java相比是如何创建的。或者我一开始使用的数据结构是错误的吗?我的意思是,这些似乎是你可能针对(例如)列表使用的常见操作,而不是每次都要编写自己的实现。

编辑:重新描述问题以更清晰明了。


5
我们有迭代器和运算符重载,以及不返回任何东西所带来的异常安全性。 - chris
2
在编写C++时,请忘记您从Java中习惯的一切。此外,编写一个函数return_pop_back并不难,它可以实现您想要的功能。 - Xeo
2
为什么会有这么多踩?这是一个经过深思熟虑的问题,尽管有些偏见。 - Mooing Duck
3
由于STL通常不公开低效的方法,因此std::list<foo>::get(index)不存在。 STL列表是一个双向链表:仅有的使用它的原因是需要能够使用O(1)成本进行拼接 - 如果您想要请求列表的第n个元素,则几乎肯定会出错并使用错误的容器。 有一些方法可以获取std::list的第n个元素(获取begin(),然后将其advance() n步),但它们比编写难度更大的操作还要昂贵。 - Yakk - Adam Nevraumont
2
@Yakk: 根据 C++11 的规定,由于 std::list::size 保证是 O(1),因此 std::list::splice 在被接合元素数量的情况下保证为 O(N)。 :( - Xeo
显示剩余4条评论
7个回答

11

已经有很多人回答了你提出的具体问题,所以我会试图从更大的角度来看待。

Java和C++之间最基本的区别之一是,C++主要使用值(values)工作,而Java主要使用引用(references)工作。

例如,如果我有这样一个东西:

class X {
    // ...
};

// ...
X x;
在Java中,x仅是类型为X的对象的引用。要使其引用实际的X类型对象,我通常会这样做:X x = new X;。然而,在C++中,单独的X x;定义了一个类型为X的对象,而不仅仅是对象的引用。我们可以直接使用该对象,而不是通过引用(即伪装成指针)来使用它。
虽然这一点最初可能看起来像是一个相当微不足道的差异,但其影响却是深远而广泛的。其中一个影响(在这种情况下可能是最重要的)是,在Java中,返回值根本不涉及复制对象本身。它只涉及复制对该值的引用。这通常被认为是非常廉价和(可能更重要的是)完全安全的--它永远不会抛出异常。
在C++中,你直接处理值。当你返回一个对象时,你不仅仅是返回对现有对象的引用,还返回该对象的值,通常以该对象状态的副本形式返回。当然,如果想要返回引用(或指针),也是可能的,但必须显式地指定。
标准容器甚至更加重视与值而不是引用一起工作。当你将一个值添加到集合中时,添加的是您传递的值的副本,并且当您从集合中获取东西时,返回的是容器本身中存在的值的副本。
这意味着,虽然返回一个值可能像在Java中一样便宜和安全,但它也可能是昂贵的和/或抛出异常。如果程序员想要存储指针,他们当然可以这样做--但与Java不同,语言并未要求必须这样做。由于返回对象可能既昂贵又会抛出异常,所以标准库中的容器通常围绕确保它们可以在复制昂贵的情况下正常工作(更重要的是),即使复制引发异常也可以正确地工作。
这种基本的设计差异不仅解释了您指出的差异,还解释了许多其他差异。

5
back()返回一个向量的最后一个元素的引用,因此几乎是免费调用的。而pop_back()则调用了向量最后一个元素的析构函数。
因此,显然pop_back()不能返回一个已被销毁的元素的引用。因此,为了让您的语法工作,pop_back()必须在其被销毁之前返回该元素的副本。
现在,在您不想要该副本的情况下,我们只是不必要地复制了一份副本。
C++标准容器的目标是给您提供几乎裸机性能的包装,在使用上非常方便。就大多数情况而言,它们并不会为了易用性而牺牲性能——如果pop_back()返回最后一个元素的副本,则会为了易用性而牺牲性能。
可能会有一种弹出并返回方法,但这将复制其他功能。在许多情况下,它也比back-and-pop效率低。
具体例子:
vector<foo> vec; // with some data in it
foo f = std::move( vec.back() ); // tells the compiler that the copy in vec is going away
vec.pop_back(); // removes the last element

请注意,在元素被销毁之前必须进行移动,以避免创建额外的临时副本......pop_back_and_get_value()在返回值之前必须销毁元素,而赋值会在返回之后发生,这是浪费的。

1
@trevor-e 看看这个 c++ 容器参考 维基百科。有许多不同类型的容器,它们实际上并不太难使用,但你需要了解它们的一般特性。 - juanchopanza
1
@trevor-e:并不是这个标签下的所有人都这样认为。你可能会注意到已经有两个投票决定重新开放这个问题,其中一个是我的。尽管你提出的问题可能存在偏见,但还是存在一个可以回答的问题。但我希望你可以看到,你的问题可能会被类似地表述为“为什么C++相对于Java很糟糕?”在这种解释下,我并不惊讶你的问题被贴上了负分并且被关闭。 - John Dibling
1
@MooingDuck 好的,很酷。既然一切都是引用,如果我弹出了某个东西并且析构函数被调用了,那么我显然不能再使用那个引用了,对吧?这更有意义。我以为这些结构在很大程度上与Java相似,但看起来我非常错误哈哈。会继续阅读这些内容的。有趣的使用统计数据。 - telkins
1
@Yakk:我不建议将std::deque作为默认选项,因为MSVC/dinkum以一种_愚蠢_的方式实现了它。但是如果他们没有搞砸的话,我会同意你的观点。 - Mooing Duck
1
@Yakk:如果它包含16字节或更大的对象,则类似于vector<unique_ptr<T>>,但具有平摊O(1)的push_front - Mooing Duck
显示剩余8条评论

4
一个链表没有get(index)方法,因为按索引访问链表非常低效。 STL 的哲学是只提供那些可以实现相对高效的方法。如果您想访问一个链表的索引,而不管其效率如何,很容易自己实现。 pop_back不返回副本的原因是在函数返回后(除了RVO/NRVO),返回值的复制构造函数将被调用。 如果此复制构造函数抛出异常,则已从列表中删除该项但未正确返回副本。这意味着该方法将不具备异常安全性。通过分离这两个操作,STL 鼓励以一种具有异常安全性的方式编程。

好的,我现在开始理解了。复杂性哲学对我来说有些奇怪。为什么不让开发人员决定是否使用它成本太高呢? - telkins
3
如果 pop 返回值本身,开发者就无法做出这个选择了。这个决定将已经被语言所制定。 - John Dibling
3
那些需要通过索引在链表中获取值的人是错误的,因此他们在像C++标准委员会这样的经验丰富的社区中没有代表。因此,该函数未被添加到std::list中,因为委员会中没有人想要它。界面中可能有无数其他功能,但添加无用的功能是没有意义的。 - Benjamin Lindley
1
此外,C++还有免费的函数和函数模板,这意味着可以使用<algorithm>中的许多函数。这与Java不同,Java只能使用类本身的方法。 - MSalters

3
我认为Bjarne Stroustrup 最好地表达了:

C++是精简而高效的。其基本原则是你不必为你不使用的东西付出代价。

就返回该项的pop()方法而言,考虑到为了同时删除该项并返回它,该项不能通过引用返回。因为引用已经不存在了,它只是被pop()了。如果您制作原始副本的新new,则可以通过指针返回它,但这是浪费的。因此,它很可能会通过值返回,这可能会进行深层复制。在许多情况下,它不会进行深层复制(通过复制省略),在其他情况下,该深层复制将是微不足道的。但在某些情况下,例如大型缓冲区,该副本可能非常昂贵,并且在一些情况下,例如资源锁定,甚至可能无法实现。

C++旨在成为通用目的编程语言,并且旨在尽可能快速。通用目的并不一定意味着“易于用于简单用例”,而是“适用于最广泛应用的平台。”


2
“list”没有像“get(index)”这样简单的访问器,为什么呢?让您从“list”中访问第n个元素的方法将隐藏操作的复杂性O(n),这就是C++不提供它的原因。出于同样的原因,C++的“std::vector”也不提供“pop_front()”函数,因为该函数在向量大小上也是O(N)。方法如“pop_back”和“pop_front”也不返回列表中的对象,这是因为C++有异常安全性,并且由于C++具有自由函数,因此编写此类扩展到任何标准容器的操作并不难。{{link1}}
template<class Cont>
typename Cont::value_type return_pop_back(Cont& c){
  typename Cont::value_type v = c.back();
  c.pop_back();
  return v;
}

需要注意的是,上述函数不具备异常安全性,这意味着如果return v;抛出异常,您将会失去一个对象并且容器也会被改变。

好的,谢谢!你提供的代码使得事情更加清晰了。我之前并不知道这是可能的。就复杂度问题而言,让开发者自己决定是否过于复杂难道不更合理吗? - telkins
@trevor-e:这不是让某人不决定,而是不向他们隐藏它。任何随机访问方法(包括您的 get(index))都意味着根据定义具有 O(1) 的随机访问。 - Xeo
@trevor-e:所有的list成员都是快速的。如果你想做一些慢的操作,你必须亲自编写那3-4行代码。他们选择这样做的原因是,首先,这样做不会让人感到烦躁;其次,这样做可以确保程序员是有意识地进行慢速操作,而不是出于意外。 - Mooing Duck

2
关于类似于pop()的函数,至少有两件事情需要考虑:
1)当没有可返回的内容时,对于返回pop_back()pop_front(),没有明确和安全的操作。
2)这些函数将通过值返回。如果在容器中存储的类型的复制构造函数中抛出异常,则该项将从容器中删除并丢失。我想这被认为是不可取和不安全的。
关于访问列表,标准库的一般设计原则是不避免提供低效的操作。std::list是一个双向链表,按索引访问列表元素意味着从开头或结尾遍历列表,直到达到所需位置。如果您想要这样做,可以提供自己的辅助函数。但是,如果您需要随机访问元素,则应该使用除列表以外的其他结构。

当使用pop_back时,值语义如何与没有返回值相关联? - Mooing Duck
在空容器上使用 pop_xxx() 简单地被视为未定义行为。 :) - Xeo
1
@wug 当然,C++支持异常,但在某些情况下,人们认为返回void的pop()比返回值并有可能抛出异常更安全。 - juanchopanza
@Wug:C++11 Jan2012,§21.4.6.5\11 "void pop_back(); 要求:!empty()" - Mooing Duck
@juanchopanza:谢谢,我们之前的沟通让我有些沮丧。现在问题已经解决了,把-1改成+1。 - Mooing Duck
显示剩余11条评论

1
在Java中,通用接口的pop可以返回弹出对象的引用。
在C++中,返回相应的内容是通过值返回。
但是,在不可移动的非POD对象的情况下,复制构造可能会抛出异常。然后,一个元素已经被删除,但尚未对客户端代码进行访问。可以始终基于更基本的检查器和纯弹出器定义方便的按值返回弹出器,但反之则不行。
这也是哲学上的差异。
使用C++时,标准库仅提供基本构建块,而不直接提供可用功能(通常情况下)。这意味着您可以自由选择数千个第三方库,但这种选择自由的代价很高,包括可用性、可移植性、培训等方面。相比之下,使用Java,您在标准库中基本上拥有所有需要的东西(用于典型的Java编程),但您实际上无法自由选择(这是另一种成本)。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接