vector.cpp

// # vector
//
// Dynamic array: https://en.wikipedia.org/wiki/Dynamic_array

#include "common.hpp"

int main() {
    // Create
    {
        // Empty
        {
            std::vector<int> v;
            // C++11 initializer lists:
            std::vector<int> v1{};
            assert(v == v1);
        }

        // Given size
        {
            std::vector<int> v(3);
            assert(v.size() == 3);
        }

        // Fill constructor.
        //
        // Make a `std::vector` with n copies of a single value.
        {
            // Copies of given object.
            {
                assert(std::vector<int>(3, 2) == std::vector<int>({2, 2, 2}));
            }

            // Default constructed objects. int = 0.
            {
                assert(std::vector<int>(3) == std::vector<int>({0, 0, 0}));
            }
        }

        // Range copy.
        {
            std::vector<int> v{0, 1, 2};
            std::vector<int> v1(v.begin(), v.end());
            assert(v == v1);
        }

        // From existing array.
        {
            int myints[]{0, 1, 2};
            std::vector<int> v(myints, myints + sizeof(myints) / sizeof(int));
            std::vector<int> v1 = {0, 1, 2};
            assert(v == v1);
        }
    }

    // Vectors have order.
    {
        std::vector<int> v{0, 1, 2};
        std::vector<int> v1{2, 1, 0};
        assert(v != v1);
    }

    // # Data
    //
    // Storage is required to be contiguous by TR1:
    // http://stackoverflow.com/questions/849168/are-stdvector-elements-guaranteed-to-be-contiguous
    //
    // C++11 introduces the `data()` method which returns a pointer to the first element.
    // It works even if the vector is empty.
    // http://stackoverflow.com/questions/6485496/how-to-get-stdvector-pointer-to-the-raw-data
    //
    // Before C++11, `&v[0]` works for non-empty vectors.
    //
    // `vector<bool>` as usual is an exception.
    {
        std::vector<int> v{0, 1, 2};
        assert(&v[0] == v.data());
        // True because contiguous:
        assert(v.data()[1] == v[1]);
    }

    // size methods
    {
        // # size
        //
        // # length of vector
        //
        // # size_type
        //
        // Number of elements in std::vector.
        //
        // This has type std::vector<X>::size_type
        {
            std::vector<int> v;
            assert(v.size() == 0);
            v.push_back(0);
            assert(v.size() == 1);
        }

        // # resize
        //
        // If larger than current size, append given element at end default initialized.
        //
        // If smaller than current size, remove elements from end.
        {
            // Reduce size
            {
                std::vector<int> v{0, 1};
                v.resize(1);
                assert((v == std::vector<int>{0}));
            }

            // Increase size
            {
                // Using default constructor objects.
                {
                    std::vector<int> v{1};
                    v.resize(3);
                    assert((v == std::vector<int>{1, 0, 0}));
                }

                // Using copies of given object.
                {
                    std::vector<int> v{1};
                    v.resize(3, 2);
                    assert((v == std::vector<int>{1, 2, 2}));
                }
            }
        }
    }

    // Capacity methods.
    {
        // # capacity
        //
        // Get currently allocated size.
        //
        // Different from size, which is the number of elements in the std::vector!
        //
        // At least as large as size.
        //
        // Likely to be a power of 2 on most implementations.
        {
            std::vector<int> v;
            v.push_back(0);
            v.push_back(1);
            v.push_back(2);
            assert(v.capacity() >= 3);
            std::cout << "capacity = " << v.capacity() << std::endl;
        }

        // # max_size: estimate of what your OS allows you to allocate
        {
            std::cout << "max_size (MiB) = " << std::vector<int>().max_size() / (1 << 20) << std::endl;
        }

        // # reserve: increase allocated size if larger than current size.
        {
            std::vector<int> v;
            v.reserve(3);
            assert(v.capacity() >= 3);
            // size() is untouched
            assert(v.empty());
        }

#if __cplusplus >= 201103L
        // # shrink_to_fit
        {
            std::vector<int> v{0, 1};
            v.reserve(4);
            v.shrink_to_fit();
            assert(v.capacity() == 2);
        }
#endif
    }

    // `std::vector` stores copies of elements, not references.
    {
        std::string s = "abc";
        std::vector<std::string> v{s};
        v[0][0] = '0';
        assert(v[0] == "0bc");
        assert(s    == "abc");
    }

    // Modify.
    {
        {
            std::vector<int> v;
            v = {0};
            v = {0, 1};
            assert((v == std::vector<int>{0, 1}));
        }

        // # push_back
        //
        // # append
        //
        // Push to the end of the std::vector.
        //
        // Amortized time O(1), but may ocassionaly make the std::vector grow,
        // which may required a full data copy to a new location if the
        // current backing array cannot grow.
        //
        // # push_front
        //
        // Does not exist for std::vector, as it would always be too costly (requires to move
        // each element forward.) Use deque if you need that.
        {
            std::vector<int> v;
            std::vector<int> v1;

            v.push_back(0);
            v1 = {0};
            assert(v == v1);

            v.push_back(1);
            v1 = {0, 1};
            assert(v == v1);

            // push_back makes copies with assign `=`
            //
            // If you want references, use pointers, or even better, auto_ptr.
            {
                std::vector<std::string> v;
                std::string s = "abc";

                v.push_back(s);
                v[0][0] = '0';
                assert(v[0] == "0bc");

                //s was not changed
                assert(s == "abc");
            }
        }

        // # pop_back
        //
        // Remove last element from std::vector.
        //
        // No return val. Rationale: http://stackoverflow.com/questions/12600330/pop-back-return-value
        {
            std::vector<int> v{0, 1};

            v.pop_back();
            assert(v == std::vector<int>{0});

            v.pop_back();
            assert(v == std::vector<int>{});
        }

        // # insert
        //
        // This operation is inneficient for `std::vector` if it is not done at the end.
        //
        // # concatenate
        //
        // The range form of insert can be used to append one vector to anoter.
        {
            // Single element form.
            {
                std::vector<int> v = {0,1};
                std::vector<int> v1;

                v.insert(v.begin(), -1);
                v1 = {-1, 0, 1};
                assert(v == v1);

                v.insert(v.end(), 2);
                v1 = {-1, 0, 1, 2};
                assert(v == v1);
            }

            // Range form.
            {
                std::vector<int> v = {0,1};
                std::vector<int> v1 = {2,3};

                v.insert(v.end(), v1.begin(), v1.end());
                assert((v == std::vector<int>{0, 1, 2, 3}));
            }
        }

        // # erase
        //
        // Remove given elements from container given iterators to those elements.
        //
        // This operation is inefficient for std::vectors,
        // since it may mean reallocation and therefore up to $O(n)$ operations.
        //
        // Returns a pointer to the new location of the element next to the last removed element.
        {
            // Single element
            {
                std::vector<int> v{0, 1, 2};
                auto it = v.erase(v.begin() + 1);
                assert((v == std::vector<int>{0, 2}));
                assert(*it == 2);
            }

            // Range
            {
                std::vector<int> v{0, 1, 2, 3};
                auto it = v.erase(v.begin() + 1, v.end() - 1);
                assert((v == std::vector<int>{0, 3}));
                assert(*it == 3);
            }
        }

        // # remove
        //
        // Helper to remove all elements that compare equal to a value from container.
        //
        // Does not actually remove the elements: only ensures that the beginning of the range
        // does not contain the item to be removed.
        //
        // Ex:
        //
        //     0, 1, 0, 2, 0, 1
        //
        // Value to remove: `0`
        //
        // Range to remove from:
        //
        //     0, 1, 0, 2, 0, 1
        //     ----------
        //
        // After the remove:
        //
        //     1, 2, X, Y, 0, 1
        //     ----------
        //
        // where `X` and `Y` are trash, and not necessarily 0!
        //
        // To actually remove the items, an `erase` is needed after remove
        // because `remove` is not a class method and thus cannot remove items from a container.
        //
        // This is called the erase and remove idiom:
        // https://en.wikipedia.org/wiki/Erase%E2%80%93remove_idiom
        //
        // After a remove the container becomes:
        //
        //     1, 2, 0, 1
        {
            std::vector<int> v{0, 1, 0, 2, 0, 1};
            auto end = std::next(v.end(), -2);
            v.erase(std::remove(v.begin(), end, 0), end);
            assert((v == std::vector<int>{1, 2, 0, 1}));
        }

        // # clear
        //
        // Make the vector empty.
        {
            std::vector<int> v{0, 1, 2};
            v.clear();
            assert(v.empty());
        }

        // # vector to string
        //
        // No built-in way.
        //
        // http://stackoverflow.com/questions/4850473/pretty-print-c-stl-containers
        // 190 votes on question, 30 on top answer! Come on C++!
        //
        // http://stackoverflow.com/questions/1430757/c-vector-to-string?lq=1
    }

    // Random access is O(1) since array backed
    {

        std::vector<int> v{0, 1, 2};

        // First element:
        assert(v.front() == 0);
        assert(v.front() == v[0]);

        // Last element:
        assert(v.back() == 2);

        // Nth element:
        v[0] = 1;
        assert(v[0] == 1);

        // BAD: just like array overflow will not change std::vector size,
        // and is unlikely to give an error
        {
            //v1[2] = 2;
        }

        // # back
        //
        // Get reference to last  element in vector.
        //
        // # front
        //
        // Get reference to first element in vector.
        //
        // # at
        //
        // Like `[]`, but does bound checking and throws `out_of_range` in case of overflow.
        {
            std::vector<int> v{0, 1, 2};
            assert(v.front() == 0);
            assert(v.at(1)   == 1);
            assert(v.back()  == 2);
            try {
                assert(v.at(3) == 0);
            } catch (std::out_of_range& e) {
            } catch (...) {
                assert(false);
            }

            // Undefined on empty.
            {
                std::vector<int> v;
                //v.front();
                //v.back();
            }
        }
    }

    // # bool std::vector
    //
    // *bool std::vectors are evil!*
    //
    // The standard requires `vector` to have an specialization for bool which packs bits efficiently.
    //
    // While efficient, in order to work this specialization breaks common std::vector interfaces
    // that require taking addresses only in the case of this specialization, since it does not
    // make sense to takes addresses anymore.
    //
    // Alternatives to `vector<bool>`: <http://stackoverflow.com/questions/670308/alternative-to-vectorbool>
    //
    // A good alternative seem to be deque<bool>, which behaves as intended.
    {
        // Works fine and dandy as expected.
        {
            std::vector<int> v{1, 0};
            int& i(v[0]);
        }

        // Does not compile!!!
        {
            std::vector<bool> v{true, false};
            //bool& b(v[0]);
        }

        // It was not a problem with bool, the problem really is `vector<bool>`.
        {
            bool b[]{true, false};
            bool& b2(b[0]);
        }
    }
}