StanfordCPPLib
vector.h
1 /*
2  * File: vector.h
3  * --------------
4  * This file exports the <code>Vector</code> class, which provides an
5  * efficient, safe, convenient replacement for the array type in C++.
6  *
7  * @version 2019/04/09
8  * - renamed private members with underscore naming scheme for consistency
9  * @version 2019/02/04
10  * - changed internal implementation to wrap std collections
11  * @version 2018/09/06
12  * - refreshed doc comments for new documentation generation
13  * @version 2018/01/07
14  * - added front, back, removeFront, removeBack, pop_front, pop_back, push_front
15  * @version 2017/11/15
16  * - added contains, indexOf, lastIndexOf, removeValue, reverse, shuffle, sort
17  * @version 2017/10/18
18  * - fix compiler warnings
19  * @version 2016/12/09
20  * - added iterator version checking support
21  * @version 2016/09/24
22  * - refactored to use collections.h utility functions
23  * @version 2016/08/12
24  * - bug fix for constructor based on initializer list
25  * @version 2016/08/10
26  * - added support for std initializer_list usage, such as {1, 2, 3}
27  * in constructor, addAll, +, +=
28  * @version 2016/08/04
29  * - fixed operator >> to not throw errors
30  * @version 2015/10/13
31  * - nulled out pointer fields in destructor after deletion to avoid double-free
32  * @version 2015/07/05
33  * - using global hashing functions rather than global variables
34  * @version 2014/11/13
35  * - added comparison operators <, >=, etc.
36  * - added template hashCode function
37  * @version 2014/10/19
38  * - added subList method
39  * @version 2014/10/10
40  * - removed usage of __foreach macro
41  * 2014/07/09
42  * - changed checkVectorIndex range checking function into a private member
43  * function to avoid unused-function errors on some newer compilers
44  * 2014/04/27
45  * - fixed bug in addAll method that was not returning reference properly.
46  */
47 
48 #include "private/init.h" // ensure that Stanford C++ lib is initialized
49 
50 #ifndef INTERNAL_INCLUDE
51 #include "private/initstudent.h" // insert necessary included code by student
52 #endif // INTERNAL_INCLUDE
53 
54 #ifndef _vector_h
55 #define _vector_h
56 
57 #include <algorithm>
58 #include <initializer_list>
59 #include <iostream>
60 #include <iterator>
61 #include <sstream>
62 #include <string>
63 #include <vector>
64 #include <deque>
65 #include <type_traits>
66 #include <functional>
67 
68 #define INTERNAL_INCLUDE 1
69 #include "collections.h"
70 #define INTERNAL_INCLUDE 1
71 #include "error.h"
72 #define INTERNAL_INCLUDE 1
73 #include "hashcode.h"
74 #define INTERNAL_INCLUDE 1
75 #include "random.h"
76 #undef INTERNAL_INCLUDE
77 
85 template <typename ValueType>
86 class Vector {
87 public:
92  Vector() = default;
93 
101  explicit Vector(int n, ValueType value = ValueType());
102 
107  Vector(std::initializer_list<ValueType> list);
108 
113  virtual ~Vector() = default;
114 
119  void add(const ValueType& value);
120 
128 
134  ValueType& back();
135 
141  const ValueType& back() const;
142 
147  void clear();
148 
154  bool contains(const ValueType& value) const;
155 
161  void ensureCapacity(int cap);
162 
170  bool equals(const Vector<ValueType>& v) const;
171 
177  ValueType& front();
178 
184  const ValueType& front() const;
185 
192  const ValueType& get(int index) const;
193 
200  int indexOf(const ValueType& value) const;
201 
209  void insert(int index, const ValueType& value);
210 
215  bool isEmpty() const;
216 
223  int lastIndexOf(const ValueType& value) const;
224 
230  void mapAll(std::function<void (const ValueType&)> fn) const;
231 
238  ValueType pop_front();
239 
246  ValueType pop_back();
247 
254  void push_back(const ValueType& value);
255 
262  void push_front(const ValueType& value);
263 
270  void remove(int index);
271 
277  ValueType removeFront();
278 
284  ValueType removeBack();
285 
293  void removeValue(const ValueType& value);
294 
300  void reverse();
301 
309  void set(int index, const ValueType& value);
310 
315  int size() const;
316 
321  void shuffle();
322 
329  void sort();
330 
338  Vector<ValueType> subList(int start, int length) const;
339 
347  Vector<ValueType> subList(int start) const;
348 
354  string toString() const;
355 
363  ValueType& operator [](int index);
364 
372  const ValueType& operator [](int index) const;
373 
378  Vector operator +(const Vector& v2) const;
379 
384  Vector operator +(const ValueType& elem) const;
385 
390  Vector& operator +=(const Vector& v2);
391 
396  Vector& operator +=(const ValueType& value);
397 
398 
404  bool operator ==(const Vector& v2) const;
405 
411  bool operator !=(const Vector& v2) const;
412 
422  bool operator <(const Vector& v2) const;
423 
433  bool operator <=(const Vector& v2) const;
434 
444  bool operator >(const Vector& v2) const;
445 
455  bool operator >=(const Vector& v2) const;
456 
457  /*
458  * Additional Vector operations
459  * ----------------------------
460  * In addition to the methods listed in this interface, the Vector
461  * class supports the following operations:
462  *
463  * - Stream I/O using the << and >> operators
464  * - Deep copying for the copy constructor and assignment operator
465  * - Iteration using the range-based for statement or STL iterators
466  *
467  * The iteration forms process the Vector in index order.
468  */
469 
470  /* Private section */
471 
472  /**********************************************************************/
473  /* Note: Everything below this point in the file is logically part */
474  /* of the implementation and should not be of interest to clients. */
475  /**********************************************************************/
476 
477 private:
478  /*
479  * Implementation notes: Vector data structure
480  * -------------------------------------------
481  * The elements are stored in a std::vector, the regular C++ library
482  * type representing a sequence of elements. We wrap std::vector because
483  * it has no runtime safety checks, something that's tricky to get used
484  * to when you're first learning to use these types.
485  *
486  * There's an edge case in the C++ libraries where std::vector<bool> doesn't
487  * work as you might think it does. This is widely regarded as a mistake
488  * in the language design and there's been a proposal to fix it for many
489  * years now. In the interim, we get around this by falling back on the
490  * std::deque type in the event that the client wants to make a
491  * Vector<bool>
492  */
493  using ContainerType = typename std::conditional<std::is_same<ValueType, bool>::value,
494  std::deque<bool>,
495  std::vector<ValueType>>::type;
496 
497  /* Instance variables */
498  ContainerType _elements;
500 
501  /* Private methods */
502 
503  /*
504  * Throws an ErrorException if the given index is not within the range of
505  * [min..max] inclusive.
506  * This is a consolidated error handler for all various Vector members that
507  * accept index parameters.
508  * The prefix parameter represents a text string to place at the start of
509  * the error message, generally to help indicate which member threw the error.
510  *
511  * We make prefix a const char* rather than a string to avoid having to
512  * construct and then destroy the prefix with each call.
513  */
514  void checkIndex(int index, int min, int max, const char* prefix) const;
515 
516  /*
517  * Hidden features
518  * ---------------
519  * The remainder of this file consists of the code required to
520  * support deep copying and iteration. Including these methods
521  * in the public interface would make that interface more
522  * difficult to understand for the average client.
523  */
524 
525 public:
531  Vector& operator ,(const ValueType& value);
532 
535 
536  iterator begin();
537  iterator end();
538  const_iterator begin() const;
539  const_iterator end() const;
540 
541  /* Updates the internal version count. Only our libraries need this, and they only
542  * need it in rare cases where an operation that's semantically mutating but bitwise
543  * non-mutating occurs.
544  */
545  void updateVersion();
546 };
547 
548 /* Implementation section */
549 
550 template <typename ValueType>
551 Vector<ValueType>::Vector(int n, ValueType value) {
552  if (n < 0) error("Cannot create a Vector with a negative number of elements.");
553  _elements.assign(n, value);
554 }
555 
556 template <typename ValueType>
557 Vector<ValueType>::Vector(std::initializer_list<ValueType> list)
558  : _elements(list) {
559 }
560 
561 /*
562  * Implementation notes: Vector methods
563  * ------------------------------------
564  * The basic Vector methods are straightforward and should require
565  * no detailed documentation.
566  */
567 template <typename ValueType>
568 void Vector<ValueType>::add(const ValueType& value) {
569  insert(size(), value);
570 }
571 
572 template <typename ValueType>
574  for (const ValueType& value : v) {
575  add(value);
576  }
577  return *this; // BUGFIX 2014/04/27
578 }
579 
580 template <typename ValueType>
582  return const_cast<ValueType&>(static_cast<const Vector &>(*this).back());
583 }
584 
585 template <typename ValueType>
586 const ValueType& Vector<ValueType>::back() const {
587  if (isEmpty()) {
588  error("Vector::back: vector is empty");
589  }
590  return _elements.back();
591 }
592 
593 template <typename ValueType>
595  _elements.clear();
596  _version.update();
597 }
598 
599 template <typename ValueType>
600 bool Vector<ValueType>::contains(const ValueType& value) const {
601  return indexOf(value) >= 0;
602 }
603 
604 template <typename ValueType>
606  return stanfordcpplib::collections::equals(*this, v);
607 }
608 
609 template <typename ValueType>
611  return const_cast<ValueType&>(static_cast<const Vector &>(*this).front());
612 }
613 
614 template <typename ValueType>
615 const ValueType& Vector<ValueType>::front() const {
616  if (isEmpty()) {
617  error("Vector::front: vector is empty");
618  }
619  return _elements.front();
620 }
621 
622 template <typename ValueType>
623 const ValueType& Vector<ValueType>::get(int index) const {
624  checkIndex(index, 0, size()-1, "get");
625  return _elements[index];
626 }
627 
628 template <typename ValueType>
629 int Vector<ValueType>::indexOf(const ValueType& value) const {
630  auto result = std::find(_elements.begin(), _elements.end(), value);
631  if (result == _elements.end()) return -1;
632  return result - _elements.begin();
633 }
634 
635 template <typename ValueType>
636 void Vector<ValueType>::insert(int index, const ValueType& value) {
637  checkIndex(index, 0, size(), "insert");
638  _elements.insert(_elements.begin() + index, value);
639  _version.update();
640 }
641 
642 template <typename ValueType>
644  return _elements.empty();
645 }
646 
647 template <typename ValueType>
648 int Vector<ValueType>::lastIndexOf(const ValueType& value) const {
649  auto result = std::find(_elements.rbegin(), _elements.rend(), value);
650  if (result == _elements.rend()) return -1;
651 
652  /* These iterators are going in the reverse direction, and so the index they give is the number of
653  * steps from the end of the range, not from the beginning. Reverse this before returning the
654  * value.
655  */
656  return (size() - 1) - (result - _elements.rbegin());
657 }
658 
659 /*
660  * Implementation notes: mapAll
661  * ----------------------------
662  * The various versions of the mapAll function apply the function or
663  * function object to each element in ascending index order.
664  */
665 template <typename ValueType>
666 void Vector<ValueType>::mapAll(std::function<void (const ValueType&)> fn) const {
667  for (const auto& elem: _elements) {
668  fn(elem);
669  }
670 }
671 
672 template <typename ValueType>
674  if (isEmpty()) {
675  error("Vector::pop_back: vector is empty");
676  }
677  auto result = _elements.back();
678  _elements.pop_back();
679  _version.update();
680  return result;
681 }
682 
683 template <typename ValueType>
685  if (isEmpty()) {
686  error("Vector::pop_front: vector is empty");
687  }
688  auto result = _elements.front();
689  _elements.erase(_elements.begin());
690  _version.update();
691  return result;
692 }
693 
694 template <typename ValueType>
695 void Vector<ValueType>::push_back(const ValueType& value) {
696  insert(size(), value);
697 }
698 
699 template <typename ValueType>
700 void Vector<ValueType>::push_front(const ValueType& value) {
701  insert(0, value);
702 }
703 
704 template <typename ValueType>
705 void Vector<ValueType>::remove(int index) {
706  checkIndex(index, 0, size() - 1, "remove");
707  _elements.erase(_elements.begin() + index);
708  _version.update();
709 }
710 
711 template <typename ValueType>
713  return pop_back();
714 }
715 
716 template <typename ValueType>
718  return pop_front();
719 }
720 
721 template <typename ValueType>
722 void Vector<ValueType>::removeValue(const ValueType& value) {
723  int index = indexOf(value);
724  if (index >= 0) {
725  remove(index);
726  }
727 }
728 
729 template <typename ValueType>
731  std::reverse(begin(), end());
732 }
733 
734 template <typename ValueType>
735 void Vector<ValueType>::set(int index, const ValueType& value) {
736  checkIndex(index, 0, size()-1, "set");
737  _elements[index] = value;
738 }
739 
740 template <typename ValueType>
742  return _elements.size();
743 }
744 
745 template <typename ValueType>
747  for (int i = 0; i < size() - 1; i++) {
748  std::swap(_elements[i], _elements[randomInteger(i, size() - 1)]);
749  }
750 }
751 
752 template <typename ValueType>
754  std::sort(begin(), end());
755 }
756 
757 template <typename ValueType>
758 Vector<ValueType> Vector<ValueType>::subList(int start, int length) const {
759  checkIndex(start, 0, size(), "subList");
760  checkIndex(start + length, 0, size(), "subList");
761  if (length < 0) {
762  error("Vector::subList: length cannot be negative");
763  }
764  Vector<ValueType> result;
765  for (int i = start; i < start + length; i++) {
766  result.add(get(i));
767  }
768  return result;
769 }
770 
771 template <typename ValueType>
773  return subList(start, size() - start);
774 }
775 
776 template <typename ValueType>
778  std::ostringstream os;
779  os << *this;
780  return os.str();
781 }
782 
783 /*
784  * Implementation notes: Vector selection
785  * --------------------------------------
786  * The following code implements traditional array selection using
787  * square brackets for the index.
788  */
789 template <typename ValueType>
790 ValueType& Vector<ValueType>::operator [](int index) {
791  return const_cast<ValueType&>(static_cast<const Vector &>(*this)[index]);
792 }
793 template <typename ValueType>
794 const ValueType& Vector<ValueType>::operator [](int index) const {
795  checkIndex(index, 0, size()-1, "operator []");
796  return _elements[index];
797 }
798 
799 template <typename ValueType>
801  Vector<ValueType> result = *this;
802  return result.addAll(v2);
803 }
804 
805 template <typename ValueType>
806 Vector<ValueType> Vector<ValueType>::operator +(const ValueType& elem) const {
807  Vector<ValueType> result = *this;
808  return result += elem;
809 }
810 
811 template <typename ValueType>
813  return addAll(v2);
814 }
815 
816 template <typename ValueType>
818  add(value);
819  return *this;
820 }
821 
822 template <typename ValueType>
823 bool Vector<ValueType>::operator ==(const Vector& v2) const {
824  return equals(v2);
825 }
826 
827 template <typename ValueType>
828 bool Vector<ValueType>::operator !=(const Vector& v2) const {
829  return !equals(v2);
830 }
831 
832 template <typename ValueType>
833 bool Vector<ValueType>::operator <(const Vector& v2) const {
834  return stanfordcpplib::collections::compare(*this, v2) < 0;
835 }
836 
837 template <typename ValueType>
838 bool Vector<ValueType>::operator <=(const Vector& v2) const {
839  return stanfordcpplib::collections::compare(*this, v2) <= 0;
840 }
841 
842 template <typename ValueType>
843 bool Vector<ValueType>::operator >(const Vector& v2) const {
844  return stanfordcpplib::collections::compare(*this, v2) > 0;
845 }
846 
847 template <typename ValueType>
848 bool Vector<ValueType>::operator >=(const Vector& v2) const {
849  return stanfordcpplib::collections::compare(*this, v2) >= 0;
850 }
851 
852 template <typename ValueType>
853 void Vector<ValueType>::checkIndex(int index, int min, int max, const char* prefix) const {
854  if (index < min || index > max) {
855  std::ostringstream out;
856  out << "Vector::" << prefix << ": index of " << index
857  << " is outside of valid range ";
858  if (isEmpty()) {
859  out << " (empty vector)";
860  } else {
861  out << "[";
862  if (min < max) {
863  out << min << ".." << max;
864  } else if (min == max) {
865  out << min;
866  } // else min > max, no range, empty vector
867  out << "]";
868  }
869  error(out.str());
870  }
871 }
872 
873 /*
874  * Implementation notes: The , operator
875  * ------------------------------------
876  * The comma operator works adding the right operand to the vector and
877  * then returning the vector by reference so that it is set for the next
878  * value in the chain.
879  */
880 template <typename ValueType>
882  add(value);
883  return *this;
884 }
885 
886 /*
887  * Implementation notes: << and >>
888  * -------------------------------
889  * The insertion and extraction operators use the template facilities in
890  * strlib.h to read and write generic values in a way that treats strings
891  * specially.
892  */
893 template <typename ValueType>
894 std::ostream& operator <<(std::ostream& os, const Vector<ValueType>& vec) {
896 }
897 
898 template <typename ValueType>
899 std::istream& operator >>(std::istream& is, Vector<ValueType>& vec) {
900  ValueType element;
901  return stanfordcpplib::collections::readCollection(is, vec, element, /* descriptor */ "Vector::operator >>");
902 }
903 
904 
905 /*
906  * Implementation notes: Iterator support
907  * --------------------------------------
908  * We used the checked iterator type, which requires us to provide information
909  * about the full range of values available.
910  */
911 template <typename ValueType>
913  return { &_version, _elements.begin(), _elements };
914 }
915 template <typename ValueType>
917  return { &_version, _elements.begin(), _elements };
918 }
919 template <typename ValueType>
921  return { &_version, _elements.end(), _elements };
922 }
923 template <typename ValueType>
925  return { &_version, _elements.end(), _elements };
926 }
927 
928 template <typename ValueType>
930  _version.update();
931 }
932 
933 /*
934  * Template hash function for vectors.
935  * Requires the element type in the Vector to have a hashCode function.
936  */
937 template <typename ValueType>
938 int hashCode(const Vector<ValueType>& vec) {
940 }
941 
942 /*
943  * Function: randomElement
944  * Usage: element = randomElement(v);
945  * ----------------------------------
946  * Returns a randomly chosen element of the given vector.
947  * Throws an error if the vector is empty.
948  */
949 template <typename T>
950 const T& randomElement(const Vector<T>& vec) {
952 }
953 
954 /*
955  * Randomly rearranges the elements of the given vector.
956  */
957 template <typename T>
958 void shuffle(Vector<T>& v) {
959  v.shuffle();
960 }
961 
962 #endif // _vector_h
ValueType & front()
Returns the element at index 0 in this vector (without removing it).
Definition: vector.h:610
iterator end()
Definition: vector.h:920
Vector< ValueType > & addAll(const Vector< ValueType > &v)
Adds all elements of the given other vector to this vector.
Definition: vector.h:573
bool operator<(const Vector &v2) const
Relational operators to compare two vectors.
Definition: vector.h:833
std::istream & readCollection(std::istream &input, CollectionType &collection, ElementType &element, string)
Definition: collections.h:493
void updateVersion()
Definition: vector.h:929
string toString() const
Converts the vector to a printable string representation such as "{10, 20, 30, 40}".
Definition: vector.h:777
Vector & operator+=(const Vector &v2)
Adds all of the elements from v2 to the end of this vector.
Definition: vector.h:812
bool equals(const Vector< ValueType > &v) const
Compares two vectors for equality.
Definition: vector.h:605
This class stores an ordered list of values similar to an array.
Definition: vector.h:86
bool operator>=(const Vector &v2) const
Relational operators to compare two vectors.
Definition: vector.h:848
virtual ~Vector()=default
Frees any heap storage allocated by this vector.
Vector< ValueType > subList(int start, int length) const
Returns a new vector containing the given subset range of elements from this vector.
Definition: vector.h:758
ValueType pop_back()
Removes and returns the last value of this vector.
Definition: vector.h:673
ValueType & back()
Returns the element at index (size - 1) in this vector (without removing it).
Definition: vector.h:581
const ValueType & get(int index) const
Returns the element at the specified index in this vector.
Definition: vector.h:623
bool operator>(const Vector &v2) const
Relational operators to compare two vectors.
Definition: vector.h:843
Vector & operator,(const ValueType &value)
Adds an element to the vector passed as the left-hand operatand.
Definition: vector.h:881
void shuffle()
Rearranges the order of the elements in this vector into a random order.
Definition: vector.h:746
ValueType & operator[](int index)
Overloads [] to select elements from this vector.
Definition: vector.h:790
void removeValue(const ValueType &value)
Removes the first occurrence of the element value from this vector.
Definition: vector.h:722
void ensureCapacity(int cap)
Guarantees that the vector&#39;s internal array is at least the given length.
void push_back(const ValueType &value)
Adds a new value to the end of this vector.
Definition: vector.h:695
ValueType pop_front()
Removes and returns the first value of this vector.
Definition: vector.h:684
void remove(int index)
Removes the element at the specified index from this vector.
Definition: vector.h:705
Definition: collections.h:685
bool operator==(const Vector &v2) const
Compares two vectors for equality.
Definition: vector.h:823
ValueType removeBack()
Removes and returns the element at index (size - 1) in this vector.
Definition: vector.h:712
void add(const ValueType &value)
Adds a new value to the end of this vector.
Definition: vector.h:568
const ElementType & randomElementIndexed(const CollectionType< ElementType > &collection)
Definition: collections.h:475
int lastIndexOf(const ValueType &value) const
Returns the index of the last occurrence of the given value.
Definition: vector.h:648
int indexOf(const ValueType &value) const
Returns the index of the first occurrence of the given value.
Definition: vector.h:629
bool operator<=(const Vector &v2) const
Relational operators to compare two vectors.
Definition: vector.h:838
void mapAll(std::function< void(const ValueType &)> fn) const
Calls the specified function on each element of the vector in ascending index order.
Definition: vector.h:666
int hashCodeCollection(const CollectionType &collection, bool orderMatters=true)
Definition: collections.h:429
std::ostream & writeCollection(std::ostream &out, CollectionType collection)
Definition: collections.h:620
void push_front(const ValueType &value)
Adds a new value to the start of this vector.
Definition: vector.h:700
bool contains(const ValueType &value) const
Returns true if the vector contains the given value.
Definition: vector.h:600
ValueType removeFront()
Removes and returns the element at index 0 in this vector.
Definition: vector.h:717
void reverse()
Reverses the order of the elements in this vector.
Definition: vector.h:730
bool equals(const CollectionType &coll1, const CollectionType &coll2)
Definition: collections.h:323
int compare(const CollectionType &coll1, const CollectionType &coll2)
Definition: collections.h:197
void set(int index, const ValueType &value)
Replaces the element at the specified index in this vector with a new value.
Definition: vector.h:735
int size() const
Returns the number of elements in this vector.
Definition: vector.h:741
bool isEmpty() const
Returns true if this vector contains no elements.
Definition: vector.h:643
void insert(int index, const ValueType &value)
Inserts the element into this vector before the specified index.
Definition: vector.h:636
auto randomElement(const Collection &collection) -> const decltype(*collection.begin())&
Definition: collections.h:462
iterator begin()
Definition: vector.h:912
void sort()
Rearranges the order of the elements in this vector into sorted order.
Definition: vector.h:753
bool operator!=(const Vector &v2) const
Compares two vectors for inequality.
Definition: vector.h:828
Vector()=default
Initializes a new empty vector.
Vector operator+(const Vector &v2) const
Concatenates two vectors and returns the result.
Definition: vector.h:800
void clear()
Removes all elements from this vector.
Definition: vector.h:594