我想知道是否有人可以帮助我。
我正在寻找一种支持以下四个操作的数据结构(例如列表,队列,堆栈,数组, vector ,二叉树等):
请注意,我根本不在乎元素的顺序。
插入/弹出示例:
A.insert(1), A.insert(2), A.insert(3), A.insert(4), A.insert(5) // contains 1,2,3,4,5 in any order
A.pop() // 3
A.pop() // 2
A.pop() // 5
A.pop() // 1
A.pop() // 4
和分割示例:
A.insert(1), A.insert(2), A.insert(3), A.insert(4), A.insert(5)
A.split(B)
// A = {1,4,3}, B={2,5} in any order
我需要结构尽可能快-最好是O(1)中的所有四个操作。我怀疑它已经在std中实现了,所以我将自己实现(在C++ 11中,因此可以使用
std::move
)。请注意,插入,pop和isEmpty的调用频率比拆分大约高十倍。
我尝试用
list
和vector
尝试some coding,但没有成功:#include <vector>
#include <iostream>
// g++ -Wall -g -std=c++11
/*
output:
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
5 6 7 8 9
*/
int main ()
{
std::vector<int> v1;
for (int i = 0; i < 10; ++i) v1.push_back(i);
for (auto i : v1) std::cout << i << " ";
std::cout << std::endl;
auto halfway = v1.begin() + v1.size() / 2;
auto endItr = v1.end();
std::vector<int> v2;
v2.insert(v2.end(),
std::make_move_iterator(halfway),
std::make_move_iterator(endItr));
// sigsegv
/*
auto halfway2 = v1.begin() + v1.size() / 2;
auto endItr2 = v1.end();
v2.erase(halfway2, endItr2);
*/
for (auto i : v1) std::cout << i << " ";
std::cout << std::endl;
for (auto i : v2) std::cout << i << " ";
std::cout << std::endl;
return 0;
}
是否有任何示例代码,想法,链接或其他有用的信息?谢谢
相关文献:
最佳答案
您的删除问题是由于代码中的错误所致。
// sigsegv
auto halfway2 = v1.begin() + v1.size() / 2;
auto endItr2 = v1.end();
v2.erase(halfway2, endItr2);
您尝试使用指向
v2
的迭代器从v1
中擦除。那是行不通的,您可能想在erase
上调用v1
。这解决了拆分 vector 时的删除问题, vector 似乎是您想要的最佳容器。
请注意,如果仅在末尾插入,除split以外的所有操作都可以在O(1)上完成,但是由于顺序对您而言无关紧要,所以我看不到任何问题,split将为O(n)一旦实现修复,就可以在实现中进行修改,但这应该非常快,因为数据在 vector 中紧挨着彼此,并且对缓存非常友好。