splitable data structure (in c++11)

Question

I wonder if anybody could help me out.

I look for a data structure (such as list, queue, stack, array, vector, binary tree etc.) supporting these four operations:

• isEmpty (true/false)
• insert single element
• pop (i.e. get&remove) single element
• split into two structures e.g. take a approximately half (let's say +/- 20%) of elements and move them to another structure

Note that I don't care about order of elements at all.

Insert/pop example:

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

and the split example:

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

I need the structure to be be fast as possible - preferably all four operations in O(1). I doubt it have been already implemented in std so I will implement it by myself (in C++11, so std::move can be used).

Note that insert, pop and isEmpty are called about ten times more frequently than split.

I tried some coding with list and vector but with no success:

#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;
}

Any sample code, ideas, links or whatever useful? Thanks

Related literature:

• How to move the later half of a vector into another vector? (actually does not work due to deletetion problem)
• http://www.cplusplus.com/reference/iterator/move_iterator/

Answer 1

Your problems with the deletion aare due to a bug in your code.

// sigsegv
auto halfway2 = v1.begin() + v1.size() / 2;
auto endItr2  = v1.end();
v2.erase(halfway2, endItr2);

You try to erase from v2 with iterators pointing into v1. That won't work and you probably wanted to callerase on v1.

That fixes your deletion problem when splitting the vector, and vector seems to be the best container for what you want.

Note that everything except split can be done in O(1) on a vector if you insert at the end only, but since order doesn't matter for you I don't see any problem with it, split would be O(n) in your implemention once you fixed it, but that should be pretty fast since the data is right next to eachother in the vector and that's very cache friendly.