mercredi 8 août 2018

What about a std::list updating its size?

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