STL, deque, pair

@Visary_Master · Регистрация: 01.12.2010

Студворк — интернет-сервис помощи студентам

Здравствуйте, помогите пожалуйста разобраться.

Есть такая очередь:

C++
1
deque<pair<int, timeval> > last_query

Как работать с такой очередью?
Как пройтись по всем элементам такой очереди?
Как найти минимальный через timeval? // если можно через метод find
Как добавить элемент в очередь, и удалить.
Можно и пройтись по такой очереди с помощью итератора?

go · 01.02.2012, 20:14

C++
1
mydeque.erase (it);

@Visary_Master · 01.02.2012, 20:15 **[ТС]**

Сообщение от go

Здесь меняли что-нибудь?

Лучше думаю, выложить, что у меня есть....

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
67
68
69
70
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <sys/time.h>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdlib>
using namespace std;
 
ostream& operator << (ostream& s, const timeval& tv)
{
    s << tv.tv_sec << ' ' << tv.tv_usec;
    return s;
}
 
bool const operator < (const timeval& tv1, const timeval& tv2)
{
    return tv1.tv_sec < tv2.tv_sec;
}
 
template <class T>
struct Comp
{
    bool operator () (const T& f, const T& l)
    {
        return f.second < l.second;
    }
};
 
int main()
{
    int n = 10;
    int *array = new int[n];
    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]; 
 
    // LRU - дольше всех не использовавшаяся
    int k = 0;
    deque<pair<int, timeval> > dq1;
    timeval tv;
    for (int i = 0; i < access_num; ++i)
    {
         for(deque<pair<int, timeval> >::iterator j = dq1.begin(); j != dq1.end(),(k<mem_size); ++j,++k) 
         {
            gettimeofday(&tv, NULL);
            dq1.push_back(pair<int, timeval>(k, tv));
         }
    }
    // выводим очередь пар
    for (deque<pair<int, timeval> >::iterator it = dq1.begin(); it != dq1.end(); ++it)
        cout << it->first << ' ' << it->second << endl;
   
   cout << endl;
   // ищем пару с минимальным временем
   deque<pair<int, timeval> >::iterator min = min_element(dq1.begin(), dq1.end(), Comp<pair<int, timeval> >());
        cout << min -> first << ' ' << min -> second << endl;
 
    cout << endl;
    
    return 0;   
}

вывод:

Введите кол-во обращений к страницам памяти:
5
Введите последовательность обращения к страницам:
1
2
3
4
5
0 1328112544 787748
1 1328112544 787750
2 1328112544 787752
3 1328112544 787753
4 1328112544 787755

0 1328112544 787748

Добавлено через 1 минуту

Сообщение от go

mydeque.erase (it);

а перегружать ничего не надо?

@soon · 01.02.2012, 20:17

Сообщение от Visary_Master

int *array = new int[n];

Первое что бросается в глаза. Выделяете память и не освобождаете.

Добавлено через 54 секунды

Сообщение от Visary_Master

а перегружать ничего не надо?

Нет. Это член класса deque.

go · 01.02.2012, 20:18

C++
1
2
3
4
5
6
7
8
9
typedef std::pair<int, timeval>    T_pair;
 
mydeque.erase 
(std::min_element(mydeque.begin(), mydeque.end(), 
                     []  ( T_pair (a), T_pair (b)) 
                     { 
                         return a.second < b.second; 
                     }  )
);

@soon · 01.02.2012, 20:21

Сообщение от Visary_Master

C++
1
2
3
4
5
6
7
8
for (int i = 0; i < access_num; ++i)
{
    for(deque<pair<int, timeval> >::iterator j = dq1.begin(); j != dq1.end(),(k<mem_size); ++j,++k) 
    {
        gettimeofday(&tv, NULL);
        dq1.push_back(pair<int, timeval>(k, tv));
    }
}

Говорил же "пересмотрите цикл"

C++
1
2
3
4
5
6
7
8
for (int i = 0; i < access_num; ++i)
{
    for( ; k < mem_size; ++k) 
    {
        gettimeofday(&tv, NULL);
        dq1.push_back(pair<int, timeval>(k, tv));
    }
}

@Visary_Master · 02.02.2012, 11:53 **[ТС]**

Сообщение от soon

Говорил же "пересмотрите цикл"

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

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

