What is this data structure called?

Here's the data structure I have in mind: names of football (soccer) teams running across the top row and down the left col, something like:

Code:

---



            Arsenal Spurs Chelsea //edit: this line should be indented right but keeps going back left!
Arsenal
Spurs
Chelsea

---

Main diagonal == one that runs top left to bottom right
Above main diagonal - scores from matches where the team in the header row was the home team
Below main diagonal - scores from matches where the team in the left col was the home team
Obviously the main diagonal itself is empty since no team plays itself!
Also, the top row and left col would be std::string datatype but the off-diagonal elements need to be able to take other datatypes
Is there a name for such a data structure and where could I find some sample code etc to get started?
Many thanks

You can call it whatever you want. :)
I would store it as a 1D array of strings for the names. Since they're the same across the top and down the side you only have to store them once. And then a 2D array (e.g., of ints) for the interior matrix. Something like:

Code:

---

class Wins {  // or whatever an appropriate name is
private:
    vector<string> names;
    vector<vector<int>> wins;
public:
    void print() {
        // print top line
        //for each row of data
          // print corresponding name then the row of data
    }
};

---

BTW, to indent the first line in code tags, you have to put a dummy character (e.g., a period) in the first column:

Code:

---

.        Arsenal Spurs Chelsea
Arsenal    -
Spurs              -
Chelsea                  -

---

Thanks, I'll start work on this shortly and report back in a day or two

it's working!
text-file: Arsenal v Spurs 0-0 Spurs v West Ham 1-1 Arsenal v Chelsea 2-0 Chelsea v Arse - Pastebin.com
program: #include <iostream> #include <string> #include <vector> #include <deque> #in - Pastebin.com
program logic:
(a) after reading file, set up std::map<std::string, std::string> with home-team + " " + away-team as map key and score as map value
(b) set up std::vector<std::vector<std::string>> as algorism suggested and the off-diagonal elements of the vector are populated with map.find()->second
program output:

Code:

---

    .          Arsenal    Chelsea      Spurs  West Ham
  Arsenal          *        2-0        0-0        1-0
  Chelsea        3-0          *        TBD        TBD
    Spurs        1-1        2-0          *        1-1
  West Ham        TBD        0-2        0-0          *

---

algorism: thank you very much for the help

Quote:

---

Originally Posted by sean_cantab

it's working!

---

That looks really good. Great job!

I'm off to dreamland now (I actually had a dream (nightmare?) about Trump yesterday!), but I'll definitely take a look at your code tomorrow.

Looks like a matrix to me. And std::vector<std::vector<std::string>> is one possible implementation of a matrix, but not the only one. For example, this implementation might allow an invalid matrix with rows of different length. Maybe that problem doesn't occur in your program, but it's an open problem that anyone looking at your code needs to consider.

One solution might be to define a single constructor to create the matrix, and verify at run time that the matrix is valid. It's probably even possible, using C++ template meta-programming, to get the error during compile-time, rather than a run-time check, but that's another topic.

MacNilly - could you please clarify:

Quote:

---

this implementation might allow an invalid matrix with rows of different length

---

I thought the following allocation would fix the row and col of the matrix:

Code:

---

std::vector<std::vector<std::string>> myVecVec(teams.size()+1, std::vector<std::string> (teams.size()+1));

---

... but perhaps I missed something? Thanks

That's a pretty cool overall algorithm.

You're not testing for eof properly. It's best to read an entire line. And the && trick is more of a shell-scripting thing. Even so, if either of the getlines fail you still continue with the code!

And instead of using 'v' as a delimiter (which could potentially occur in a team name), you should find the string " v ".

So how about:

Code:

---

    typedef std::string::size_type sz_t;

    while (getline(inFile, line)) {
        sz_t delim = line.find(" v ");
        home = line.substr(0, delim);

        sz_t last_space = line.find_last_of(" ");
        away = line.substr(delim + 3, last_space - delim - 3);
        result = line.substr(last_space + 1);

        teams.insert(home);
        tieResults[home + " " + away] = result;
    }

