17 / 18 / 1
Регистрация: 01.12.2010
Сообщений: 296
1

STL, deque, pair

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

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

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

C++
1
deque<pair<int, timeval> > last_query
Как работать с такой очередью?
Как пройтись по всем элементам такой очереди?
Как найти минимальный через timeval? // если можно через метод find
Как добавить элемент в очередь, и удалить.
Можно и пройтись по такой очереди с помощью итератора?
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
31.01.2012, 13:30
Ответы с готовыми решениями:

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

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

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

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

60
2554 / 1319 / 178
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
01.02.2012, 02:54 21
Author24 — интернет-сервис помощи студентам
Цитата Сообщение от Visary_Master Посмотреть сообщение
может ничего не происходит тут:
Да. Я даже не смотрел туда.
Память-то не выделена под элементы очереди. Либо resize, либо push_back. На cplusplus посмотрите примеры.
Да и условие в цикле странное. Почему через запятую?
1
17 / 18 / 1
Регистрация: 01.12.2010
Сообщений: 296
01.02.2012, 02:58  [ТС] 22
Цитата Сообщение от soon Посмотреть сообщение
Да и условие в цикле странное. Почему через запятую?
потому, что 2 условия

Добавлено через 30 секунд
Цитата Сообщение от soon Посмотреть сообщение
либо push_back
подумал об этом.
Вот, вроде получилось:
C++
1
2
3
4
5
6
7
8
9
10
11
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));
            
         }
    }
0
2554 / 1319 / 178
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
01.02.2012, 03:07 23
Цитата Сообщение от Visary_Master Посмотреть сообщение
потому, что 2 условия
Ага. Сравните
C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
 
int main()
{
    for(int i = 0, j = 5; i > 5 && --j; ++i)
        std::cout << 1 << ' ';
    std::cout << std::endl;
    for(int i = 0, j = 5; i > 5, (--j); ++i)
        std::cout << 2 << ' ';
    std::cout << std::endl;
    return 0;
}
Только почему там предупреждение не выбило - непонятно.

Цитата Сообщение от Visary_Master Посмотреть сообщение
Вот, вроде получилось:
Ну вот и ладушки
1
17 / 18 / 1
Регистрация: 01.12.2010
Сообщений: 296
01.02.2012, 03:17  [ТС] 24
Цитата Сообщение от soon Посмотреть сообщение
Ага. Сравните
C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
 
int main()
{
    for(int i = 0, j = 5; i > 5 && --j; ++i)
        std::cout << 1 << ' ';
    std::cout << std::endl;
    for(int i = 0, j = 5; i > 5, (--j); ++i)
        std::cout << 2 << ' ';
    std::cout << std::endl;
    return 0;
}
Только почему там предупреждение не выбило - непонятно.
Дело в том, что нельзя сделать так:
for(int i = 0, double k = 0.0; ... ...)
разные типы, и компилятор вроде не будет понимать, что две переменные разного типа.

Вывод при том(5-размер очереди...):

0 1328051249 799902
1 1328051249 799904
2 1328051249 799906
3 1328051249 799907
4 1328051249 799909
Добавлено через 3 минуты
Цитата Сообщение от Visary_Master Посмотреть сообщение
i > 5 && --j
точка с запятой там стоит

Добавлено через 2 минуты
осталось сделать поиск, и заменить дольше всех не использующуюся.
0
2554 / 1319 / 178
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
01.02.2012, 03:19 25
Цитата Сообщение от Visary_Master Посмотреть сообщение
Дело в том, что нельзя сделать так:
for(int i = 0, double k = 0.0; ... ...)
Дело не в этом
Цитата Сообщение от Visary_Master Посмотреть сообщение
for(deque<pair<int, timeval> >::iterator j = dq1.begin(); j != dq1.end(),(k<mem_size); ++j,++k)
В условии запятая.
0
17 / 18 / 1
Регистрация: 01.12.2010
Сообщений: 296
01.02.2012, 03:20  [ТС] 26
условия через запятую прописываются.

