The iterator interface is common to all STL containers, including lists. In the example below we see that a list is a “linear” data structure that behaves similarly to a vector, in a sense that supports almost the same operations.
#include <iostream>
#include <list>
int main(){
std::list<int> mylist{ 1,2,3,4,5 };
mylist.push_back(6);
std::list<int>::iterator itr = mylist.begin();
for (itr = mylist.begin(); itr != mylist.end(); ++itr)
std::cout << *itr << ",";
std::cout << std::endl;
}
The first difference between a vector and a list is the ability to add to the front of a list.
int main() {
std::list<int> mylist{ 1,2,3,4,5 };
mylist.push_front(6);
for (auto x:mylist)
std::cout << x<< ",";
std::cout << std::endl;
}
One can argue that we can do the same by using the vector::insert at the beginning. Let us compare the performance of the two.
using namespace std::chrono;
int main() {
std::random_device e;
std::uniform_int_distribution<> dist(1, 10);
std::vector<int> myvec;
auto startv = system_clock::now();
for(int i=0;i<1000000;i++)
myvec.insert(myvec.begin(), dist(e));
auto elapsed = duration_cast<seconds>(system_clock::now() - startv);
std::cout << elapsed.count() << std::endl;
std::list<int> mylist;
auto startl = system_clock::now();
for (int i = 0; i < 100000; i++)
mylist.push_front(dist(e));
elapsed = duration_cast<seconds>(system_clock::now() - startl);
std::cout << elapsed.count() << std::endl;
}
On my computer the operations on a vector takes more than a minute whereas on a list less than a second. As explained in class this is because every time we insert at the beginning of the vector we need to move all existing elements to the right which is an O(n) operation instead of constant for a list.
On the other hand, random access is very costly in the case of a list. Notice that std::list does not have an indexing operator like in the case of a vector. We can simulate that using the STL function std::advance
using namespace std::chrono;
int main(){
std::random_device e;
std::uniform_int_distribution<> dist(1, 10);
const int n=1000000;
const int ops=1000;
std::vector<int> myvec(n);
std::list<int> mylist(n);
std::generate(myvec.begin(), myvec.end(), [&]() { return dist(e); });
std::generate(mylist.begin(), mylist.end(), [&]() { return dist(e); });
auto startv = system_clock::now();
for (int i = 0; i < ops; i++)
std::advance(myvec.begin(), n/2);
auto elapsed = duration_cast<seconds>(system_clock::now() - startv);
std::cout << elapsed.count() << std::endl;
auto startl = system_clock::now();
for (int i = 0; i < ops; i++)
std::advance(mylist.begin(), n/2);
elapsed = duration_cast<seconds>(system_clock::now() - startl);
std::cout << elapsed.count()<<std::endl;
}
On my computer the operations for the list take about a minute whereas for a vector less than a second. Again, as explained in class random access for a list is an O(n) operation.
These are the main differences between a vector and a list. Other than that they can be treated in the same using STL algorithms.
For example, filtering both a vector and a list should in principle take the roughly the same amount of time since both are scanned in a linear fashion. We have seen the example below when discussing std::vector. The example below explores that idea. As you can see the vector performance is much better. This is due to difference in allocation strategies between vector and list. When a vector is full its capacity is increased exponentially whereas in the case of a list only a single node is added every time.
using namespace std::chrono;
const int n = 1000000;
std::random_device e;
std::uniform_int_distribution<> dist(1, 10);
std::vector<int> v;
std::list<int> l;
v.resize(n);
l.resize(n)
std::generate(v.begin(), v.end(), [&]() {return dist(e); });
std::vector<int> ov;
std::list<int> ol;
auto startv = system_clock::now();
std::copy_if(v.begin(), v.end(), std::back_insert_iterator(ov),
[](int i) { return i % 2 ==0; });
auto elapsed = duration_cast<seconds>(system_clock::now() - startv);
auto startl = system_clock::now();
std::copy_if(l.begin(), l.end(), std::back_insert_iterator(ol),
[](int i) { return i % 2 ==0; });
elapsed = duration_cast<seconds>(system_clock::now() - startl);
}
Even when the operations on both lists an vectors is asymptotically the same it is almost always better to use a vector unless we need to insert/delete at the beginning (or arbitrary position) of the data.