我要编写一个 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/