Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.80
Visary_Master
-154 / 16 / 4
Регистрация: 01.12.2010
Сообщений: 297
#1

Помогите разобраться (STL, алгоритмы замещения страниц) - C++

18.01.2012, 15:46. Просмотров 1233. Ответов 18
Метки нет (Все метки)

Здравствуйте, хочу реализовать алгоритм замещения страниц памяти FIFO.
Не знаю как организовать проверку на присутствие страницы в памяти, если страница есть в памяти, то ничего не делаем, иначе добавляем в начало, удаляем с конца.
Вот мои наработки(компилятор g++):
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <sys/time.h>
#include <deque>
using namespace std;
 
 
void show_fifo(const char *str, const deque<int> &dq)
{
    deque<int>::const_iterator i;
    cout << str << endl;
    for (i=dq.begin(); i != dq.end(); ++i)
    {
        cout << *i << " ";
    }
     cout << endl;
}
   
int main()
{
    int n = 10;
    int *array = new int[n];
    deque<int> dq;    
    int mem_size = 5;
    int access_num; // число эл-ов последовательности
    
    cout << "Введите кол-во обращений к страницам памяти: " << endl;
    cin >> access_num;
    
    cout << "Введите последовательность обращения к страницам: " << endl;
    for(int it = 0; it < access_num; it++)
        cin >> array[it]; 
 
    for (int i=0; i<mem_size; i++)
    {
        dq.push_back(-1);
    }
    cout << "Memory: " << endl;
    show_fifo("After init", dq);
    
    deque<int>::const_iterator j;
 
    // FIFO - алгоритм "первым вошел, первым вышел"   
    for (int i = 0; i < access_num; ++i)
    {
         for (int j=0; j<dq.size(); j++)
         {
            if (array[i] == dq.at(j))
            {
                cout<< "Page " << array[i] << " has in memory: " << endl;
                break;
            }
            else
            {
                dq.push_front(array[i]);
                dq.pop_back();
                break;
            }
         }
         cout << "Step " << (i+1) << ":" << endl;
         show_fifo("After step", dq);
    }
    return 0;   
}
Помогите пожалуйста.
Можно ли воспользоваться методами STL find или find_if?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.01.2012, 15:46
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Помогите разобраться (STL, алгоритмы замещения страниц) (C++):

Алгоритмы замещения страниц(STL, вторая попытка) - C++
Помогите пожалуйста найти ошибку в алгоритме, вроде все правильно работает, но иногда при разных входных данных возникает ошибка. Так...

Алгоритм замещения страниц LRU с помощью методов библиотеки STL - C++
Здравствуйте! Мне нужно реализовать алгоритм замещения страниц LRU с помощью методов библиотеки STL. Подскажите пожалуйста, как это сделать...

