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

Не могу разобраться в vector<> - C++

Восстановить пароль Регистрация
 
enigma18
0 / 0 / 0
Регистрация: 05.10.2013
Сообщений: 6
05.10.2013, 15:21     Не могу разобраться в vector<> #1
Доброго времени суток.
Не могу понять реализацию вектора, да и вообще с векторами плохо знакома.

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

Вот код:
Кстати это алгоритм Крускала(теория графов: Минимальное островное дерево")

Кликните здесь для просмотра всего текста

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 <vector>
#include <algorithm>
#include <iostream>
 
using namespace std;
 
int main()
{
 
int m;
int n;
vector < pair < int, pair<int,int> > > g (m); // вес - вершина 1 - вершина 2
 
int cost = 0;
vector < pair<int,int> > res;
 
sort (g.begin(), g.end());
vector<int> tree_id (n);
for (int i=0; i<n; ++i)
    tree_id[i] = i;
for (int i=0; i<m; ++i)
{
    int a = g[i].second.first,  b = g[i].second.second,  l = g[i].first; // ??
    if (tree_id[a] != tree_id[b])
    {
        cost += l;
        res.push_back (make_pair (a, b));
        int old_id = tree_id[b],  new_id = tree_id[a];
        for (int j=0; j<n; ++j)
            if (tree_id[j] == old_id)
                tree_id[j] = new_id;
    }
}
}


взято с сайта e-maxx

у меня даже вводные данные есть)

Sample input
5 8
0 3 5
0 1 1
0 2 3
2 1 6
2 3 1
4 1 3
4 2 2
4 3 2

Вот что должно получится.
2 3 1
0 1 1
4 2 2
0 2 3

И что значит .first . second? Про них вообще ничего не написано. Остальное все понятно.

Если найдется добрая душа может покажете мне как этот же алгоритм реализуется еще на list<>
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.10.2013, 15:21     Не могу разобраться в vector<>
Посмотрите здесь:

C++ не могу разобраться
C++ Не могу разобраться в С++
C++ не могу разобраться
C++ не могу разобраться
Не могу разобраться C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Tulosba
:)
Эксперт C++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
05.10.2013, 15:29     Не могу разобраться в vector<> #2
Цитата Сообщение от enigma18 Посмотреть сообщение
И что значит .first . second?
Это поля структуры std::pair
Цитата Сообщение от enigma18 Посмотреть сообщение
Мне бы только показать, как ввести данные и вывести,
для добавления в вектор используйте метод push_back. Для вывода цикл через итератор:
C++
1
2
3
4
for( auto it = v.begin(); v != v.end(); ++it )
{
   std::cout << *it << std::endl;
}
Возможны и другие варианты.
enigma18
0 / 0 / 0
Регистрация: 05.10.2013
Сообщений: 6
05.10.2013, 15:40  [ТС]     Не могу разобраться в vector<> #3
Меня больше вот эта строчка интересует :

C++
1
vector < pair < int, pair<int,int> > > g (m);
Это типа двухмерный вектор. Как с ним поступать?
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11817 / 6796 / 769
Регистрация: 27.09.2012
Сообщений: 16,867
Записей в блоге: 2
Завершенные тесты: 1
05.10.2013, 15:48     Не могу разобраться в vector<> #4
Это вектор ( std::vector ), который хранит в себе пару ( std:air ), у которой первое "поле" ( first ) целочисленное ( int ), а второе значение это пара, у которой оба "поля" целочисленные ( std:air < int , int > )
Tulosba
:)
Эксперт C++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
05.10.2013, 16:21     Не могу разобраться в vector<> #5
C++
1
vector < pair < int, pair<int,int> > > g (m);
Вообще, такие вложенные типы хорошо бы разворачивать для удобства чтения:
C++
1
2
3
using integerDuo = pair<int,int>;
using integerTrio = pair<int, integerDuo>;
vector<integerTrio> g(m);
Становится куда яснее.
mat_for_c
 Аватар для mat_for_c
115 / 110 / 19
Регистрация: 26.04.2013
Сообщений: 585
Завершенные тесты: 2
05.10.2013, 18:21     Не могу разобраться в vector<> #6
Croessmah, Tulosba,
Цитата Сообщение от Tulosba Посмотреть сообщение
Для вывода цикл через итератор:
такой глупый вопрос:
как быстрее выводить ?

через
C++
1
for (it = vec.begin(); it != vec.end(); ++it)
или через
C++
1
for(i = 0; i < vec.size(); ++i)
enigma18
0 / 0 / 0
Регистрация: 05.10.2013
Сообщений: 6
05.10.2013, 18:49  [ТС]     Не могу разобраться в vector<> #7
Ура ура!
Получилось, хотя бы вывести

вот код если кому понадобится :