Добавлено через 1 час 41 минуту
Теперь проблемы с логикой...

Не знаю, как правильно построить алгоритм...

Добавлено через 53 минуты

Код

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <sys/time.h>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdlib>
using namespace std;
 
ostream& operator << (ostream& s, const timeval& tv)
{
    s << tv.tv_sec << ' ' << tv.tv_usec;
    return s;
}
 
bool const operator < (const timeval& tv1, const timeval& tv2)
{
    return tv1.tv_sec < tv2.tv_sec;
}
 
template <class T>
struct Comp
{
    bool operator () (const T& f, const T& l)
    {
        return f.second < l.second;
    }
};
 
int main()
{
    int n = 10;
    int *array = new int[n];
    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]; 
 
    // LRU - дольше всех не использовавшаяся
    int k = 0;
    deque<pair<int, timeval> > dq1;
    timeval tv;
    for (int i = 0; i < access_num; ++i)
    {
         for(int k = 0; k < mem_size; ++k) 
         {
            if (i<mem_size)
            {
                gettimeofday(&tv, NULL);
                dq1.push_back(pair<int, timeval>(array[i], tv));
                break;
            }
            else
            {
                deque<pair<int, timeval> >::iterator min = min_element(dq1.begin(), dq1.end(), Comp<pair<int, timeval> >());
                dq1.erase(min);
                gettimeofday(&tv, NULL);
                dq1.push_back(pair<int, timeval>(array[i], tv));
                break;
            }
         }
    }
    cout << endl;
    // выводим очередь пар
    for (deque<pair<int, timeval> >::iterator it = dq1.begin(); it != dq1.end(); ++it)
        cout << it->first << ' ' << it->second << endl;
   
   cout << endl;
   // ищем пару с минимальным временем
   deque<pair<int, timeval> >::iterator min = min_element(dq1.begin(), dq1.end(), Comp<pair<int, timeval> >());
        cout << min->first << ' ' << min->second << endl;
 
    cout << endl;
    
    delete [] array;
    return 0;   
}

Вроде получилось, теперь нужно как-то зная где есть такая же страница обновлять время у нее и не добавлять ее... это нужно думаю в else сделать.

Добавлено через 31 секунду
А то, получается FIFO.

Добавлено через 2 минуты
Еще, такая ошибка возникает, когда больше страниц, чем в mem_size вводишь:

