which is more effecient?

This is a discussion on which is more effecient? within the C++ Programming forums, part of the General Programming Boards category; Code: //a linked list? struct SETTINGS { string name; string value; SETTINGS *next; } //or struct SETTINGS { vector<string> name; ...

  1. #1
    i want wookie cookies the Wookie's Avatar
    Join Date
    Oct 2002
    Posts
    455

    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

  2. #2
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    The 2nd one would require much less coding on your part.
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  3. #3
    i want wookie cookies the Wookie's Avatar
    Join Date
    Oct 2002
    Posts
    455
    true, but the program is mainly for practice so i don't mind. is the first one more effecient?

  4. #4
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    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.
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  5. #5
    Magically delicious LuckY's Avatar
    Join Date
    Oct 2001
    Posts
    856
    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

  6. #6
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    Can you show us what code you used for the tests?
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  7. #7
    i want wookie cookies the Wookie's Avatar
    Join Date
    Oct 2002
    Posts
    455
    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

  8. #8
    ˇAmo fútbol!
    Join Date
    Dec 2001
    Posts
    2,136
    Why not

    struct SETTINGS
    { string name;
    string value;
    }

    and then declare

    vector <SETTINGS> AllSettings;

  9. #9
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    Because the vector class requires that the datatype have a defined assignment operator, which is not provided with structs.
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  10. #10
    i want wookie cookies the Wookie's Avatar
    Join Date
    Oct 2002
    Posts
    455
    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

  11. #11
    Magically delicious LuckY's Avatar
    Join Date
    Oct 2001
    Posts
    856
    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
    Last edited by LuckY; 04-28-2003 at 11:03 PM.

  12. #12
    Registered User
    Join Date
    Apr 2002
    Posts
    1,571
    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.

  13. #13
    Disturbed Boy gustavosserra's Avatar
    Join Date
    Apr 2003
    Posts
    244

    Question ???

    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!
    Nothing more to tell about me...
    Happy day =)

  14. #14
    Open to suggestions Brighteyes's Avatar
    Join Date
    Mar 2003
    Posts
    204
    >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...
    p.s. What the alphabet would look like without q and r.

  15. #15
    i want wookie cookies the Wookie's Avatar
    Join Date
    Oct 2002
    Posts
    455
    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

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Effecient Code
    By computerquip in forum C++ Programming
    Replies: 8
    Last Post: 11-11-2008, 09:57 PM
  2. Effecient Selection Statements?
    By 031003b in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2007, 07:08 AM
  3. Help making Program Better/More Effecient
    By toonlover in forum C++ Programming
    Replies: 14
    Last Post: 04-30-2006, 12:40 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21