Thread: What is this data structure called?

  1. #1
    Registered User
    Join Date
    Mar 2016
    Posts
    199

    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
    Last edited by sean_cantab; 02-12-2017 at 08:03 AM.

  2. #2
    Registered User
    Join Date
    Jun 2015
    Posts
    1,643
    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                   -

  3. #3
    Registered User
    Join Date
    Mar 2016
    Posts
    199
    Thanks, I'll start work on this shortly and report back in a day or two

  4. #4
    Registered User
    Join Date
    Mar 2016
    Posts
    199
    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

  5. #5
    Registered User
    Join Date
    Jun 2015
    Posts
    1,643
    Quote Originally Posted by sean_cantab View Post
    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.

  6. #6
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Location
    CA, USA
    Posts
    466
    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.
    Last edited by MacNilly; 02-15-2017 at 02:12 AM.

  7. #7
    Registered User
    Join Date
    Mar 2016
    Posts
    199
    MacNilly - could you please clarify:
    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

  8. #8
    Registered User
    Join Date
    Jun 2015
    Posts
    1,643
    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.

  9. #9
    Registered User
    Join Date
    Mar 2016
    Posts
    199
    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:
    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:
    if either of the getlines fail you still continue with the code!
    I'd also thought based on the discussion below, particularly #7 ...
    Reading .txt files with whitespaces within data-fields
    ... that if both getlines are not true evaluation would not continue? Thanks again

  10. #10
    Registered User
    Join Date
    Jun 2015
    Posts
    1,643
    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.

  11. #11
    Registered User
    Join Date
    Mar 2016
    Posts
    199
    algorism - its very clear now, thank a lot!

  12. #12
    Registered User
    Join Date
    Jun 2015
    Posts
    1,643
    Quote Originally Posted by sean_cantab View Post
    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;
    }

  13. #13
    Registered User
    Join Date
    Mar 2016
    Posts
    199
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 1
    Last Post: 05-07-2012, 11:39 PM
  2. Replies: 6
    Last Post: 12-01-2011, 01:02 PM
  3. difference between data object and data structure?
    By c_lady in forum C++ Programming
    Replies: 2
    Last Post: 02-22-2011, 12:30 PM
  4. Data structure for storing serial port data in firmware
    By james457 in forum C Programming
    Replies: 4
    Last Post: 06-15-2009, 09:28 AM
  5. data structure design for data aggregation
    By George2 in forum C# Programming
    Replies: 0
    Last Post: 05-20-2008, 06:43 AM

Tags for this Thread