How do I access objects in a linked-list in C++

Question

I'm very use to working with arrays and vectors, but now I'm playing with some STD::lists, as well as a custom list class I made.

Let's say I have a simple class, Stock.

//stock.h
class Stock{
public:
    Stock(); //default constructor
    Stock(string, double); //overloaded constructor
    void setSymbol(string); //sets stock symbol
    void setPrice(double);
    string getSymbol();
    double getPrice();        
private:
    string symbol;
    double price;
};

Now in a separate file I have my int main to test.

#include "stock.h"
#include <list>

int main(){
    list<Stock> portfolio;

    Stock Google("GOOG", 500);
    Stock Apple("APPL", 300);
    Stock Chipotle("CMG", 200);

    portfolio.push_back(Google);
    portfolio.push_back(Apple);
    portfolio.push_back(Chipotle);
}

Now if this was a vector or array, I would have no problem, I'm just completely loss on the linked-list equivalent of the following:

for(int i=0; i <portfolio.size(); i++){
    portfolio[i].getSymbol();
    portfolio[i].getPrice();
 }

Or something along those lines...I have no lecture/training in Linked-Lists so I'm really trying to do my best in teaching myself--but I'm stuck on basic manipulation. I'm using STL::list right now, but really trying to make my own class as well.

You should really be using your list class's iterator. Unfortunately I'm too lazy to tell you how right now, but look it up! — jtbandes
– jtbandes, Commented Jul 3, 2011 at 7:00

Loki Astari · Accepted Answer · 2011-07-03 15:46:34Z

6

for(int i= portfolio.begin(); i <portfolio.size(); i++)

If this worked for a std::vector, it was only by sheer accident. I have no idea how that might have worked for a vector.

std::any_stl_container::begin() returns an object called an "iterator". Specifically, an object of type std::any_stl_container::iterator. An iterator is kind of like a generalized pointer: it refers to an element in an STL container.

The iterator returned by begin is the iterator that references the first element in the list. You can move iterators around like pointers. For example:

std::list<Stock> portfolio;
...
std::list<Stock>::iterator currElem = portfolio.begin();
++currElem; //Now points to the second element in the list.
Stock &secondStock = *currElem;

In order to iterate over all of the elements in a list, you need two iterators: the first one, and the iterator for the element after the last element in the list. Fortunately, this is returned by the std::any_stl_container::end() function. So, your loop should look like:

typedef std::list<Stock>::iterator StockIt;
for(StockIt i = portfolio.begin(); i != portfolio.end(); ++i) /* Prefer pre-increment with iterators */
{
    i->getSymbol();
    i->getPrice();
}

This will work for any of the usual STL containers.

edited Jul 3, 2011 at 15:46

Loki Astari

267k87 gold badges344 silver badges575 bronze badges

answered Jul 3, 2011 at 7:05

Nicol Bolas

481k66 gold badges861 silver badges1.1k bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

6502 Over a year ago

The original code of course wouldn't compile... I corrected that typo (s/he was clearly using 0 as start instead of portfolio.begin()) and also pushback into push_back.

Staypuft Over a year ago

@Nicol-Bolas Thanks. It seems like I'm having a tough time thinking in pointers/iterators instead of accessing an element directly. I just threw together my std::vector off the top of my head, it's likely that code was not working.

iammilind · Accepted Answer · 2011-07-03 07:10:25Z

2

You have iterators as begin() and end() for std::list also:

for (list<stock>::iterator it = portfolio.begin() ; it != portfolio.end(); it++)
{
  // use 'it' to access the current element (i.e. *it)
}

edited Jul 3, 2011 at 7:10

answered Jul 3, 2011 at 7:04

iammilind

70.5k39 gold badges188 silver badges364 bronze badges

Comments

Frigo · Accepted Answer · 2011-07-03 07:09:52Z

1

You have to use iterators. Every STL container has them, even vector. They behave similarly to pointers; they can be dereferenced with * or ->, they can be incremented, they can be compared.

for( list<Stock>::iterator it = portfolio.begin(); it != portfolio.end(); it++ ){
    it->getSymbol();
    it->getPrice();
}

answered Jul 3, 2011 at 7:09

Frigo

1,7311 gold badge15 silver badges33 bronze badges

Comments

Benoit · Accepted Answer · 2011-07-03 07:11:12Z

An object of type std::list is very inefficient if you try to compute its length, because such an operation would have linear time.

Therefore with lists, you cannot compare iterators with the < and > operators. It is also ill-advised to try to get the nth element with the operator [].

Also, you should not mix begin() and size() which are respectively an iterator and an integer.

The proper way to iterate over an std::list is to use the pair of iterators begin() and end() and to increment your iterator until it reaches the end().

So, two ways:

for(std::list<stock>::const_iterator i = my_list.cbegin(); i != my_list.cend(); ++i)
{
    // access a “const stock &” object via *i
}

or

for(std.:list<stock>::iterator i = my_list.begin(); i != my_list.end(); ++i)
{
    // access a “stock &” object via *i
}

Collectives™ on Stack Overflow

How do I access objects in a linked-list in C++

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related