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

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

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

STL, deque, pair - C++

31.01.2012, 13:30. Просмотров 4545. Ответов 60
Метки нет (Все метки)

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

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

C++
1
deque<pair<int, timeval> > last_query
Как работать с такой очередью?
Как пройтись по всем элементам такой очереди?
Как найти минимальный через timeval? // если можно через метод find
Как добавить элемент в очередь, и удалить.
Можно и пройтись по такой очереди с помощью итератора?
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.01.2012, 13:30
Здравствуйте! Я подобрал для вас темы с ответами на вопрос STL, deque, pair (C++):

Контейнер deque <pair> - C++
Есть контейнер deque&lt;pair&lt;int, int&gt;&gt; dq; Делаю вставку dq.push_back(make_pair(100, 100)); dq.push_back(make_pair(80, 80)); ...

STL deque - C++
Устройство, основные операции и их стоимость, особенности использования deque. Ни где не могу найти стоимость выполнения основных...

STL, deque Перераспределение памяти - C++
Есть книга, в ней написано такое о деке Можно ли пример увидеть, а-то чего-то непонятно. Пример когда все итераторы из-за...

Как реализован deque в STL ? - C++
Как реализован deque в STL ? Насколько я понимаю условно все разделяется на блок с адресами и блоки с данными. Есть какие-то...

Реализовать пользовательский класс Pair (упрощённый аналог std::pair) - C++
Здравствуйте. Проблема с выводом. В приложенном задании, требуется сделать вывод как в примере. Мой вывод основан на вводе количества...

STL std::set, std::pair, std::make_pair - C++
Я не знаю как описать тему в двух словах, поэтому не обращайте внимание на название темы. Собственно перейдем к нашим баранам: есть...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Visary_Master
-154 / 16 / 4
Регистрация: 01.12.2010
Сообщений: 297
02.02.2012, 11:53  [ТС] #46
Цитата Сообщение от 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!
0
soon
2540 / 1305 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
02.02.2012, 13:01 #47
Цитата Сообщение от Visary_Master Посмотреть сообщение
Проблема в том, что нужно повторяющемся страницам обновлять время, и одну из них не добавлять....
Есть 2 сравнительно простых способа.
1) Пишете свою функцию, которая ищет по первой переменной в pair.
2) Изучаете лямбду, обновляете компилятор и используете find_if с лямбда функцией. Также можно будет обойтись без struct Comp(написав вместо него соответсвующую лямбду).

Можно, конечно, попробовать заморочится с еще одним функтором. Или с bind-ами(хотя для них тоже нужен будет класс). Но оно того не стоит, имхо.
1
Visary_Master
-154 / 16 / 4
Регистрация: 01.12.2010
Сообщений: 297
02.02.2012, 14:46  [ТС] #48
может мне проще со счетчиком реализовать?
deque<pair<int, int> > dq
1й int - элемет последовательности
2й - счетчик... который буду увеличивать, уменьшать.
видел как лямбды облегчают жизнь в шарпе, но тут не могу представить.
0
soon
2540 / 1305 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
02.02.2012, 17:01 #49
Цитата Сообщение от Visary_Master Посмотреть сообщение
может мне проще со счетчиком реализовать?
Я что-то не представляю, как счетчик может время последнего доступа заменить.
1
Visary_Master
-154 / 16 / 4
Регистрация: 01.12.2010
Сообщений: 297
02.02.2012, 17:33  [ТС] #50
Цитата Сообщение от soon Посмотреть сообщение
Я что-то не представляю, как счетчик может время последнего доступа заменить.
В таблице страниц добавляется запись - счетчик обращений к странице. Чем меньше значение счетчика, тем реже она использовалась.
0
soon
2540 / 1305 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
02.02.2012, 18:05 #51
Visary_Master, Если задача выяснить, какая страница реже/чаще всех использовалась, то пожалуйста. Вам функцию поиска помочь составить?
1
Visary_Master
-154 / 16 / 4
Регистрация: 01.12.2010
Сообщений: 297
02.02.2012, 18:46  [ТС] #52
да, помогите... желательно, если возможно с deque<pair<int, int> > dq тогда.
0
soon
2540 / 1305 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
02.02.2012, 19:16 #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
#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;
}
3
Visary_Master
-154 / 16 / 4
Регистрация: 01.12.2010
Сообщений: 297
16.02.2012, 09:38  [ТС] #54
Цитата Сообщение от soon Посмотреть сообщение
C
1
f -> second = i * 10;
А что делается в это строчке?

Добавлено через 13 минут
Цитата Сообщение от soon Посмотреть сообщение
C
1
std::size_t i = 0;
Какой тип у переменной i?
0
silent_1991
Эксперт С++
4964 / 3040 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
16.02.2012, 09:42 #55
Цитата Сообщение от Visary_Master Посмотреть сообщение
А что делается в это строчке?
Присваивается значение i * 10 члену second объекта класса std::pair, находящегося по итератору f.

Цитата Сообщение от Visary_Master Посмотреть сообщение
Какой тип у переменной i?
std::size_t. Псевдоним unsigned int.
1
Visary_Master
-154 / 16 / 4
Регистрация: 01.12.2010
Сообщений: 297
26.02.2012, 22:55  [ТС] #56
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;   
}
Вот что у меня получилось, но есть моменты, где счетчик не прибавляется и возникают повторения страниц.
0
Visary_Master
-154 / 16 / 4
Регистрация: 01.12.2010
Сообщений: 297
29.02.2012, 00:32  [ТС] #57
uuuupppp!!!!
0
DU
1483 / 1059 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
29.02.2012, 01:09 #58
я бы посоветовал сначало переделать программу так, чтобы она проще понималась. для этого нужно дать переменным более осмысленные имена.
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;
  }
}
т.е. всегда происходит выход из тела цикла на первой же итерации. переменная к не используется => цикл не нужен
1
Visary_Master
-154 / 16 / 4
Регистрация: 01.12.2010
Сообщений: 297
29.02.2012, 09:38  [ТС] #59
А перегрузка операторов потребуется?
0
Visary_Master
-154 / 16 / 4
Регистрация: 01.12.2010
Сообщений: 297
02.03.2012, 20:34  [ТС] #60
C++
1
deque<Page> pages;
А как в такую очередь добавлять, удалять из такой очереди что-то, находить минимальный элемент?

Добавлено через 16 минут
uppppp!!!!
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.03.2012, 20:34
Привет! Вот еще темы с ответами:

Как считать данные в vector<pair<int, pair<int, int>>> arr(m) ? - C++
Здравствуйте! Помогите, как считать данные данные в массив такого типа? vector&lt;pair&lt;int, pair&lt;int, int&gt;&gt;&gt; arr(m) Пытался вот так...

Compair deque - C++
есть два списка. Теперь мне нужно сравнить элементы если х &lt;у то return (x+y) . я так думаю надо результат в 3 список записать как мне...

std::deque - C++
Как известно при добавлении в конец вектора элементов(и не только в конец) может возникнуть перераспределение памяти что переместит данные...

Контейнер deque - C++
Задание:(используя контейнер deque) ввести последовательность натуральных чисел,у конце которой 0.Не сохраняя всей последовательности в...


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

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

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