Подумал... а на while так то не разбить вроде...
Придется превращать в одно условие с &&
0
2554 / 1319 / 178
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
01.02.2012, 03:27 27
Цитата Сообщение от Visary_Master Посмотреть сообщение
условия через запятую прописываются.
Я вам для чего в посте #23 пример привел?
Если лень компилировать и проверять
http://liveworkspace.org/code/... 7de82e6b66
1
17 / 18 / 1
Регистрация: 01.12.2010
Сообщений: 296
01.02.2012, 03:54  [ТС] 28
дошло...
warning: left operand of comma operator has no effect [-Wunused-value]
компилю g++

Добавлено через 18 минут
Дело думаю в том, что в 1м случае задается условие для обеих переменных, а во втором для отдельных.
пример:
C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
 
int main()
{
    for(int i = 0, j = 5; i > 5 || --j; ++i)
        std::cout << 1 << ' ';
    std::cout << std::endl;
    for(int i = 0, j = 5; i > 5, (--j); ++i)
        std::cout << 2 << ' ';
    std::cout << std::endl;
    return 0;
}
http://liveworkspace.org/code/... e21cb7f50e
Господи... это еще и разные вещи, у себя не могу исправить.
0
2554 / 1319 / 178
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
01.02.2012, 04:07 29
Цитата Сообщение от Visary_Master Посмотреть сообщение
Дело думаю в том, что в 1м случае задается условие для обеих переменных, а во втором для отдельных.
пример:
Оператор запятая последовательно выполняет выражения слева направо, и возвращает результат крайнего правого выражения.
А цикл у вас неправильно построен. Смысл заводить для dq1 итератор, если там нет ни одного элемента? И k пройдет одну итерацию цикла i, и больше не будет увеличиваться.
1
17 / 18 / 1
Регистрация: 01.12.2010
Сообщений: 296
01.02.2012, 12:14  [ТС] 30
хорошо, я проверю... поможете с поиском?
0
2554 / 1319 / 178
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
01.02.2012, 12:22 31
Перегружаете < для timeval и используете std::min_element + нужен функтор. Функтор можете взять из кода на первой странице. Ну и перегрузку оттуда можете взять, только ее подправить нужно будет, я же для своего класса реализовывал.
1
17 / 18 / 1
Регистрация: 01.12.2010
Сообщений: 296
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
Эксперт С++
3646 / 1378 / 243
Регистрация: 16.04.2009
Сообщений: 4,526
01.02.2012, 15:20 33
Цитата Сообщение от Visary_Master Посмотреть сообщение
Правильно?
Да. Как вариант const добавить.
1
17 / 18 / 1
Регистрация: 01.12.2010
Сообщений: 296
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
Эксперт С++
3646 / 1378 / 243
Регистрация: 16.04.2009
Сообщений: 4,526
01.02.2012, 18:52 35
Visary_Master, можете конкретно задание сказать?
Цитата Сообщение от Visary_Master Посмотреть сообщение
Не могу разобраться, перегружая функтор, какие мы параметры должны передавать ему?
Вроде правильно.
0
17 / 18 / 1
Регистрация: 01.12.2010
Сообщений: 296
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
Эксперт С++
3646 / 1378 / 243
Регистрация: 16.04.2009
Сообщений: 4,526
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
17 / 18 / 1
Регистрация: 01.12.2010
Сообщений: 296
01.02.2012, 20:09  [ТС] 38
Нет, не пробовал, ваш код не компилится.
Сейчас попробую, как говорил, soon.

Добавлено через 5 минут
Получилось сделать(магическим образом), так, как говорил soon...
0
go
Эксперт С++
3646 / 1378 / 243
Регистрация: 16.04.2009
Сообщений: 4,526
01.02.2012, 20:10 39
Цитата Сообщение от Visary_Master Посмотреть сообщение
ваш код не компилится.
C++
1
typedef std::pair<T_str, int>    T_pair;
Здесь меняли что-нибудь?
0
17 / 18 / 1
Регистрация: 01.12.2010
Сообщений: 296
01.02.2012, 20:11  [ТС] 40
Теперь нужно сделать удаление этого минимального элемента...
0
01.02.2012, 20:11
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
01.02.2012, 20:11
Помогаю со студенческими работами здесь

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

Как в vector<pair <класс, int> > добавлять свой объект в качестве первого элемента pair?
#include&lt;iostream&gt; #include &quot;Employee.h&quot; #include&lt;string&gt; #include&lt;algorithm&gt; #include&lt;vector&gt;...

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

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


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

Или воспользуйтесь поиском по форуму:
40
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru