gpt4 book ai didi

c++ - 关于如何使用循环数组实现 std::vector 的建议?

转载 作者:行者123 更新时间:2023-11-30 03:44:34 25 4
gpt4 key购买 nike

我要编写一个 C++ 程序:

“通过以循环方式使用的可扩展数组实现 vector ADT,以便在开始和结束处的插入和删除在恒定时间内运行。(所以不是 O(n)) . 每次插入和删除之前和之后打印循环数组,你不能使用STL。”

这个任务对我来说似乎很困惑。 std::vector 是使用基于堆栈概念的动态数组实现的,对吗?在前面执行删除或插入在我看来,这应该作为队列或出列而不是 vector 来实现。此外,循环数组意味着当数据被推送到一个完整的数组时,旧数据会被覆盖,对吧?那么我什么时候应该知道扩展 vector 的容量呢?

如果我在这里没有意义,基本上我需要帮助来理解我应该如何实现动态循环数组。

是的,这是一项家庭作业。不,我不希望任何人为我提供代码,我只希望有人能给我一个正确的方向,让我知道我应该如何考虑实现它。谢谢。

最佳答案

我认为您实际上是被要求实现双端队列。 “循环”的要点是,在法 vector 中,您不能在开头添加元素,因为没有可用空间,您必须将所有其他元素向右移动。因此,您可以做的是通过将元素放在基本数组的末尾来模拟一个圆,并记住这是第一个元素所在的位置。

示例:2、3、-、-、1,其中 1 在前,3 在后

所以,基本上你循环插入元素,并记住第一个和最后一个元素的位置,这样你就可以在 O(1) 中添加到开头/结尾。此外,当数组已满时,您必须将所有元素移动到更大的元素。如果你将大小加倍,你仍然会得到 O(1) 的摊销时间

关于c++ - 关于如何使用循环数组实现 std::vector 的建议?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35382995/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com