Changeset 1481 for trunk


Ignore:
Timestamp:
Jun 3, 2012, 1:29:54 PM (8 years ago)
Author:
Peter Johansson
Message:

avoid logN lookup and insertion

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/lib/Vector.h

    r1418 r1481  
    55
    66/*
    7   Copyright (C) 2010 Peter Johansson
     7  Copyright (C) 2010, 2012 Peter Johansson
    88
    99  This file is part of svndigest, http://dev.thep.lu.se/svndigest
     
    148148    Vector& operator+=(const Vector& other)
    149149    {
    150       Vector result;
    151       typename Map::iterator first1 = map_.begin();
    152       typename Map::iterator last1 = map_.end();
     150      // make a copy (of map_) whose iterators are not invalidated
     151      // when we insert values into map_.
     152      Map old;
     153      // Efficient way (constant time) to copy map_ into old and clear map_
     154      std::swap(old, map_);
     155      const_iterator first1 = old.begin();
     156      const_iterator last1 = old.end();
    153157      const_iterator first2 = other.begin();
    154158      const_iterator last2 = other.end();
    155159      while (first1!=last1 || first2!=last2) {
    156160        svn_revnum_t rev = 0;
     161        T value = 0;
    157162        if (first1==last1) {
    158163          rev = first2->first;
     164          value = policy_.get(old, first1) + first2->second;
    159165          ++first2;
    160166        }
    161         else if (first2==last2) {
     167        else if (first2==last2 || first1->first < first2->first) {
    162168          rev = first1->first;
    163           ++first1;
    164         }
    165         else if (first1->first < first2->first) {
    166           rev = first1->first;
     169          value = first1->second + other.policy_.get(other.map_, first2);
    167170          ++first1;
    168171        }
    169172        else if (first1->first == first2->first) {
    170173          rev = first1->first;
     174          value = first1->second + first2->second;
    171175          ++first1;
    172176          ++first2;
     
    174178        else if (first1->first > first2->first) {
    175179          rev = first2->first;
     180          value = policy_.get(old, first1) + first2->second;
    176181          ++first2;
    177182        }
    178         result.set(rev, (*this)[rev] + other[rev]);
     183        map_.insert(map_.end(), std::make_pair(rev, value));
    179184      }
    180       // assign result map to this
    181       std::swap(map_, result.map_);
    182       resize(std::max(size_, other.size()));
     185      size_ = std::max(size_, other.size());
    183186      return *this;
    184187    }
Note: See TracChangeset for help on using the changeset viewer.