Использование вектора push_back с парой

Question

Я смотрел на реализацию алгоритма Прима на geeksforgeeks.org и пытался реализовать эту функцию в режиме практики. Я посмотрел, как был получен вход, и увидел это:

#include<bits/stdc++.h>
using namespace std;

const int MAX = 1e4 + 5;

int spanningTree(vector <pair<int,int> > g[], int n);

int main()
{
    int t ;
    cin>>t;
    while(t--)
    {
        vector <pair<int,int> > adj[MAX];
        int n,e;
        int w, mC;
        cin >> n>> e;
        for(int i = 0;i < e;++i)
        {
            int x,y;
            cin >> x >> y >> w;
            adj[x].push_back({w, y});
            adj[y].push_back({w, x});
        }

        mC= spanningTree(adj, MAX);
        cout << mC << endl;
    }
    return 0;
}

У меня много проблем с пониманием того, как они используют vector. Я никогда не видел передачу вектора подобным массиву: vector <pair<int,int> > g[].

Я посмотрел на реализацию STD vector и не смог ничего найти о прохождении вектора таким образом или о создании вектора с vector <pair<int,int> > adj[MAX];.

Наконец, я очень озадачен тем, что делает следующий код:

adj[x].push_back({w, y});
adj[y].push_back({w, x});

Я пытался реализовать это сам:

#include <iostream>
#include <vector>
#include <utility>
#include <string>

using namespace std;

int main()
{
    vector< pair<string, int> > vec[2];
    vec[0].push_back({"One", 1});

    vec[1].push_back({"Two", 2});

    for(int x = 0; x < 2; ++x){
        cout << vec[x].first << ", " << vec[x].second << endl;
    }

    return 0;
}

Но я получаю ошибку class 'std::vector< pair<string, int> >' has no member named ‘first’.

Если бы я мог помочь с пониманием того, как здесь используется * 1021, я был бы очень признателен Я уже просмотрел несколько сообщений StackOverflow, включая vector :: push_back vs vector :: operator [] .

Ссылка на исходную задачу: здесь

Answer 1

Я никогда не видел передачу вектора подобным массиву: vector <pair<int,int> > g[]

Это это массив! Массив векторов.

Проблема с вашим кодом в том, что у вас есть два вектора, оба с одним элементом, и ваш цикл извлекает только векторы ... а не их единственный элемент.

Ваша версия будет:

#include <iostream>
#include <vector>
#include <utility>
#include <string>

using namespace std;

int main()
{
    vector< pair<string, int> > vec[2];
    vec[0].push_back({"One", 1});

    vec[1].push_back({"Two", 2});

    for(int x = 0; x < 2; ++x){
        cout << vec[x][0].first << ", " << vec[x][0].second << endl;
    }

    return 0;
}

Все, что я добавил, было [0] (индекс для каждого вектора).

Конечно, такой пример имеет сомнительную практичность. В такой ситуации может показаться, что вам нужен один вектор с двумя элементами и без видимых массивов.

Если честно, я не в восторге от оригинального кода. Смешивание массивов и векторов - рецепт путаницы ( hyello ); они могли бы использовать «2D-векторы» или, что лучше, 1D-вектор с 2D-индексами, наложенными поверх него. В этом случае также будет гораздо лучше локальность кэша.

Answer 2

Это массив векторов в стиле C, здесь действительно нет ничего волшебного.

int spanningTree(vector <pair<int,int> > g[], int n);

Может быть, вы видели что-то подобное раньше:

int foo( int array[], int n);

В своем коде элементы массива не int с, а std::vector с. Почему они смешивают простые массивы и std::vector Я не могу вам сказать.

В вашем примере вам необходимо сначала использовать operator[] для доступа к элементу, прежде чем вы сможете получить доступ к .first и .second, или использовать front для получения первого элемента:

for(int x = 0; x < 2; ++x){
    cout << vec[x].front().first << ", " << vec[x].front().second << endl;
}