Overloading subscript operator in vector

help
,
1

say I have a pair a
can I define a function such that
x[a] gives me x[a.first][a.second]
I did not know how much I needed this until I had to write this.

    int ans=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(grid[i][j] && !found[i][j]){
                ++ans;
                found[i][j]=1;
                queue<pair<int, int>> q;
                q.push(mp(i,j));
                while(!q.empty()){
                    for(const auto &path : dir){
                        auto next=q.front()+path;
                        if(valid(next) && grid[next.first][next.second] && !found[next.first][next.second] && check(q.front(), next)){
                            found[(q.front()+path).first][(q.front() + path).second]=1;
                            q.push(q.front() + path);
                        }
                    }
                    q.pop();
                }
            }
        }
    }
    cout<<ans<<'\n';

I already tried this

template<typename T>
T& operator-(const vector<vector<T>> &seq, const pair<int , int> &idx){
    return seq[idx.first][idx.second];
}

but I get a compilation error

c:\Users\Public\My-codes\639D.cpp: In instantiation of 'T& operator-(const std::vector<std::vector<_Tp> >&, const std::pair<int, int>&) [with T = bool]':
c:\Users\Public\My-codes\639D.cpp:164:48:   required from here
c:\Users\Public\My-codes\639D.cpp:35:26: error: cannot bind non-const lvalue reference of type 'bool&' to an rvalue of type 'std::vector<bool>::const_reference' {aka 'bool'}
   35 |     return seq[idx.first][idx.second];
      |            ~~~~~~~~~~~~~~^

@ssjgz Do you know how to do this?

Full code(Very long) 
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb push_back
#define vi vector<int>
using namespace std;
template<typename T>
ostream& operator+(ostream& out, const vector<T> &vec){
    for(const auto &x : vec){
        out<<x<<" ";
    }
    out<<"\n";
    return out;
}
template<typename T>
ostream& operator*(ostream& out, const vector<T> &vec){
    for(const auto &x : vec){
        out+x;
    }
    return out;
}
template<typename T>
istream& operator>>(istream& in, vector<T> &vec){
    for(auto &x : vec){
        in>>x;
    }
    return in;
}
template<typename T>
T& operator-(const vector<vector<T>> &seq, const pair<int , int> &idx){
    return seq[idx.first][idx.second];
}
pair<int, int> operator+(const pair<int, int> &x, const pair<int, int> &y){
    return mp(x.first + y.first, x.second + y.second);
}
void solve(){
    int n,m;
    cin>>n>>m;
    vector<vector<bool>> grid(n, vector<bool>(m,0));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            char type;
            cin>>type;
            grid[i][j]=(type=='#');
        }
    }
    vector<vector<bool>> southposs(n, vector<bool>(m, 1));
    for(int i=0;i<n;i++){
        bool foundgood=0, foundbad=0;
        for(int j=0;j<m;j++){
            if(grid[i][j]){
                foundgood=1;
            }
            if(foundgood && !grid[i][j]){
                foundbad=1;
            }
            if(foundgood && foundbad){
                southposs[i][j]=0;
            }
        }
    }
    for(int i=0;i<n;i++){
        bool foundgood=0, foundbad=0;
        for(int j=m-1;j>=0;--j){
            if(grid[i][j]){
                foundgood=1;
            }
            if(foundgood && !grid[i][j]){
                foundbad=1;
            }
            if(foundgood && foundbad){
                southposs[i][j]=0;
            }
        }
    }
    for(int i=0;i<m;i++){
        bool foundgood=0, foundbad=0;
        for(int j=0;j<n;j++){
            if(grid[j][i]){
                foundgood=1;
            }
            if(foundgood && !grid[j][i]){
                foundbad=1;
            }
            if(foundgood && foundbad){
                southposs[j][i]=0;
            }
        }
    }
    for(int i=0;i<m;i++){
        bool foundgood=0, foundbad=0;
        for(int j=n-1;j>=0;--j){
            if(grid[j][i]){
                foundgood=1;
            }
            if(foundgood && !grid[j][i]){
                foundbad=1;
            }
            if(foundgood && foundbad){
                southposs[j][i]=0;
            }
        }
    }
    vector<vector<int>> prefixrow(n, vector<int>(m+1, 0));
    vector<vector<int>> prefixcol(n+1, vector<int>(m, 0));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            prefixrow[i][j+1]=prefixrow[i][j]+southposs[i][j];
            prefixcol[i+1][j]=prefixcol[i][j]+southposs[i][j];
        }
    }
    for(int i=0;i<n;i++){
        if(prefixrow[i][m]==0){
            cout<<"-1\n";
            return;
        }
    }
    for(int i=0;i<m;i++){
        if(prefixcol[n][i]==0){
            cout<<"-1\n";
            return;
        }
    }
    auto valid=[&](const pair<int, int> &x){
        return x.first<n && x.first>=0 && x.second>=0 && x.second<m;
    };
    auto check=[&](const pair<int, int> a, const pair<int, int> &b){
        int x=a.first, x2=b.first, y=a.second, y2=b.second;
        if(x!=x2){
            if(x2>x){
                return ((prefixcol[n][y]-prefixcol[x][y])>0);
            }
            else{
                return (prefixcol[x][y]>0);
            }
        }
        if(y!=y2){
            if(y2>y){
                return ((prefixrow[x][m]-prefixrow[x][y])>0);
            }
            else{
                return (prefixrow[x][y]>0);
            }
        }
        return false;
    };
    vector<pair<int, int>> dir={{1,0},{-1,0},{0,1},{0,-1}};
    vector<vector<bool>> found(n, vector<bool>(m,0));
    int ans=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(grid[i][j] && !found[i][j]){
                ++ans;
                found[i][j]=1;
                queue<pair<int, int>> q;
                q.push(mp(i,j));
                while(!q.empty()){
                    for(const auto &path : dir){
                        auto next=q.front()+path;
                        if(valid(next) && grid-next && !(found-next) && check(q.front(), next)){
                            found-next=1;
                            q.push(next);
                        }
                    }
                    q.pop();
                }
            }
        }
    }
    cout<<ans<<'\n';
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}
2

