Я пытался реализовать deque, используя два вектора; для толкания спереди и сзади соответственно. Чтобы упорядочить элементы, я бы итерировал обратный вектор с обычным итератором, а фронтальный вектор с обратным итератором. std :: deque медленный, и мне не нужна его полная функциональность. Итак, я пытаюсь создать свой собственный класс, чтобы ускорить выполнение.
Все работало нормально, если я не осознавал, что мне также нужно обрабатывать и извлекать элементы сзади / вперед, пока очередь не станет пустой. В таком случае мне нужно будет переключать задний вектор с всплывающего вектора сзади и спереди назад, пока хлопает спереди.
Даже это я могу сделать, но в некоторых случаях после переключения с заднего вектора на передний мне может понадобиться добавить больше элементов сзади, теперь они должны go в переднем векторе. Я пытался настроить код, но все портится, и я просто не могу придумать хороший лог c, который мог бы работать. Мне нужны предложения и идеи. Пожалуйста помоги. Вот код.
class Deque{
public:
vector<int> front;
vector<int> back;
int fsize = 5000;
int bsize = 5000;
int fp;
int bp;
int x,y;
Deque()
{
front.resize(fsize);
back.resize(bsize);
fp=-1;
bp=-1;
x=0;
y=0;
}
void pushfront(int x)
{
if(fp>=fsize)
{
fsize = 2*fsize;
front.resize(fsize);
}
fp++;
front[fp]=x;
}
void pushback(int x)
{
if(bp>=bsize)
{
bsize = 2*bsize;
back.resize(bsize);
}
bp++;
back[bp]=x;
}
r_vecitr f_begin()
{
return front.rbegin() + (front.end()-(front.begin()+fp+1));
}
r_vecitr f_end()
{
return front.rend();
}
vecitr b_begin()
{
return back.begin();
}
vecitr b_end()
{
return back.begin()+bp+1;
}
int getfront()
{
if(fp==0)
return back[x];
else if(fp-1>=0)
return front[fp-1];
else
{
return back[x++];
}
}
int getback()
{
if(bp-1>=0)
return back[bp-1];
else
return front[y++];
}
void popfront()
{
if(fp>0)
fp--;
}
void popback()
{
if(bp>0)
bp--;
}
void cleard()
{
fp=-1;
bp=-1;
}
int size()
{
return ( fp+bp +2 );
}
int empty()
{
if(fp+bp+2>0)
return 0;
else
return 1;
}