Data Structures

[powah2players]

So I'm about to start a class in college on Data Structures, I was wondering if anyone can throw in any information on the subject so I can start research in my book on what the key factors are. The book I'm using is D.S. Malik's C++ 5th Edition From Program Analysis to Program Design. On some of the readings I've done online it looks like a lot of array work, but any other information that can be given will be helpful. Thanks in advance for the advice!

[Stewbond]

Lets say that we have a student name and a student number that should be associated with the same student.

We can do this:

std::string name;
int number;

Now let's say that we have several students and we want to make an array. We'd have to make both arrays, and both the same length.

std::string name[10];
int number[10];

Now let's say we want to sort "name" alphabetically... We'll need to also sort number in the same way and ensure that number always remains in synch with the name. This is going to get tough. Instead we can ALWAYS ensure that it remains in synch by making a structure:

struct Student
{
    std::string name;
    int number;
};

Now we can use Student as a type. If we want several students, we can make an array of Student
Student students[10];

Now we know that we have 10 names, 10 numbers, and if we sort them, they will always be associated with the right object.

for (int i = 0; i < 10; ++i)
    std::cout << students[i].name << ' ' << students[i].number << std::endl;

[powah2players]

So std::cout << students[i].name << ' ' << students[i].number << std::endl; is going to organize the names of the students from 1-10 in order by name? kinda like:

1.Adam
2.Bravo
3.Charlie...

so on and so forth, or is it going to throw it in random?

[S6k9GNh0]

It would print them in whatever you order you assigned them in. Otherwise, you'd have to sort them.

[jmadsen]

Stewbond's advice was good and a very good starting point for a basic data structure. However, I would recommend using a class instead of struct. The only significant difference is that in a class all member variables and functions are private by default (meaning they can only be accessed from within the class functions), and in a struct all the member functions and variables are public by default. E.g.

struct MyStruct
{
// public:
// is implied here
    std::string name;
    int ID;
};

class MyClass
{
// private:
// is implied here
    std::string name;
    int ID;
};


int main(int argc, char** argv) 
{
     MyStruct a_struct;
     MyClass a_class;

     a_struct.name = "Student Name";  // this is valid because name is public
     a_class.name = "Student Name"; // this is invalid because name is private

     return 0;
}

The reason is suggest this is you can make public functions in the class, e.g.

class MyClass
{
public:
    void SetName(const std::string& val) { name = val; }
    const std::string& GetName() const { return name; }

private:
    std::string name;
    int ID;

};

so if the name or ID variables are changed, it has to be explicitly done by invoking the "set" function. It's a bit more verbose but it's the safe practice to do as data structures get more complex because it doesn't allow for accidental reassignments that might be very difficult to locate.

also, use the STL data containers instead of C-style arrays.

// C-style array
Student students[10];

// C++ alternative
std::vector<Student> students(10);
// The benefits of this over the C-style array is you have access to member
// functions such as size() that tells you how large the data structure is
// which is very useful when constructing loops:
// for(unsigned i = 0; i < students.size(); ++i) { ... }

Vector is just one of many C++ data containers (vector, list, deque, map, set, multimap, ... etc.)

These containers are dynamically allocating - meaning instead of being a fixed size, you can make the container larger if you exceed 10 students in the above example. i.e.

// ... assuming the vector of students has been fully 
// populated with its initial capacity of 10 students ...

// These a better way to do this by creating non-default constructor btw
Student a_student;
a_student.SetName("John Smith");
a_student.SetID(11);

// Add another student to the data container so the size of the container
// goes from 10 to 11
students.push_back(a_student);

[N36fSL3A]

Vectors are great, just remember to not use "resize" at all.

Also, they're a little bit slower than C arrays.

[cire]

Vectors are great, just remember to not use "resize" at all.

Back to the inane advice, I see.

Also, they're a little bit slower than C arrays.

If you need to use dynamic arrays in C, expect similar performance.