I can’t think of any way of doing precisely what you want, offhand.

Can you change all occurrences of

vector<bool>

to

vector<char>

and see if the error goes away? If not, please post full code so I can compile it locally :slight_smile:

2 Likes
3

I tried overloading with - but I can’t give a non const reference to a bool.
Added full code.
Here’s the problem link if you want to check whether it still works correctly.

4

I haven’t dared to try and run it, but this compiles, at least:

#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb push_back
#define vi vector<int>
using namespace std;
template<typename T>
ostream& operator+(ostream& out, const vector<T> &vec){
    for(const auto &x : vec){
        out<<x<<" ";
    }
    out<<"\n";
    return out;
}
template<typename T>
ostream& operator*(ostream& out, const vector<T> &vec){
    for(const auto &x : vec){
        out+x;
    }
    return out;
}
template<typename T>
istream& operator>>(istream& in, vector<T> &vec){
    for(auto &x : vec){
        in>>x;
    }
    return in;
}
template<typename T>
decltype(auto) operator-(const vector<vector<T>> &seq, const pair<int , int> &idx){
    return seq[idx.first][idx.second];
}
template<typename T>
decltype(auto) operator-(vector<vector<T>> &seq, const pair<int , int> &idx){
    return seq[idx.first][idx.second];
}
pair<int, int> operator+(const pair<int, int> &x, const pair<int, int> &y){
    return mp(x.first + y.first, x.second + y.second);
}
void solve(){
    int n,m;
    cin>>n>>m;
    vector<vector<bool>> grid(n, vector<bool>(m,0));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            char type;
            cin>>type;
            grid[i][j]=(type=='#');
        }
    }
    vector<vector<bool>> southposs(n, vector<bool>(m, 1));
    for(int i=0;i<n;i++){
        bool foundgood=0, foundbad=0;
        for(int j=0;j<m;j++){
            if(grid[i][j]){
                foundgood=1;
            }
            if(foundgood && !grid[i][j]){
                foundbad=1;
            }
            if(foundgood && foundbad){
                southposs[i][j]=0;
            }
        }
    }
    for(int i=0;i<n;i++){
        bool foundgood=0, foundbad=0;
        for(int j=m-1;j>=0;--j){
            if(grid[i][j]){
                foundgood=1;
            }
            if(foundgood && !grid[i][j]){
                foundbad=1;
            }
            if(foundgood && foundbad){
                southposs[i][j]=0;
            }
        }
    }
    for(int i=0;i<m;i++){
        bool foundgood=0, foundbad=0;
        for(int j=0;j<n;j++){
            if(grid[j][i]){
                foundgood=1;
            }
            if(foundgood && !grid[j][i]){
                foundbad=1;
            }
            if(foundgood && foundbad){
                southposs[j][i]=0;
            }
        }
    }
    for(int i=0;i<m;i++){
        bool foundgood=0, foundbad=0;
        for(int j=n-1;j>=0;--j){
            if(grid[j][i]){
                foundgood=1;
            }
            if(foundgood && !grid[j][i]){
                foundbad=1;
            }
            if(foundgood && foundbad){
                southposs[j][i]=0;
            }
        }
    }
    vector<vector<int>> prefixrow(n, vector<int>(m+1, 0));
    vector<vector<int>> prefixcol(n+1, vector<int>(m, 0));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            prefixrow[i][j+1]=prefixrow[i][j]+southposs[i][j];
            prefixcol[i+1][j]=prefixcol[i][j]+southposs[i][j];
        }
    }
    for(int i=0;i<n;i++){
        if(prefixrow[i][m]==0){
            cout<<"-1\n";
            return;
        }
    }
    for(int i=0;i<m;i++){
        if(prefixcol[n][i]==0){
            cout<<"-1\n";
            return;
        }
    }
    auto valid=[&](const pair<int, int> &x){
        return x.first<n && x.first>=0 && x.second>=0 && x.second<m;
    };
    auto check=[&](const pair<int, int> a, const pair<int, int> &b){
        int x=a.first, x2=b.first, y=a.second, y2=b.second;
        if(x!=x2){
            if(x2>x){
                return ((prefixcol[n][y]-prefixcol[x][y])>0);
            }
            else{
                return (prefixcol[x][y]>0);
            }
        }
        if(y!=y2){
            if(y2>y){
                return ((prefixrow[x][m]-prefixrow[x][y])>0);
            }
            else{
                return (prefixrow[x][y]>0);
            }
        }
        return false;
    };
    vector<pair<int, int>> dir={{1,0},{-1,0},{0,1},{0,-1}};
    vector<vector<bool>> found(n, vector<bool>(m,0));
    int ans=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(grid[i][j] && !found[i][j]){
                ++ans;
                found[i][j]=1;
                queue<pair<int, int>> q;
                q.push(mp(i,j));
                while(!q.empty()){
                    for(const auto &path : dir){
                        auto next=q.front()+path;
                        if(valid(next) && grid-next && !(found-next) && check(q.front(), next)){
                            found-next=1;
                            q.push(next);
                        }
                    }
                    q.pop();
                }
            }
        }
    }
    cout<<ans<<'\n';
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

