stl - Алгоритм замещения страниц "Вторая попытка"


1

Помогите, пожалуйста, найти ошибку в алгоритме, вроде все правильно работает, но иногда при разных входных данных возникает ошибка. Так вот, решил реализовать алгоритм замещения страниц "Вторая попытка". Коротко о задаче, имеется память ограниченного размера, в память на вход подаются страницы, алгоритм подобен FIFO, отличие в том, что если страница есть в памяти, то она переводится в конец очереди. У меня сделано так, что находится страница, которая есть в памяти, и удаляется по ее позиции, а пришедшая страница добавляется в конец очереди (если они совпадают).

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdlib>

void show_fifo(const deque<int> &dq)
{
    deque<int>::const_iterator i;
    for (i=dq.begin(); i != dq.end(); ++i)
    {
        cout << *i << " ";
    }
     cout << endl;
}
int main()
{
    int mem_size = 5;
    int access_num;
    access_num = 13;
    int array[] = { 1, 2, 3, 4, 5, 2, 3, 4, 1, 5, 4, 1, 3};

    cout << "Vtoraya popbitka: " << endl;
    // Vtoraya popitka
        deque<int> dq;

        for (int i=0; i<mem_size; i++)
        {
                dq.push_back(-1);
        }
        cout << "Memory: " << endl;
        show_fifo(dq);

        for (int i = 0; i < access_num; ++i)
        {
                cout << "Step " << (i+1) << ":" << endl;
                for (int j = 0; j < dq.size(); j++)
                {
                                if ((find(dq.begin(), dq.end(), array[i]) != dq.end()) && (dq.size() != 0))
                                {       
                                        cout << "Page: " << array[i] << " has in memory" << endl;
                                        int del = dq.at(array[i]);
                                        dq.erase(dq.begin()+del);
                                        dq.push_front(array[i]);
                                        break;
                                }
                                else
                                {
                                        dq.push_front(array[i]);
                                        dq.pop_back();
                                        break;
                                }
                }
                show_fifo(dq);
        }
Источник
  •  38
  •  1
  • 27 янв 2012 2012-01-27 17:29:31
вместо for (int i=0; i<mem_size; i++) { dq.push_back(-1); } можно написать deque<int> dq(sizeof(array)/sizeof(array[0]), -1) // создать deque<int> и поместить туда 13 элементов со значением -1 — 26 янв 20122012-01-26 16:45:54.000000

1 ответ

1

Если я правильно понимаю код, то Вы проверяете есть ли array[i] в dq, и если есть, "перемещаете" его в конец очереди, посредством удаления и вставки в конец. Если так, то так это и пишите:

    for (int j = 0; j < dq.size(); j++)
    {
        deque<int>::iterator ii = find(dq.begin(), dq.end(), array[i]);

        if ( ii != dq.end() )
        {       
            cout << "Page: " << array[i] << " has in memory" << endl;
            dq.erase(ii);
            dq.push_front(array[i]);
            break;
        }
        else
        {
            dq.push_front(array[i]);
            dq.pop_back();
            break;
        }
    }

У Вас уже есть итератор, указывающий где нужно удалять, зачем повторно шаманить с

int del = dq.at(array[i]);
dq.erase(dq.begin()+del);

? (насколько понимаю, в этом месте и падает)

Кстати, помещаение в конец очереди посредством удаления/вставки не оптимально, имхо проще сделать

        deque<int>::iterator ii = find(dq.begin(), dq.end(), array[i]);

        if ( ii != dq.end() )
        {       
            cout << "Page: " << array[i] << " has in memory" << endl;

            deque<int>::reverse_iterator temp = dq.rbegin(); // получить итератор на последний элемент
            std::swap(*ii, *temp); // обменять значения итераторов

            break;
        }
  • 26 янв 2012 2012-01-26 16:39:27
Недоглядел немного, подумал, что Вы добавляете ко-во элементов, равное размер массива array. С mem_size вместо sizeof(array) будет правильно. — 27 янв 20122012-01-27 04:22:35.000000
Разобрался. Можно еще так: вместо for (int i=0; i<mem_size; i++) { dq.push_back(-1); } можно написать deque<int> dq(mem_size, -1); // используете sizeof, говорите зачем. Да в том месте падало на последнем шаге, но работал алгоритм правильно. Взял на заметку swap(). Спаспбо!!! — 27 янв 20122012-01-27 04:13:29.000000