which is more effecient?

Code:

---

//a linked list?
struct SETTINGS {
    string name;
    string value;
    SETTINGS *next;
}

//or
struct SETTINGS {
    vector<string> name;
    vector<string> value;
}

---

one will be in a node where there are multiple settings for the node. i think i like the linked list more, but i'm not sure

The 2nd one would require much less coding on your part.

true, but the program is mainly for practice so i don't mind. is the first one more effecient?

It would depend on how well you coded the functions for the linked list. I'm willing to bet that some well-coded functions would out-perform the STL, mainly because of less overhead.

I just did a quick and dirty test. Here are my results:

10,000 items:

Linked List:
Inserted 10000 items in 0.09 secs
Deleted 10000 items in 0.026 secs

Vector:
Inserted 10000 items in 0.101 secs
Deleted 10000 items in 0.008 secs


100,000 items:

Linked List:
Inserted 100000 items in 1.58 secs
Deleted 100000 items in 0.111 secs

Vector:
Inserted 100000 items in 0.9 secs
Deleted 100000 items in 0.106 secs

Can you show us what code you used for the tests?

well heres my insert node code

Code:

---

void cAIBrain::AddNode() {
        //create a new node
        BLOCK *node =  new BLOCK;
        BLOCK *curr;
                node->next = NULL;
                node->say = say;
                node->resp = resp;
                numblocks++;
                node->index = numblocks;
                node->nopunc = nopunc;

        say.clear(); resp.clear();
        nopunc=false;

        //attach it to the first available spot
        if(first==NULL){
                first=node;
        } else {
                curr=first;
                if(curr->next==NULL){
                        curr->next=node;
                } else {
                        while(curr->next!=NULL){
                                curr=curr->next;
                        }
                        curr->next=node;
                }
        }
}

---

i'm not sure if its the most effecient thing, but again, im learning :)

Why not

struct SETTINGS
{ string name;
string value;
}

and then declare

vector <SETTINGS> AllSettings;

Because the vector class requires that the datatype have a defined assignment operator, which is not provided with structs.

Quote:

---

Originally posted by XSquared
Because the vector class requires that the datatype have a defined assignment operator, which is not provided with structs.

---

yeah and that won't work because each node has it's own settings structure only if there are settings for that node...otherwise it's null

Quote:

---

Originally posted by XSquared
Can you show us what code you used for the tests?

---

I coded it and posted the message literally seconds before shutting down my computer at work and heading out. It was quite short and simple though. I just retyped it pretty much how I did it earlier.

Code:

---

#include <iostream>
#include <vector>
#include <ctime>
using namespace std;

struct SETTINGS {
  string name;
  string value;
  SETTINGS *next;
};

struct VSETTINGS {
  vector<string> name;
  vector<string> value;
};

int main() {

  SETTINGS *head = new SETTINGS;
  SETTINGS *ptr = head;

  int items = 1000000;

  clock_t start = clock();

  for (int i = 0; i < items; ++i) {
    ptr->next = new SETTINGS;
    ptr = ptr->next;
    ptr->next = NULL;
    ptr->name = "ABCDEFG";
    ptr->value = "HIJKLMNOP";
  }

  cout << "Linked list:\n";
  cout << "Inserting " << items << " took " << double((clock() - start) / CLOCKS_PER_SEC) << " secs\n";

  start = clock();

  while (head != NULL) {
    ptr = head->next;
    delete head;
    head = ptr;
  }

  cout << "Deleting " << items << " took " << double((clock() - start) / CLOCKS_PER_SEC) << " secs\n";

  start = clock();

  VSETTINGS vset;

  for (int i = 0; i < items; ++i) {
    vset.name.push_back("ABCDEFG");
    vset.value.push_back("HIJKLMNOP");
  }

  cout << "\nVector:\n";
  cout << "Inserting " << items << " took " << double((clock() - start) / CLOCKS_PER_SEC) << " secs\n";

  start = clock();

  for (int i = 0; i < items; ++i) {
    vset.name.pop_back();
    vset.value.pop_back();
  }

  cout << "Deleting " << items << " took " << double((clock() - start) / CLOCKS_PER_SEC) << " secs\n";

  return 0;
}

---

Linked list:
Inserting 1000000 took 1.828 secs
Deleting 1000000 took 0.297 secs

Vector:
Inserting 1000000 took 1.828 secs
Deleting 1000000 took 0.235secs

