Changeset 4087

Timestamp:

Aug 30, 2021, 4:00:02 AM (18 months ago)

Author:

Peter

Message:

extend docs; closes #710

Location:

trunk/yat/utility

Files:

• Ranking.h (modified) (13 diffs)
• ranking/Impl.h (modified) (1 diff)

trunk/yat/utility/Ranking.h

@@ -54 +54 @@
     /// type used to compare elements
     typedef Compare key_compare;
+    /// reference
+    typedef const T& reference;
+    /// reference
+    typedef const T& const_reference;
+    /// pointer
+    typedef const T* pointer;
+    /// const pointer
+    typedef const T* const_pointer;
     /// size type
     typedef size_t size_type;
@@ -254 +262 @@
        \return An iterator pointing to the element that follows the
        last element removed.
+
+       Complexity: constant time.
      */
     iterator erase(const_iterator position);
@@ -260 +270 @@
        Erase all elements that are equivalent with \c value
        \return number of elements removed
+
+       Complexity: logarithmic in size of container.
      */
     size_type erase(const T& value);
@@ -268 +280 @@
        \return An iterator pointing to the element that follows the
        last element removed.
+
+       Complexity: Linear in number of elements erased.
      */
     iterator erase(const_iterator first, const_iterator last);
 
     /**
-       Find an element that is equivalent to x
+       Find an element that is equivalent to x.
+
+       \return end() if no such element exists
+
+       Complexity: logarithmic in size of container.
      */
     const_iterator find(const T& x) const;
@@ -279 +297 @@
     /**
        \brief insert an element
+
+       \return a n iterator pointing to just inserted element
+
+       Complexity: logarithmic in size of container.
      */
     iterator insert(const T& element)
@@ -290 +312 @@
     /**
        \brief insert an element
+
+       Same as insert(const T& element) but moves rather than copy \c
+       element.
      */
     iterator insert(T&& element)
@@ -316 +341 @@
     /**
        \brief insert with hint
+
+       Same as as insert(const_iterator, const T&) but move instead of
+       copy \c element.
      */
     iterator insert(const_iterator hint,  T&& element)
@@ -327 +355 @@
     /**
        \brief insert range
+
+       Complexity: N log S, where S is size of container and N is
+       number of inserted elements. If inserted range is sorted,
+       complexity linear, N.
      */
     template<typename InputIterator>
@@ -338 +370 @@
     /**
        \return the first element which is equal (or greater) to \c x
+
+       Complexity: logarithmic in size of container.
      */
     const_iterator lower_bound(const T& x) const
@@ -349 +383 @@
     /**
        \return the first element which is greater than \c x
+
+       Complexity: logarithmic in size of container.
      */
     const_iterator upper_bound(const T& x) const
@@ -360 +396 @@
     /**
        \return number of elements smaller than \c it
+
+       Complexity: logarithmic in size of container.
      */
     size_t ranking(const_iterator it) const
@@ -370 +408 @@
     /**
        \return number of elements in container
+
+       Complexity: constant time
      */
     size_t size(void) const
@@ -378 +418 @@
   private:
     Compare compare_;
+    // Things that are agnostic to T are implemented in impl_.
     ranking::Impl impl_;
 

trunk/yat/utility/ranking/Impl.h

@@ -39 +39 @@
   namespace ranking {
 
+    /**
+       This class is a helpwer class for Ranking that handles
+       everything that is independent of template parameter T. Copy
+       constructor and assignment are deleted because copying a tree
+       needs to be aware of T so the nodes can be copied (cloned)
+       correctly, i.e., copied as NoveValue<T> objects (not NodeBase).
+     */
     class Impl
     {