The problems were:

  • For const vector<vector<T>>& seq (and T != bool), the type of seq[x][y] is const T&, not T&, so I added an overload of operator- that handles the non-const seq case
  • vector<bool> is a much-maligned specialisation since it behaves very differently to vector<T> for T != bool: a vector v of type vector<bool> does not return a bool& from its operator[], but instead an object whose type is a proxy class which has an implicit conversion to bool.

Thus, in

template<typename T>
T& operator-(vector<vector<T>> &seq, const pair<int , int> &idx){
    return seq[idx.first][idx.second];
}

with T = bool, seq[idx.first][idx.second] returns a reference to an object of this proxy class, which must then be implicitly converted (via a temporary) to a temporary bool. C++ forbids the binding of temporaries to (non-const) references, hence your error.

Declaring the return type as decltype(auto) means “deduce the return type of the function (just as if we declared the return type as plain auto), and set it to precisely the deduced type”, which, for T = bool, will be a reference to vector<bool>'s proxy class. If we had just used plain auto, the return type would be just the proxy class (not a reference to it), and so operator- would return a copy of the proxy class object resulting from seq[idx.first][idx.second];, which wouldn’t be what we wanted (probably a compiler error).

2 Likes
5

It works correctly, Thanks. I’ll look up what decltype does.

1 Like