Реализация механизма замещения страниц в ОП - C++
Необходимо реализовать модель «реализация механизма замещения страниц в ОП». Существует список из N активных страниц (по желанию можно...

Функторы и алгоритмы stl - C++
Добрый день! Интересует такой вопрос. Я хочу, используя стандартный алгоритм стл for_each() и функтор, определить наибольший элемент в...

STL алгоритмы сортировки - C++
Здрасти. В STL есть алгоритмы sort - упорядочивает последовательность и stable_sort - упорядочивает последовательность, не меняя...

Задача на С++. Алгоритмы библиотеки STL. - C++
Программа должна демонстрировать использование контейнерных классов для хранения встроенных типов данных. В программе выполнить...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
soon
2540 / 1305 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
18.01.2012, 15:56 #2
Visary_Master, если вы об этом, то да
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <deque>
#include <algorithm>
#include <iostream>
 
int main()
{
    std::deque<int> d;
    d.push_back(10);
    d.push_back(20);
    d.push_back(30);
    std::cout << std::find(d.begin(), d.end(), 20) - d.begin() << std::endl;
    return 0;
}
Прокатит с deque, но не с queue
1
go
Эксперт C++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
18.01.2012, 16:04 #3
Цитата Сообщение от Visary_Master Посмотреть сообщение
Здравствуйте, хочу реализовать алгоритм замещения страниц памяти FIFO.
Разве не так?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <queue>
 
using namespace std;
 
bool cmp (queue<int> q, int val)
{
   while ( !q.empty() )
   {
     if ( q.front() == val )
        return true;
     q.pop();
   }
   return false;
}   
 
int main ()
{
  queue<int> myqueue;
  for ( int i = 0 ;  i < 5 ; ++i )
     myqueue.push (i);
  
  for ( int j = 3 ; j < 10 ; ++j )
     if ( !cmp (myqueue, j) )
        myqueue.push (j) ;
        
   while (!myqueue.empty())
   {
    cout << " " << myqueue.front();
    myqueue.pop();
   }           
  
  return 0;
}
http://liveworkspace.org/code/71cbbd...10955c8b2ebae2
1
Visary_Master
-154 / 16 / 4
Регистрация: 01.12.2010
Сообщений: 297
18.01.2012, 16:10  [ТС] #4
Цитата Сообщение от soon Посмотреть сообщение
std::cout << std::find(d.begin(), d.end(), 20) - d.begin() << std::endl;
А как для чего
- d.begin()
Можете объяснить, что делает эта строка?
0
soon
2540 / 1305 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
18.01.2012, 16:15 #5
Цитата Сообщение от Visary_Master Посмотреть сообщение
А как для чего
- d.begin()
deque - double-end queue. Т.е. там существует произвольный доступ к элементам. Однако там все равно FIFO, что можно увидеть на этом примере
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <deque>
#include <algorithm>
#include <iostream>
#include <iterator>
 
int main()
{
    std::deque<int> d;
    d.push_back(10);
    d.push_back(20);
    d.push_back(30);
    d.pop_front();
    std::copy(d.begin(), d.end(), std::ostream_iterator<int>(std::cout, " "));
    return 0;
}
Удалили front- элемент, т.е. 10. Подробнее можно прочитать тут

А конкретно d.begin() возвращает итератор, указывающий на 1-й элемент.
0
Visary_Master
-154 / 16 / 4
Регистрация: 01.12.2010
Сообщений: 297
18.01.2012, 16:27  [ТС] #6
У меня нет проблем с удалением и вставкой элементов. Простите конечно, может заставил думать вас, что исходник, который выложил выше, не мой, но я его писал сам. Про тут, я тут постоянный посетитель...

Добавлено через 3 минуты
Цитата Сообщение от go Посмотреть сообщение
for ( int j = 3 ; j < 10 ; ++j )
Почему j от 3 до 10?
0
soon
2540 / 1305 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
18.01.2012, 16:35 #7
Visary_Master, я нигде не говорил, что в посте #1 не ваш исходник. Вопрос был - можно ли воспользоваться std::find и иже с ними. Ответ - да, можно, в посте #2 я это показал. Затем спросили, что такое d.begin - я ответил, что это функция, возвращает итератор, указывающий на первый элемент очереди. Кроме того, я объяснил, что хоть deque и имеет произвольный доступ к элементам, но это все равно очередь.

Если есть еще вопросы - задавайте.

Добавлено через 2 минуты
go, с обычной очередью, имхо, неудобно. Насколько я понял задание, чтобы найти страницу, нужно будет либо убирать в другую очередь, либо делать копию исходной.
0
Visary_Master
-154 / 16 / 4
Регистрация: 01.12.2010
Сообщений: 297
18.01.2012, 16:40  [ТС] #8
Цитата Сообщение от Visary_Master Посмотреть сообщение
find(d.begin(), d.end(), 20)
Для чего вы из этого выражения вычитаете
Цитата Сообщение от Visary_Master Посмотреть сообщение
d.begin()
я про это хотел спросить, просто не совсем понятно.

Добавлено через 2 минуты
Думаю, как применить это к своему коду... тоже думал, делать копию страницы, и искать по всей очереди(встречается она или нет), но линейный поиск обрубает все на первом вхождении страницы во очереди.

Добавлено через 1 минуту
Цитата Сообщение от go Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
bool cmp (queue<int> q, int val)
{
    while ( !q.empty() )
    {
       if ( q.front() == val )
          return true;
       q.pop();
    }
    return false;
}
И... чем плоха эта функция, если использовать deque?
0
soon
2540 / 1305 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
18.01.2012, 16:44 #9
Цитата Сообщение от Visary_Master Посмотреть сообщение
Для чего вы из этого выражения вычитаете
Чтобы позицию узнать.

Цитата Сообщение от Visary_Master Посмотреть сообщение
И... чем плоха эта функция, если использовать deque?
Если делать с deque, то в ней нет смысла. Кроме того, она удаляет все элементы, "идущие" перед val.
0
go
Эксперт C++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
18.01.2012, 16:50 #10
Цитата Сообщение от Visary_Master Посмотреть сообщение
Почему j от 3 до 10?
Ну мы положили в очередь числа от 1 до 5
Потом пытаемся положить в очередь, от 3 до 10 но с проверкой, чтобы не класть числа, которые уже присутствуют.



Цитата Сообщение от Visary_Master Посмотреть сообщение
И... чем плоха эта функция, если использовать deque?
Если надо FIFO, значит используйте queue::queue

Цитата Сообщение от soon Посмотреть сообщение
go, с обычной очередью, имхо, неудобно.
Все зависит, как того требует задание. Может необходимо разобраться именно с FIFO

Цитата Сообщение от soon Посмотреть сообщение
чтобы найти страницу, нужно будет либо убирать в другую очередь, либо делать копию исходной.
Я бы вообще в вектор клал все элементы.

Вообщем вариант с queue я предложил.

Добавлено через 41 секунду
Цитата Сообщение от soon Посмотреть сообщение
Если делать с deque, то в ней нет смысла. Кроме того, она удаляет все элементы, "идущие" перед val.
Удаляет?

Добавлено через 52 секунды
soon, все на месте http://liveworkspace.org/code/0cacdb...b9663e32d93008
1
soon
18.01.2012, 16:54
  #11

Не по теме:

Ыы, точно, там же уже копия. go, мои извинения, неправ был.

0
retmas
Жарю без масла
859 / 741 / 164
Регистрация: 13.01.2012
Сообщений: 1,694
18.01.2012, 16:54 #12
Цитата Сообщение от Visary_Master Посмотреть сообщение
Для чего вы из этого выражения вычитаете
чтоб узнать и вывести позицию в очереди найденного элемента

Не по теме:

upd: сначала не заметил, что ответили

0
Visary_Master
-154 / 16 / 4
Регистрация: 01.12.2010
Сообщений: 297
18.01.2012, 17:00  [ТС] #13
C++
1
 while ( !q.empty() )
Не могу понять почему пользуемся методом empty(), может нужно до последнего эл-та в очереди?
0
soon
2540 / 1305 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
18.01.2012, 17:05 #14
Цитата Сообщение от Visary_Master Посмотреть сообщение
Не могу понять почему пользуемся методом empty(), может нужно до последнего эл-та в очереди?
В queue нет queue::end(). Так что только через проверку на пустую очередь.
1
Visary_Master
-154 / 16 / 4
Регистрация: 01.12.2010
Сообщений: 297
18.01.2012, 17:46  [ТС] #15
Так... надо подумать, как в моем коде использовать...

Добавлено через 1 минуту
Получается, что мне не нужно делать эту проверку?
C++
1
2
3
4
5
if (array[i] == dq.at(j))
{
    cout<< "Page " << array[i] << " has in memory: " << endl;
    break;
}
Можно обойтись той строчкой с find()
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.01.2012, 17:46
Привет! Вот еще темы с ответами:

Стандартная библиотека шаблонов STL Алгоритмы - C++
Здравствуйте помогите пожалуйста сделать сортировку по фамилии // ConsoleApplication59.cpp: определяет точку входа для консольного...

Контейнер map и алгоритмы STL: несовместимость? - C++
Всем доброго времени суток! Столкнулся с проблемой: алгоритм remove_if не работает с контейнером map. Рассмотрим следующую функцию: ...

Избавиться от цикла, используя алгоритмы из STL - C++
Сделал вот такую функцию... Она создает из вектора ассоциативный массив, у которого ключ - элемент вектора, а значение - частота повторений...

Алгоритмы STL Удаление элементов в векторе - C++
Банальный вопрос. vector&lt;int&gt; В нем разные числа могут повторяться. Хочу удалить заданное значение, полностью исключить его из вектора. ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
18.01.2012, 17:46
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru