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

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

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

STL, deque, pair - C++

31.01.2012, 13:30. Просмотров 4544. Ответов 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++
Я не знаю как описать тему в двух словах, поэтому не обращайте внимание на название темы. Собственно перейдем к нашим баранам: есть...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
soon
2540 / 1305 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
01.02.2012, 12:22 #31
Перегружаете < для timeval и используете std::min_element + нужен функтор. Функтор можете взять из кода на первой странице. Ну и перегрузку оттуда можете взять, только ее подправить нужно будет, я же для своего класса реализовывал.
1
Visary_Master
-154 / 16 / 4
Регистрация: 01.12.2010
Сообщений: 297
01.02.2012, 15:12  [ТС] #32
Перегружаю оператор так:
C++
1
2
3
4
bool operator < (const timeval& tv1, const timeval& tv2)
{
    return tv1.tv_sec < tv2.tv_sec;
}
Правильно?
0
go
Эксперт C++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
01.02.2012, 15:20 #33
Цитата Сообщение от Visary_Master Посмотреть сообщение
Правильно?
Да. Как вариант const добавить.
1
Visary_Master
-154 / 16 / 4
Регистрация: 01.12.2010
Сообщений: 297
01.02.2012, 18:50  [ТС] #34
Не могу разобраться, перегружая функтор, какие мы параметры должны передавать ему?

Или полностью можно взять кусок кода?

C++
1
2
3
4
5
6
7
8
template <class T>
struct Comp
{
    bool operator () (const T& f, const T& l)
    {
        return f.second < l.second;
    }
};
0
go
Эксперт C++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
01.02.2012, 18:52 #35
Visary_Master, можете конкретно задание сказать?
Цитата Сообщение от Visary_Master Посмотреть сообщение
Не могу разобраться, перегружая функтор, какие мы параметры должны передавать ему?
Вроде правильно.
0
Visary_Master
-154 / 16 / 4
Регистрация: 01.12.2010
Сообщений: 297
01.02.2012, 19:06  [ТС] #36
Нужно реализовать алгоритм LRU с помощью такой двусторонней очереди(ограниченной по размеру 5 ячеек):
deque<pair<int, timeval> >dq
timeval - структура, которая возвращает время с помощью gettimeofday().
Задаем последовательность:
1 2 3 4 5 2 1 2 3 4 3 1 2 3 4 1 2 3
Добавляем в очередь страницы:
1 2 3 4 5
далее страница 2, она есть в памяти
удаляем дольше всех не использовавшуюся страницу, на ее место помещаем страницу 2, а ту страницу с 2, которая дублируется, удаляем... (если я правильно понимаю).
И так далее.
Проблема в том, что я вообще плохо знаю STL. А это хороший вариант как мне кажется(вот бы его реализовать...)
И еще, алгоритм LRU, который зарегламентирован, он должен содержать счетчик, тогда хватило бы обычной очереди думаю. Но с gettimeofday мы смотрим по времени обращения...

Дошел до того, что нужно в такой очереди найти самое маленькое время.
0
go
Эксперт C++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
01.02.2012, 19:44 #37
Цитата Сообщение от Visary_Master Посмотреть сообщение
Дошел до того, что нужно в такой очереди найти самое маленькое время.
C++
1
2
3
4
5
6
7
8
typedef std::pair<T_str, int>    T_pair;
 
 
std::cout << std::min_element(dq.begin(), dq.end(), 
                     [] ( T_pair (a), T_pair (b)) 
                        { return a.second < b.second; })
             -> first; 
          << std::endl;
Так пробовали?
0
Visary_Master
-154 / 16 / 4
Регистрация: 01.12.2010
Сообщений: 297
01.02.2012, 20:09  [ТС] #38
Нет, не пробовал, ваш код не компилится.
Сейчас попробую, как говорил, soon.

Добавлено через 5 минут
Получилось сделать(магическим образом), так, как говорил soon...
0
go
Эксперт C++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
01.02.2012, 20:10 #39
Цитата Сообщение от Visary_Master Посмотреть сообщение
ваш код не компилится.
C++
1
typedef std::pair<T_str, int>    T_pair;
Здесь меняли что-нибудь?
0
Visary_Master
-154 / 16 / 4
Регистрация: 01.12.2010
Сообщений: 297
01.02.2012, 20:11  [ТС] #40
Теперь нужно сделать удаление этого минимального элемента...
0
go
Эксперт C++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
01.02.2012, 20:14 #41
C++
1
mydeque.erase (it);
1
Visary_Master
-154 / 16 / 4
Регистрация: 01.12.2010
Сообщений: 297
01.02.2012, 20:15  [ТС] #42
Цитата Сообщение от 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);
а перегружать ничего не надо?
0
soon
2540 / 1305 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
01.02.2012, 20:17 #43
Цитата Сообщение от Visary_Master Посмотреть сообщение
int *array = new int[n];
Первое что бросается в глаза. Выделяете память и не освобождаете.

Добавлено через 54 секунды
Цитата Сообщение от Visary_Master Посмотреть сообщение
а перегружать ничего не надо?
Нет. Это член класса deque.
1
go
Эксперт C++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
01.02.2012, 20:18 #44
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; 
                     }  )
);
0
soon
2540 / 1305 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
01.02.2012, 20:21 #45
Цитата Сообщение от 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));
    }
}
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.02.2012, 20:21
Привет! Вот еще темы с ответами:

Как считать данные в 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
Объявления
01.02.2012, 20:21
Ответ Создать тему
Опции темы

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