YODA/Utils/sortedvector.h

0001 // -*- C++ -*-
0002 //
0003 // This file is part of YODA -- Yet more Objects for Data Analysis
0004 // Copyright (C) 2008-2024 The YODA collaboration (see AUTHORS for details)
0005 //
0006 #ifndef YODA_SORTEDVECTOR_H
0007 #define YODA_SORTEDVECTOR_H
0008
0009 #include <vector>
0010 #include <algorithm>
0011 #include <stdexcept>
0012 #include <iostream>
0013
0014 namespace YODA {
0015   namespace Utils {
0016
0017
0018     /// @brief Specialisation of std::vector to allow indexed access to ordered elements
0019     ///
0020     /// @warning This still scales as n^2 log n or so, if inserting n
0021     /// elements. Prefer to populate a whole std::vector first, then add, so the
0022     /// sorting/searching only needs to be done once.
0023     ///
0024     /// @todo Need to template on the value-comparison definition?
0025     /// @todo Generalise the type of source container for constructor argument
0026     template <typename T>
0027     class sortedvector : public std::vector<T> {
0028     public:
0029
0030       /// Default constructor
0031       sortedvector() {}
0032
0033       /// Conversion from std::vector
0034       sortedvector(const std::vector<T> & vec)
0035         : std::vector<T>(vec) {
0036         std::sort(this->begin(), this->end());
0037       }
0038
0039       /// Insertion operator (push_back should not be used!)
0040       void insert(const T& val) {
0041         // Dumb way:
0042         //   std::vector<T>::push_back(val);
0043         //   std::sort(this->begin(), this->end());
0044         //
0045         // A bit better:
0046         std::vector<T>::insert(std::upper_bound(std::vector<T>::begin(), std::vector<T>::end(), val), val);
0047       }
0048
0049
0050     private:
0051
0052       /// Hiding push_back from the base class
0053       void push_back();
0054
0055     };
0056
0057
0058   }
0059 }
0060
0061 #endif