lab7_2.out: malloc.c:3096: sYSMALLOc: Assertion `(old_top == (((mbinptr) (((char *) &((av)->bins[((1) - 1) * 2])) - __builtin_offsetof (struct malloc_chunk, fd)))) && old_size == 0) || ((unsigned long) (old_size) >= (unsigned long)((((__builtin_offsetof (struct malloc_chunk, fd_nextsize))+((2 * (sizeof(size_t))) - 1)) & ~((2 * (sizeof(size_t))) - 1))) && ((old_top)->size & 0x1) && ((unsigned long)old_end & pagemask) == 0)' failed.

Добавлено через 2 часа 51 минуту
Думаю, алгоритм, как-то так должен выглядеть. Проблема в том, что нужно повторяющемся страницам обновлять время, и одну из них не добавлять....

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <sys/time.h>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdlib>
using namespace std;
 
ostream& operator << (ostream& s, const timeval& tv)
{
    s << tv.tv_sec << ' ' << tv.tv_usec;
    return s;
}
 
bool const operator < (const timeval& tv1, const timeval& tv2)
{
    return tv1.tv_sec < tv2.tv_sec;
}
 
template <class T>
struct Comp
{
    bool operator () (const T& f, const T& l)
    {
        return f.second < l.second;
    }
};
 
int main()
{
    int n = 10;
    int *array = new int[n];
    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]; 
 
    // LRU - дольше всех не использовавшаяся
    int k = 0;
    deque<pair<int, timeval> > dq1;
    timeval tv;
    for (int i = 0; i < access_num; ++i)
    {
         for(int k = 0; k < mem_size; ++k) 
         {
            if (i<mem_size)
            {
                gettimeofday(&tv, NULL);
                dq1.push_back(pair<int, timeval>(array[i], tv));
                break;
            }
            else
            {
                deque<pair<int, timeval> >::iterator min = min_element(dq1.begin(), dq1.end(), Comp<pair<int, timeval> >());
                cout << "First min: " << min->second << endl;
                if (array[i] != min->first)
                {
                    gettimeofday(&(min->second), NULL);
                    cout << "second min: " << array[i] << " " << min->first << " " << min->second << endl;
                    break;
                }
                else
                {
                    dq1.push_back(pair<int, timeval>(array[i], tv));
                    dq1.erase(min);
                    break;
                }
                break;
            }
         }
    }
    cout << endl;
    
    // выводим очередь пар
    for (deque<pair<int, timeval> >::iterator it = dq1.begin(); it != dq1.end(); ++it)
        cout << it->first << ' ' << it->second << endl;
    cout << endl;
    
    delete [] array;
    return 0;   
}

Добавлено через 9 часов 53 минуты
upppp!

@soon · 02.02.2012, 13:01

Сообщение от Visary_Master

Проблема в том, что нужно повторяющемся страницам обновлять время, и одну из них не добавлять....

Есть 2 сравнительно простых способа.
1) Пишете свою функцию, которая ищет по первой переменной в pair.
2) Изучаете лямбду, обновляете компилятор и используете find_if с лямбда функцией. Также можно будет обойтись без struct Comp(написав вместо него соответсвующую лямбду).

Можно, конечно, попробовать заморочится с еще одним функтором. Или с bind-ами(хотя для них тоже нужен будет класс). Но оно того не стоит, имхо.

@Visary_Master · 02.02.2012, 14:46 **[ТС]**

может мне проще со счетчиком реализовать?
deque<pair<int, int> > dq
1й int - элемет последовательности
2й - счетчик... который буду увеличивать, уменьшать.
видел как лямбды облегчают жизнь в шарпе, но тут не могу представить.

@soon · 02.02.2012, 17:01

Сообщение от Visary_Master

может мне проще со счетчиком реализовать?

Я что-то не представляю, как счетчик может время последнего доступа заменить.

@Visary_Master · 02.02.2012, 17:33 **[ТС]**

Сообщение от soon

Я что-то не представляю, как счетчик может время последнего доступа заменить.

В таблице страниц добавляется запись - счетчик обращений к странице. Чем меньше значение счетчика, тем реже она использовалась.

@soon · 02.02.2012, 18:05

Visary_Master, Если задача выяснить, какая страница реже/чаще всех использовалась, то пожалуйста. Вам функцию поиска помочь составить?

@Visary_Master · 02.02.2012, 18:46 **[ТС]**

да, помогите... желательно, если возможно с deque<pair<int, int> > dq тогда.

@soon · 02.02.2012, 19:16

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
#include <deque>
#include <utility>
#include <iostream>
#include <algorithm>
 
typedef std::pair<int, int> T_pair;
typedef std::deque<T_pair>   T_deq;
 
template <class Iterator, class T>
Iterator findBy1stArg(Iterator first, const Iterator& last, const T& t)
{
    for( ; first != last; ++first)
        if(first -> first == t)
            return first;
    return first;
}
 
std::ostream& operator << (std::ostream& stream, T_deq& dq)
{
    for(T_deq::iterator it = dq.begin(); it != dq.end(); ++it)
        stream << it -> first << ' ' << it -> second << std::endl;
    return stream;
}
 
int main()
{
    T_deq dq;
    dq.push_back(T_pair(0, 10));
    dq.push_back(T_pair(1, 20));
    dq.push_back(T_pair(2, 30));
    std::cout << dq << std::endl;
    
    for(std::size_t i = 0; i < dq.size(); ++i)
    {
        T_deq::iterator f = findBy1stArg
                            (
                                dq.begin(),
                                dq.end(),
                                static_cast<int>(i));
        if(f != dq.end())
        {
            f -> second = i * 10;
            std::cout << dq << std::endl;
        }
        else
            std::cout << "No " << i << " in deque :(" << std::endl;
    }
    return 0;
}

@Visary_Master · 16.02.2012, 09:38 **[ТС]**

Сообщение от soon

C
1
f -> second = i * 10;

А что делается в это строчке?

Добавлено через 13 минут

Сообщение от soon

C
1
std::size_t i = 0;

Какой тип у переменной i?

silent_1991 · 16.02.2012, 09:42

Сообщение от Visary_Master

А что делается в это строчке?

Присваивается значение i * 10 члену second объекта класса std::pair, находящегося по итератору f.

Сообщение от Visary_Master

Какой тип у переменной i?

std::size_t. Псевдоним unsigned int.

@Visary_Master · 26.02.2012, 22:55 **[ТС]**

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdlib>
using namespace std;
 
template <class Iterator, class T>
Iterator findArg(Iterator first, const Iterator& last, const T& t)
{
    for( ; first != last; ++first)
        if(first -> first == t)
            return first;
    return first;
}
 
template <class T>
struct Comp
{
    bool operator () (const T& f, const T& l)
    {
        return f.second < l.second;
    }
};
std::ostream& operator << (std::ostream& stream, deque<pair<int, int> >& dq)
{
    for(deque<pair<int, int> >::iterator it = dq.begin(); it != dq.end(); ++it)
        stream << it -> first << ' ' << it -> second << std::endl;
    return stream;
}
 
int main()
{
    int mem_size = 5;
    int access_num = 13;
    int array[] = { 1, 2, 3, 4, 5, 2, 3, 4, 1, 5, 4, 1, 3};
 
    // LRU - дольше всех не использовавшаяся
    cout << "LRU" << endl;
    int k = 0;
    deque<pair<int, int> > dq3;
    int count = 0;
    for (int i = 0; i < access_num; ++i)
    {
        for(int k = 0; k < mem_size; ++k) 
        {
            if (i<mem_size)
            {
                cout << "Step " << i << endl;
                dq3.push_back(pair<int, int>(array[i], count));
                count++;
                for (deque<pair<int, int> >::iterator it = dq3.begin(); it != dq3.end(); ++it)
                    cout << it->first << ' ' << it->second << endl;
                break;
            }
            else
            {
                if (i>=mem_size)
                {
                    cout << "Step " << i << endl;
                    deque<pair<int, int> >::iterator f = findArg(dq3.begin(), dq3.end(), static_cast<int>(array[i]));
                    if(f != dq3.end())
                    {
                        f -> second = i + 1;
                        cout << dq3 << endl;
                    }
                    else
                        cout << "No " << array[i] << " in deque" << endl;
                    dq3.push_back(pair<int, int>(array[i], count));
                    // ищем пару с минимальным значением счетчика, чтобы определить страницу
                    // дольше всех не использующихся
                    deque<pair<int, int> >::iterator min = min_element(dq3.begin(), dq3.end(), Comp<pair<int, int> >());
                    dq3.erase(min);
                    for (deque<pair<int, int> >::iterator it = dq3.begin(); it != dq3.end(); ++it)
                        cout << it->first << ' ' << it->second << endl;
                    break;
                }
                break;
            }
        }
    }
    cout << endl;
    return 0;   
}

Вот что у меня получилось, но есть моменты, где счетчик не прибавляется и возникают повторения страниц.

@Visary_Master · 29.02.2012, 00:32 **[ТС]**

uuuupppp!!!!

@DU · 29.02.2012, 01:09

я бы посоветовал сначало переделать программу так, чтобы она проще понималась. для этого нужно дать переменным более осмысленные имена.
1. перейти от дека с std:

air<int, int> к такой же структуре, но у которой поля имели бы осмысленное название. И текущего не совсем ясно за что отвечает first, а за что second;

C++
1
2
3
4
5
6
7
struct Page
{
   int Id;
   int LastAccessTime;
};
 
std::deque<Page> pages;

Если я правильно понял, то first - это некий идентификатор страниц. Если так, то как в пейдже могут оказаться разные страницы с одним и тем же идентификатором. Иначе, я не понял что такое first.

int mem_size = 5; - это что? максимальное количество страниц? тогда вместо mem_size лучше maxPagesCount;

int array[] = { 1, 2, 3, 4, 5, 2, 3, 4, 1, 5, 4, 1, 3};
Если я правильно понял, то это идентификаторы страниц к которым нужно обратиться в порядке, в котором они представленны в этом массиве. В общем непонятно. Тогда это не массив чего-то, а очередь обращений. В общем нужно придумать что-то более понятное.

Если в цилке идет обращение и каждое обращение происходит в свой момент времени, тогда в цикле переменную i лучше назвать time. Если это означает что-то другое, то я этого не понял.

C++
1
 for(int k = 0; k < mem_size; ++k)

этот цикл левый. в теле цикла примерно такой код:

C++
1
2
3
4
5
6
7
8
9
10
11
for(int k = 0; k < mem_size; ++k)
{
  if (что-то)
  {
     break;
  }
  else
  {
     break;
  }
}

т.е. всегда происходит выход из тела цикла на первой же итерации. переменная к не используется => цикл не нужен

@Visary_Master · 29.02.2012, 09:38 **[ТС]**

А перегрузка операторов потребуется?

@Visary_Master · 02.03.2012, 20:34 **[ТС]**

C++
1
deque<Page> pages;

А как в такую очередь добавлять, удалять из такой очереди что-то, находить минимальный элемент?

Добавлено через 16 минут
uppppp!!!!

Новые блоги и статьи Все статьи Все блоги /
Транслитерация текста с кириллицы на латиницу (вариант №2) Maks 13.11.2026 Обновленная версия ранее созданной обработки. Добавлено: - Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .	Часы с термометром и праздничным календарем yariko 12.11.2026 Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы. Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .	Транслитерация текста с кириллицы на латиницу (вариант №1) Maks 11.11.2026 Решил облегчить жизнь себе и коллегам админам при создании электронных почтовых ящиков для пользователей, в результате написал обработку "Транслитерация текста" с кириллицы на латиницу, а в ней. . .	Книги по геймдизайну, левел-дизайну, игровым механикам и проектированию игрового опыта 8Observer8 08.11.2026 Содержание блога \| English Version 1. 2003 - 06 - Designing Virtual Worlds (1st Edition) Автор: Richard A. Bartle \| Объем: 768 стр. Ссылки: Amazon . . .
Родители токсичные абьюзеры по отношению к своим детям ругают их оскорбляют не любят zorxor 08.11.2026 Жить в атмосфере постоянных оскорблений, критики и холодности со стороны родителей — это тяжелое и болезненное испытание, которое оставляет глубокие эмоциональные раны. Токсичное и абьюзивное. . .	Как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Ответ от Джемени ИИ. zorxor 08.11.2026 Джемени, как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Многие люди, возвращаясь домой, сразу переодеваются в максимально свободную одежду или вовсе предпочитают. . .	Паттерн очереди действий/команд (Action / Command Queue). Система очереди действий и кат-сцен с SDL3 Callbacks, cglm и OpenGL 8Observer8 07.11.2026 Содержание блога \| English Version Руководство для начинающих по реализации паттерна очереди действий/ команд (Action / Command Queue) на C++ (C++20) с использованием официального SDL3 Callbacks. . .	Проверка полного ФИО в типовом справочнике Maks 07.11.2026 Решение реализовано в конфигурации КА2, на примере справочника "КонтактныеЛицаПартнеров". Задача: Запрет инициалов. Не допускаеть использование сокращений вида "И. И. ", "И. И. ", "И И" и. . .

@Visary_Master 17 / 18 / 1 Регистрация: 01.12.2010 Сообщений: 296
	02.02.2012, 14:46 [ТС]
	может мне проще со счетчиком реализовать? deque<pair<int, int> > dq 1й int - элемет последовательности 2й - счетчик... который буду увеличивать, уменьшать. видел как лямбды облегчают жизнь в шарпе, но тут не могу представить. 0

@soon 2554 / 1319 / 178 Регистрация: 09.05.2011 Сообщений: 3,086 Записей в блоге: 1
	02.02.2012, 18:05
	Visary_Master, Если задача выяснить, какая страница реже/чаще всех использовалась, то пожалуйста. Вам функцию поиска помочь составить? 1

@Visary_Master 17 / 18 / 1 Регистрация: 01.12.2010 Сообщений: 296
	02.02.2012, 18:46 [ТС]
	да, помогите... желательно, если возможно с deque<pair<int, int> > dq тогда. 0

@Visary_Master 17 / 18 / 1 Регистрация: 01.12.2010 Сообщений: 296
	29.02.2012, 00:32 [ТС]
	uuuupppp!!!! 0

@Visary_Master 17 / 18 / 1 Регистрация: 01.12.2010 Сообщений: 296
	29.02.2012, 09:38 [ТС]
	А перегрузка операторов потребуется? 0

STL, deque, pair

Решение