The results vary a lot from those earlier because I'm on a much faster box now (and I used 1,000,000 iterations each this time through). I tried a billion but it took a while ; P

Well for one Visual Studio's STL implementation uses exception handling which can cripple performance. STL-Port is pretty fast though you might want to look at it. I'm not even sure which compiler you are using.

1)I didn´t know that STL had more than one implementations? Doesn´t this reduce the portability of the code?

2)And about what said XSquared... how so assignment operator? How can I use the vector class without defining any =? Does the compiler generates a default?

3)And if was a pointer to a struct(instead of a struct)

4)What vector stores? Pointers to the desired data? References?

Sorry for the many questions!

>which is more effecient?
It depends on what kind of operations will be most common. A vector offers constant time access to every element, but a linked list at best has linear time. For insertions at the end, a vector is good and so is a list, but when you have to insert anywhere else the list is much better. And so on...

im using visual studio.net. it'll mostly just be searching, like there will be a function where the user just types int he name of the setting and the node and it will return the value. there will only be a one time insertion at the beginning of the program when it reads into the file. i chose loading everything into a linked list/memory first isntead of constantly having to access the file


>3)And if was a pointer to a struct(instead of a struct)
that would be a linked list, each struct contains a pointer to the next struct, kind of like a daisy chain


>4)What vector stores? Pointers to the desired data? References?
stores a 'string' object, instead of a char*, its a string

It sounds like a vector would be faster since you can keep it sorted and use a binary search for finding things.

Lucky, the vector code could probably be made faster if this:

Code:

---

VSETTINGS vset;

for (int i = 0; i < items; ++i) {
    vset.name.push_back("ABCDEFG");
    vset.value.push_back("HIJKLMNOP");
}

---

Was changed to this:

Code:

---

VSETTINGS vset;

vset.name.reserve(items);  // Reserve space in one fell swoop
vset.value.reserve(items);  // Reserve space in one fell swoop

for (int i = 0; i < items; ++i)
{
    vset.name[i] = "ABCDEFG";
    vset.value[i] = "HIJKLMNOP";
}

---

This could change your timings, although I don't know by how much. Reserving that space initially would mean no reallocations of the vector memory. I haven't tested it but it seems like it should be faster. As has been said already, it all depends on how well you write your code.

Quote:

---

Originally posted by hk_mp5kpdw
Lucky, the vector code could probably be made faster...
This could change your timings...

---

Thanks for pointing that out, however, that would negate the purpose of the application. As you said it could change the timings which is why it would throw it off. The purpose of the code was to compare the time it would take to insert x number of items and to delete them. The way I figure it, a given user won't normally know the number of items to be inserted into a vector/list.

A few more points. Reserve grabs the space, but does not call any ctor's thus you still need to use push_back(). You could use resize() and []. structs can have =, ctor's, copy ctor's, and dtors just like classes, and if they are not provided, default ones are generated, just like classes. If all the members of a struct have working ctor's,=,etc.. then the default ones will work fine, just like classes. The only difference between a struct and a class is that a struct is born with no class and let's just anyone play with it's privates.

Quote:

---

Originally posted by grib
The only difference between a struct and a class is that a struct is born with no class and let's just anyone play with it's privates.

---

Hahahaha... Nice.

As molestingly as grib put it, it's true that the only difference between a struct and class (depending on the compiler) is the default member type.

"play with it's privates" hehehe

so structs can have functions? or did i completely misunderstand that? lol

Quote:

---

Originally posted by XSquared
Because the vector class requires that the datatype have a defined assignment operator, which is not provided with structs.

---

That would take about two seconds to make.

Quote:

---

Originally posted by the Wookie
so structs can have functions? or did i completely misunderstand that? lol

---

Yep, structs can have functions (in C++ at least). In C, it is a different story.

Quote:

---

Originally posted by golfinguy4
Yep, structs can have functions (in C++ at least). In C, it is a different story.

---

oh ok i gotcha, but no constructor/destructor right?

structs are classes with a default access of public, that is the only difference.

Quote:

---

Originally posted by the Wookie
so structs can have functions? or did i completely misunderstand that? lol

---

Quote:

---

Originally posted by me
the only difference between a struct and class (depending on the compiler) is the default member type.

---

Originally, structs were basically just groups of data combined with a common name. Eventually, compiler designers figured they were just so similar to classes that they are now handled identically, with the exception that the default member type of a struct is public and that of a class is private. Aside from that, everything you can do with a class you can also do with a struct.