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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.80
Visary_Master
 Аватар для Visary_Master
-154 / 16 / 4
Регистрация: 01.12.2010
Сообщений: 297
18.01.2012, 15:46     Помогите разобраться (STL, алгоритмы замещения страниц) #1
Здравствуйте, хочу реализовать алгоритм замещения страниц памяти 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?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.01.2012, 15:46     Помогите разобраться (STL, алгоритмы замещения страниц)
Посмотрите здесь:

Реализация механизма замещения страниц в ОП C++
STL алгоритмы сортировки C++
C++ Функторы и алгоритмы stl
C++ Написать свой итератор, чтобы алгоритмы STL работали с моим классом
C++ Задача на С++. Алгоритмы библиотеки STL.
C++ Алгоритмы замещения страниц(STL, вторая попытка)
Алгоритм замещения страниц LRU с помощью методов библиотеки STL C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
18.01.2012, 15:56     Помогите разобраться (STL, алгоритмы замещения страниц) #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
go
Эксперт C++
3584 / 1364 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
18.01.2012, 16:04     Помогите разобраться (STL, алгоритмы замещения страниц) #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
Visary_Master
 Аватар для Visary_Master
-154 / 16 / 4
Регистрация: 01.12.2010
Сообщений: 297
18.01.2012, 16:10  [ТС]     Помогите разобраться (STL, алгоритмы замещения страниц) #4
Цитата Сообщение от soon Посмотреть сообщение
std::cout << std::find(d.begin(), d.end(), 20) - d.begin() << std::endl;
А как для чего
- d.begin()
Можете объяснить, что делает эта строка?
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
18.01.2012, 16:15     Помогите разобраться (STL, алгоритмы замещения страниц) #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-й элемент.
Visary_Master
 Аватар для Visary_Master
-154 / 16 / 4
Регистрация: 01.12.2010
Сообщений: 297
18.01.2012, 16:27  [ТС]     Помогите разобраться (STL, алгоритмы замещения страниц) #6
У меня нет проблем с удалением и вставкой элементов. Простите конечно, может заставил думать вас, что исходник, который выложил выше, не мой, но я его писал сам. Про тут, я тут постоянный посетитель...

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

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

Добавлено через 2 минуты
go, с обычной очередью, имхо, неудобно. Насколько я понял задание, чтобы найти страницу, нужно будет либо убирать в другую очередь, либо делать копию исходной.
Visary_Master
 Аватар для Visary_Master
-154 / 16 / 4
Регистрация: 01.12.2010
Сообщений: 297
18.01.2012, 16:40  [ТС]     Помогите разобраться (STL, алгоритмы замещения страниц) #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?
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
18.01.2012, 16:44     Помогите разобраться (STL, алгоритмы замещения страниц) #9
Цитата Сообщение от Visary_Master Посмотреть сообщение
Для чего вы из этого выражения вычитаете
Чтобы позицию узнать.

Цитата Сообщение от Visary_Master Посмотреть сообщение
И... чем плоха эта функция, если использовать deque?
Если делать с deque, то в ней нет смысла. Кроме того, она удаляет все элементы, "идущие" перед val.
go
Эксперт C++
3584 / 1364 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
18.01.2012, 16:50     Помогите разобраться (STL, алгоритмы замещения страниц) #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
soon
18.01.2012, 16:54
  #11

Не по теме:

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

retmas
Жарю без масла
824 / 706 / 151
Регистрация: 13.01.2012
Сообщений: 1,618
18.01.2012, 16:54     Помогите разобраться (STL, алгоритмы замещения страниц) #12
Цитата Сообщение от Visary_Master Посмотреть сообщение
Для чего вы из этого выражения вычитаете
чтоб узнать и вывести позицию в очереди найденного элемента

Не по теме:

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

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

Добавлено через 1 минуту
Получается, что мне не нужно делать эту проверку?
C++
1
2
3
4
5
if (array[i] == dq.at(j))
{
    cout<< "Page " << array[i] << " has in memory: " << endl;
    break;
}
Можно обойтись той строчкой с find()
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
18.01.2012, 17:58     Помогите разобраться (STL, алгоритмы замещения страниц) #16
Цитата Сообщение от Visary_Master Посмотреть сообщение
Можно обойтись той строчкой с find()
Да, если делаете через deque. Если через queue будете, то через функцию от go в посте #3
Visary_Master
 Аватар для Visary_Master
-154 / 16 / 4
Регистрация: 01.12.2010
Сообщений: 297
18.01.2012, 18:08  [ТС]     Помогите разобраться (STL, алгоритмы замещения страниц) #17
А можно как нибудь сделать так:
C++
1
2
3
4
if (!find(d.begin(), d.end(), 20) - d.begin())
{
    //то делаем действия удаления и вставки
}
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
18.01.2012, 18:18     Помогите разобраться (STL, алгоритмы замещения страниц) #18
Цитата Сообщение от Visary_Master Посмотреть сообщение
А можно как нибудь сделать так:
Если не найден?
C++
1
2
3
4
if(std::find(d.begin(), d.end(), value) == v.end())
{
    //do something
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.01.2012, 18:37     Помогите разобраться (STL, алгоритмы замещения страниц)
Еще ссылки по теме:

C++ Не могу разобраться с map(STL)
Контейнер map и алгоритмы STL: несовместимость? C++
Найти элемент в контейнере priority_queue, используя STL вские итераторы и алгоритмы C++
C++ Алгоритмы STL Удаление элементов в векторе
Избавиться от цикла, используя алгоритмы из STL C++

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

Или воспользуйтесь поиском по форуму:
Visary_Master
 Аватар для Visary_Master
-154 / 16 / 4
Регистрация: 01.12.2010
Сообщений: 297
18.01.2012, 18:37  [ТС]     Помогите разобраться (STL, алгоритмы замещения страниц) #19
Цены вам нет, когда подрасту, тоже буду помогать всем чем смогу Спасибо!
Можно закрыть тему.
Взял на заметку Метод go.
Yandex
Объявления
18.01.2012, 18:37     Помогите разобраться (STL, алгоритмы замещения страниц)
Ответ Создать тему
Опции темы

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