---

This assumes perfect input. It wouldn't work with, e.g.:

Code:

---

Arsenal v Spurs 0-0                  // extra spaces at end
                                    // blank line
Spurs    v West Ham 1-1              // spaces before " v "
    Arsenal v Chelsea 2-0            // extra spaces at beginning
Chelsea v Arsenal    3-0            // spaces before result
Spurs v    Arsenal 1-1              // spaces after " v "
West Ham    v    Chelsea 0-2        // spaces before and after " v "
  Spurs  v    Chelsea    2-0      // spaces all over the place!

---

In general it's a real hastle to deal with messy input. :(

algorism: thanks for taking the time to review, I've incorporated your suggestions. I like particularly the use of std::string::size_type as some googling shows that this is far more preferable to using ints, etc.
There are couple of points though that are not quite clear to me:

Quote:

---

You're not testing for eof properly

---

I'd thought ...

Code:

---

if (inFile)
        {
            teams.insert(home);
            tieResults[home + " " + away] = result;
        }

---

... would take care of this?
The other thing is:

Quote:

---

if either of the getlines fail you still continue with the code!

---

I'd also thought based on the discussion below, particularly #7 ...
https://cboard.cprogramming.com/cplu...ta-fields.html
... that if both getlines are not true evaluation would not continue? Thanks again

You mention size_type, which is the least important change.
The most important is testing for " v " instead of just 'v'.
Secondly, testing for eof properly.

Code:

---

    while(inFile)
    {
        // Obviously if either or both of these fail ...
        getline(inFile, home, 'v') && getline(inFile, remainder);
        // ... control still move on to the next part.
        // So your code executes the next part one more
        // time than it should.

        remainder.erase(0,1);//remove leading space
        std::size_t found = remainder.find_last_of(" ");
        away = remainder.substr(0, found);
        result = remainder.substr(found+1);
        home.pop_back();//remove trailing space

        // The following will help somewhat, but it's really too late.
        // Why bother executing the above code with garbage data?
        // So you could put this above the remainder.erase() call.
        // But it's still an amateurish way to do it.
        if(inFile)
        {
            teams.insert(home);
            tieResults[home + " " + away] = result;
        }
    }

---

In general, the proper way to test for eof is to test the statement that reads from the file for failure, as I did in my correction to your code.

You are misinterpreting laserlight's code in post 4 of your link. Note that laserlight firstly uses getline to read an entire line from the input and tests the input state at the same time (as I did). Then laserlight uses the && trick to parse the line from a stringstream. That's totally different.

algorism - its very clear now, thank a lot!

Quote:

---

Originally Posted by sean_cantab

its very clear now

---

Excellent.

I should also mention that you don't need the deque and vector in order to display the table. You can display it directly from the set and map.

Code:

---

#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>
#include <set>
#include <map>

int main() {
    using std::cout;
    typedef std::string::size_type sz_t;

    std::ifstream inFile("teams.txt");
    std::string line, home, away, result;
    std::set<std::string> teams;
    std::map<std::string,std::string> results;

    while (getline(inFile, line)) {
        sz_t delim = line.find(" v ");
        home = line.substr(0, delim);

        sz_t last_space = line.find_last_of(" ");
        away = line.substr(delim + 3, last_space - delim - 3);
        result = line.substr(last_space + 1);

        teams.insert(home);
        results[home + ':' + away] = result;
    }

    cout << std::setw(10) << ' ';
    for (auto const& e: teams) cout << std::setw(10) << std::left << e;
    cout << '\n';

    for (auto const& home: teams) {
        cout << std::setw(10) << std::left << home;
        for (auto const& away: teams) {
            cout << std::setw(10) << std::left;
            if (home == away)
                cout << '*';
            else
                cout << results[home + ':' + away];
        }
        cout << '\n';
    }

    return 0;
}

---

algorism : this is super efficient indeed, I was using needlessly two additional containers just to format printing! thanks for your generosity, I've learnt so much from the discussion