Кликните здесь для просмотра всего текста
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
#include <vector>
#include <algorithm>
#include <iostream>
 
using namespace std;
 
int main()
{
 
int m=8; // ребра
int n=5; // вершины
 
vector < pair < int, pair<int,int> > > g (m);
 
for(int i =0; i<m; ++i )
{
    std::cin>> g[i].second.first >> g[i].second.second >> g[i].first; // вводим числа.
}
 
 
int cost = 0;
vector < pair < int, pair<int,int> > > res;
 
sort (g.begin(), g.end());
vector<int> tree_id (n);
for (int i=0; i<n; ++i)
    tree_id[i] = i;
for (int i=0; i<m; ++i)
{
    int a = g[i].second.first,  b = g[i].second.second,  l = g[i].first; 
    if (tree_id[a] != tree_id[b])
    {
        cost += l;
        res.push_back (make_pair (a, make_pair(b,l)));
        int old_id = tree_id[b],  new_id = tree_id[a];
        for (int j=0; j<n; ++j)
            if (tree_id[j] == old_id)
                tree_id[j] = new_id;
    }
}
 
for(int i = 0; i !=res.size(); ++i)
    cout << res[i].first << " " << res[i].second.first << " " << res[i].second.second<< endl; // выводим
 
}


правда не получилось через вот этот цикл сделать
for( auto it = v.begin(); v != v.end(); ++it )

А как сделать чтобы сразу инициализировать vector?
как отдельно инициализировать написано в документации, а вот совместно с pair как то не получается...
Tulosba
:)
Эксперт C++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
05.10.2013, 21:26     Не могу разобраться в vector<> #8
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от mat_for_c Посмотреть сообщение
как быстрее выводить ?
Через индекс получилось быстрее http://ideone.com/d7sM9S
Но это вовсе не значит, что во всех реализациях будет так же. К тому же, основная нагрузка идет всё же в теле цикла, а значит то, как идет переход от элемента к элемента не так уж и важно в большинстве случаев.
Цитата Сообщение от enigma18 Посмотреть сообщение
правда не получилось через вот этот цикл сделать
for( auto it = v.begin(); v != v.end(); ++it )
Тут у меня опечатка закралась. Должно быть так:
C++
1
for( auto it = v.begin(); it != v.end(); ++it )
Но если с auto работать не будет, то попробуйте такой вариант:
C++
1
for( std::vector<type>::iterator it = v.begin(); it != v.end(); ++it )
где type - тип элементов вектора.

Добавлено через 1 минуту
Цитата Сообщение от enigma18 Посмотреть сообщение
А как сделать чтобы сразу инициализировать vector?
как отдельно инициализировать написано в документации, а вот совместно с pair как то не получается...
А какими значениями хотите инициализировать?
sigma7i
 Аватар для sigma7i
1 / 1 / 0
Регистрация: 26.03.2013
Сообщений: 17
05.10.2013, 22:29     Не могу разобраться в vector<> #9
Добавлено через 2 минуты
Цитата Сообщение от enigma18 Посмотреть сообщение

А как сделать чтобы сразу инициализировать vector?
как отдельно инициализировать написано в документации, а вот совместно с pair как то не получается...
можно через структуру попробывать?
enigma18
0 / 0 / 0
Регистрация: 05.10.2013
Сообщений: 6
05.10.2013, 22:34  [ТС]     Не могу разобраться в vector<> #10
Цитата Сообщение от Tulosba Посмотреть сообщение
Добавлено через 1 минуту

А какими значениями хотите инициализировать?
простыми целочислинными значениями.

0 3 5
0 1 1
0 2 3
2 1 6
2 3 1
4 1 3
4 2 2
4 3 2

но приходится вручную набивать таким образом:

C++
1
2
3
4
for(int i =0; i<m; ++i )
{
    std::cin>> g[i].second.first >> g[i].second.second >> g[i].first; // вводим числа.
}
вся загвоздка именно в том что vector имеет такую конструкцию:

C++
1
vector < pair < int, pair<int,int> > >
сбивает с толку что необходимо одновременно инициализировать и внутренности.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.10.2013, 22:54     Не могу разобраться в vector<>
Еще ссылки по теме:

C++ Не могу получить объект по индексу в vector, где же ошибка?
C++ Не могу разобраться
Не могу разобраться в if C++

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

Или воспользуйтесь поиском по форуму:
Tulosba
:)
Эксперт C++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
05.10.2013, 22:54     Не могу разобраться в vector<> #11
C++
1
2
vector < pair < int, pair<int,int> > > g;
g.push_back( make_pair( 0, make_pair( 3, 5 ) ) ); // 0 3 5
и т.д.
Yandex
Объявления
05.10.2013, 22:54     Не могу разобраться в vector<>
Ответ Создать тему
Опции темы

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