Have you ever been annoyed with list::size recounting all elements of a list each times size () is called ? SizedList class contains a member size_ and updates it for insert and erase (just one element at the moment) Looks to improve list::size speed. It needs to upgrade other methods, but what about this basic SizedList ? Feel free to complete that class
SizedList.hpp
#pragma once
#include <list>
#include <iostream>
#include <algorithm>
template <typename T>
class SizedList : public std::list<T> {
public :
SizedList (const T* i, const T* j) : std::list<T> (i, j), size_ ((size_t) (j -i)) {
}
SizedList (const SizedList& l) : std::list<T> (l), size_ (l.size_) {
}
SizedList (const std::list<T>& l) : std::list<T> (l), size_ (l.size ()) {
}
SizedList& operator = (const SizedList& l) {
std::list<T>::operator = (l);
size_ = l.size_;
return *this;
}
SizedList () : std::list<T> (), size_ ((size_t) (0)) {}
size_t size () const {return size_;}
typename std::list<T>::iterator erase (typename std::list<T>::iterator i) {
typename std::list<T>::iterator j (std::list<T>::erase (i));
--size_;
return j;
}
typename std::list<T>::iterator insert (typename std::list<T>::iterator i, const T& t) {
typename std::list<T>::iterator j (std::list<T>::insert (i, t));
++size_;
return j;
}
bool operator == (const SizedList& l) const {
if (size_ != l.size_) return false;
typename std::list<T>::const_iterator i (std::list<T>::begin ());
std::find_if (l.begin (), l.end (), [&i] (const T& t) {
if (t != *i) return true;
++i;
return false;
});
if (i != std::list<T>::end ()) return false;
return true;
}
bool operator != (const SizedList& l) const {
return !operator == (l);
}
private :
size_t size_;
};
Test program :
int main (int argc, char*argv []) {
std::list<size_t> l5 (1000000, 0);
//buiding list l5 : [0...1000000[
{
size_t s_ (0);
std::for_each (l5.begin (), l5.end (), [&s_] (size_t& s) {s = s_; ++s_;});
}
SizedList<size_t> l6 (l5);
//insert a foo element
{
std::list<size_t>::iterator i5 (l5.begin ());
std::advance (i5, 500000);
l5.insert (i5, 12);
}
{
std::list<size_t>::iterator i6 (l6.begin ());
std::advance (i6, 500000);
l6.insert (i6, 12);
}
if (l6 == (SizedList<size_t>)l5) std::cout << "insertion was ok" << std::endl;
else std::cout << "insertion was nok" << std::endl;
//chronometered size () on normal list
{
size_t s (0);
clock_t t0 (clock ()), t1 (t0);
s = l5.size ();
t1 = clock ();
std::cout << "l5 list size after insert insert == " << s << " and number of ticks elapsed :" << (size_t) (t1 - t0) << std::endl;
}
//chronometered size on sized list
{
size_t s (0);
clock_t t0 (clock ()), t1 (t0);
s = l6.size ();
t1 = clock ();
std::cout << "l6 list size after insert insert == " << s << " and number of ticks elapsed :" << (size_t) (t1 - t0) << std::endl;
}
}
and results :
insertion was ok
l5 list size after insert insert == 1000001 and number of ticks elapsed :10509
l6 list size after insert insert == 1000001 and number of ticks elapsed :0
Aucun commentaire:
Enregistrer un commentaire