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

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

Войти
Регистрация
Восстановить пароль
 
enigma18
0 / 0 / 0
Регистрация: 05.10.2013
Сообщений: 6
#1

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

05.10.2013, 15:21. Просмотров 529. Ответов 10
Метки нет (Все метки)

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

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

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

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

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<>
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.10.2013, 15:21
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Не могу разобраться в vector<> (C++):

Не могу вставить элемент в second(vector) мультимапа. multimap<string, vector<string>> - C++
#include &lt;iostream&gt; #include &lt;map&gt; #include &lt;vector&gt; #include &lt;algorithm&gt; #include &lt;string&gt; #include &lt;iterator&gt; int main() ...

error LNK2019: ссылка на неразрешенный внешний символ "public: __thiscall Vector<int>::Vector<int>(void)" (?0?$Vector@H@@QAE@XZ) в функции _main - C++
//Vector.h #include &lt;iostream&gt; #include &lt;Windows.h&gt; #include &lt;climits&gt; #include &lt;vector&gt; #include &lt;stdlib.h&gt; #include &lt;fstream&gt;...

Как можно увеличить размер вектора, который является элементом вектора vector<vector<int>>arr(n, vector <int>) - C++
Написал программу, которая создает вектор 'а' векторов 'b', вектора 'b' содержат 2 числа. Стало интересно, как нужно изменить программу...

Не могу получить объект по индексу в vector, где же ошибка? - C++
Есть класс class Processor { private: int operationTime; list&lt;Problem*&gt; *taskList; public: Processor(); ...

Ошибка [Linker error] undefined reference to `Vector::Vector(int)' - C++
Добрый день. Делал по методички, и почему-то валятся ошибки... файл lab9_main.cpp #include &lt;iostream&gt; #include &quot;Vector.h&quot; int...

vector<Struct2{int,vector<struct1>}> или множественное наследование ... - C++
Здравствуйте! Помогите, пожалуйста. Есть такие данные: typedef struct { int x; int y; // координаты...

10
Tulosba
:)
Эксперт С++
4397 / 3233 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
05.10.2013, 15:29 #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;
}
Возможны и другие варианты.
1
enigma18
0 / 0 / 0
Регистрация: 05.10.2013
Сообщений: 6
05.10.2013, 15:40  [ТС] #3
Меня больше вот эта строчка интересует :

C++
1
vector < pair < int, pair<int,int> > > g (m);
Это типа двухмерный вектор. Как с ним поступать?
0
Croessmah
Ушел
Эксперт CЭксперт С++
13553 / 7704 / 872
Регистрация: 27.09.2012
Сообщений: 19,006
Записей в блоге: 3
Завершенные тесты: 1
05.10.2013, 15:48 #4
Это вектор ( std::vector ), который хранит в себе пару ( std:air ), у которой первое "поле" ( first ) целочисленное ( int ), а второе значение это пара, у которой оба "поля" целочисленные ( std:air < int , int > )
1
Tulosba
:)
Эксперт С++
4397 / 3233 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
05.10.2013, 16:21 #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);
Становится куда яснее.
1
mat_for_c
164 / 159 / 34
Регистрация: 26.04.2013
Сообщений: 724
Завершенные тесты: 3
05.10.2013, 18:21 #6
Croessmah, Tulosba,
Цитата Сообщение от Tulosba Посмотреть сообщение
Для вывода цикл через итератор:
такой глупый вопрос:
как быстрее выводить ?

через
C++
1
for (it = vec.begin(); it != vec.end(); ++it)
или через
C++
1
for(i = 0; i < vec.size(); ++i)
0
enigma18
0 / 0 / 0
Регистрация: 05.10.2013
Сообщений: 6
05.10.2013, 18:49  [ТС] #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 как то не получается...
0
Tulosba
:)
Эксперт С++
4397 / 3233 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
05.10.2013, 21:26 #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 как то не получается...
А какими значениями хотите инициализировать?
3
sigma7i
1 / 1 / 0
Регистрация: 26.03.2013
Сообщений: 17
05.10.2013, 22:29 #9
Добавлено через 2 минуты
Цитата Сообщение от enigma18 Посмотреть сообщение

А как сделать чтобы сразу инициализировать vector?
как отдельно инициализировать написано в документации, а вот совместно с pair как то не получается...
можно через структуру попробывать?
0
enigma18
0 / 0 / 0
Регистрация: 05.10.2013
Сообщений: 6
05.10.2013, 22:34  [ТС] #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> > >
сбивает с толку что необходимо одновременно инициализировать и внутренности.
0
Tulosba
:)
Эксперт С++
4397 / 3233 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
05.10.2013, 22:54 #11
C++
1
2
vector < pair < int, pair<int,int> > > g;
g.push_back( make_pair( 0, make_pair( 3, 5 ) ) ); // 0 3 5
и т.д.
0
05.10.2013, 22:54
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.10.2013, 22:54
Привет! Вот еще темы с ответами:

Не могу разобраться с С++ - C++
Всем Привет, так я кодеру в Делфи. Не давно нашел что мне нужно но оy написан на С. Вот и начался у меня проблемы с кодами. Вот часть...

не могу разобраться.. - C++
Вывести на экран все натуральные числа из диапазона от A до B, в записи которых цифра 7 встречается ровно N раз. При отсутствии чисел с...

Как корректно скопировать vector в vector внутри класса - C++
Есть класс принимающий в конструкторе vector: class test { test(std::vector&lt;std::string&gt; codeList); ~test(); ...

Указатель на объект вектор в векторе vector < vector<int>* >* - C++
Дело касается вот чего, есть такая вот незатейлевая вещь. #include &lt;vector&gt; #include &lt;iostream&gt; int main( ) { using...


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

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

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