我想知道是否有人可以帮助我。

我正在寻找一种支持以下四个操作的数据结构(例如列表,队列,堆栈,数组, vector ,二叉树等):

  • isEmpty (true/false)
  • 插入单个元素
  • 流行(即获取和删除)单元素
  • 分为两个结构,例如接受大约一半的元素(假设为+/- 20%)并将其移至另一个结构

  • 请注意,我根本不在乎元素的顺序。

    插入/弹出示例:
    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的调用频率比拆分大约高十倍。

    我尝试用listvector尝试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;
    }
    

    是否有任何示例代码,想法,链接或其他有用的信息?谢谢

    相关文献:
  • How to move the later half of a vector into another vector?(由于删除问题,实际上不起作用)
  • http://www.cplusplus.com/reference/iterator/move_iterator/
  • 最佳答案

    您的删除问题是由于代码中的错误所致。

    // 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 中紧挨着彼此,并且对缓存非常友好。

    09-09 23:26
    查看更多