Musings

A random collection

Archive for the ‘STL’ Category

C++: Standard Library

STL provides:

  1. Containers:
    • vector, list, deque
    • stack, queue, priority_queue
    • map, set, bitset, multimap, multiset
  2. Iterators – copied (iter1 = iter2, , copy-constructed (Iterator iter1(iter2)), incremented (iter++, ++iter, *iter++)
    • input iterator – equality/inequality comparison (iter == end(), iter != end()), dereference as rvalue (i = *iter, iter->ival) – istream_iterator, istream_buf_iterator
    • output iterator – dereference as lvalue (*iter = x) – ostream_iterator, ostreambuf_iterator
    • forward iterator – default constructor (ForwardIterator iter, ForwardIterator())
    • bidirectional iterator – decrement (iter--, --iter, *iter--)
    • random access iterator – ptr arithmetic (iter + 10, iter-10, n = iter2-iter1), inequality comparison (iter1 < iter2, iter1 > iter2), compound assignment (+=, -=), offset dereference (iter[n])
    • Inserter iteratorsback_insert_iterator, front_insert_iterator, insert_iterator
    • Inserter iterator constructorsback_inserter, front_inserter, inserter
    • reverse_iterator
    • raw_storage_iterator
  3. Algorithms:
    • 12 non-modifying sequence operationsfor_each, find, find_if, find_end, find_first_of, adjacent_find, count, count_if, mismatch, equal, search, search_n
    • 27 modifying sequence operationscopy, copy_backward, swap, swap_ranges, iter_swap, transform, replace, replace_if, replace_copy, replace_copy_if, fill, fill_n, generate, generate_n, remove, remove_if, remove_copy, remove_copy_if, unique, unique_copy, reverse, reverse_copy, rotate, rotate_copy, random_shuffle, partition, stable_partition
    • 5 sortingsort, stable_sort, partial_sort, partial_sort_copy, nth_element
    • 4 binary search on sorted rangeslower_bound, upper_bound, equal_range, binary_search
    • 7 merge operationsmerge, inplace_merge, includes, set_union, set_intersection, set_difference, set_symmetric_difference
    • 4 heap operationspush_heap, pop_heap, make_heap, sort_heap
    • 7 min/max operationsmin, max, min_element, max_element, lexicographical_compare, next_permutation, prev_permutation
    • 4 numericaccumulate, adjacent_difference, inner_product, partial_sum
    • raw memoryuninitialized_copy, uninitialized_fill, uninitialized_fill_n
  4. Function Objects:
    • base classesunary_function, binary_function
    • arithmeticplus, minus, multiplies, divides, modulus, negate
    • comparisonequal_to, not_equal_to, greater, less, greater_equal, less_equal
    • logicallogical_and, logical_or, logical_not
    • negatorsnot1, not2
    • 2 parameter bindersbind1st, bind2nd
    • 3 convertorsptr_fun, mem_fun, mem_fun_ref
    • 14 instrumental typesunary_negate, binary_negate, binder1st, binder2nd, pointer_to_unary_function, pointer_to_binary_function, mem_fun_t, mem_fun1_t, const_mem_fun_t, const_mem_fun1_t, mem_fun_ref_t, mem_fun1_ref_t, const_mem_fun_ref_t, const_mem_fun1_ref_t
  5. valarray
  6. exceptionslogical (logic_error, domain_error, invalid_argument, length_error, out_of_range), runtime (runtime_error, range_error, overflow_error, underflow_error)
  7. memory – auto_ptr, auto_ptr_ref
  8. string
  9. RTTItypeid, type_info
  10. I/O Streamistream, ostream, iostream, streambuf, filebuf, stringbuf, ifstream, ofstream, fstream, istringstream, ostringstream, stringstream, getline – cin, cout, cerr, clog
  11. Locale

Written by curious

July 15, 2010 at 9:00 am

Posted in STL

C++: Smart Pointers

Many choices for Smart Pointers or Auto Pointers:

  1. Boost Smart Pointers
    1. Safe Pointers: Simple sole ownership of single objects
    2. Shared Pointers: Object ownership shared among multiple pointers
    3. Weak Pointers: Non-owning observers of an object owned by shared_ptr
    4. Intrusive Pointers: Shared ownership of objects with an embedded reference count
  2. STL Auto Pointers

What are some of the problems with std::auto_ptr?

auto_ptr is a ownership based smart-pointer. The auto_ptr owns the object it points to and is responsible for freeing the memory when it goes out of scope.

If a auto_ptr is assigned to another auto_ptr, the new auto_ptr becomes the owner and the old auto_ptr is set to NULL.

  1. auto_ptr has explicit constructor
    auto_ptr<int> p1(new int(21));  // ok
    auto_ptr<int> p2 = new int(101); // error!
    
  2. Problem with storing pointers to arrays
    auto_ptr<B> p1(new int[51]);  // problem with delete, does not call delete[]
    
  3. No pointer arithmetic supported
    ++p1; // error!
    *p1 = 10; // ok
    
  4. auto_ptr not suitable for STL containers
    vector< auto_ptr<int> > v; // invitation to problems
    sort(v.begin(), v.end()); // problems!!
    
  5. Copies of auto_ptr cause problems
    auto_ptr<int> p1(new int(101));
    auto_ptr<int> p2;
    
    p2 = p1; // p2 is owner of memory
    *p1 = 5; // error, p1 not owner anymore
    
    void f(auto_ptr<int> p) {}
    f(p2); // ownership transferred to temporary variable for passing by value
    
  6. Need to disallow unintentional ownership transfer, make it const. const auto_ptr will stop you from snatching ownership from it (will not allow – assignment, copy-ctor, release, reset)
    const auto_ptr<int> p1(new int(101));
    auto_ptr<int> p2;
    
    p2 = p1; // compilation error
    
    void f(auto_ptr<int> p) {}
    f(p1); // compiler error
    
  7. Class member auto_ptr objects should be declared const
    class A
    {
        const auto_ptr<B> p1;
    public:
        A(const A& that) : p1(new B(*that.p1)) {}
    
        A& operator=(const A& that)
        {
            if (this != &that)
            {
                // does not reset the pointer
                *p1 = *that.p1;
            }
        }
    
        // no destructor
        // ~A()
    };
    

More on “Using Auto Ptr Effectively

How do you implement a smart pointer?

template<typename X>
class SmartPtr
{
public:
    SmartPtr();
    explicit SmartPtr(X* p);      // always make single argument ctor explicit
    // SmartPtr(SmartPtr& that);  -- do not want this
    X* operator->();
    X* operator->() const;
    X& operator*();
    const X& operator*() const;
    operator void*() const;
    ~SmartPtr();
private:
    X* xptr;
};
Analysis
  1. Guess what design pattern is this? Proxy pattern
  2. Benefits summary: Less bugs (automatic cleanup, automatic initialization, dangling pointers), Exception Safety, Garbage Collection, Efficienct use of available memory(for Copy On Write – COW), in STL Containers (but don’t use std::auto_ptr for this).
  3. SmartPtr() initializes the NULL pointer. Ordinary pointer if left uninitialized may cause havoc if you happen to dereference it. SmartPtr makes sure it is at least initialized to NULL.

    When you dereference a pointer, if it is set to NULL, operator->() and operator*() can assert a failure. Which will not corrupt memory and instead will give predictable behavior of terminating your program.

    SmartPtr<SomeType> ptr1;  // initialized to 0, not to some random value
    *ptr1.field;                 // ASSERT failed!!!
    ptr1->field;                 // ASSERT failed!!!
    
  4. SmartPtr(X*) initializes the Smart pointer to the raw pointer and from now on will take the ownership of it. You get a safer pointer and you do not need to worry about releasing this memory anymore.
    {
        SmartPtr<SomeType> ptr1(new SomeType());
        // use ptr1 like a regular pointer
        ...
        // automatically release memory when going out of scope
    }
    
  5. Make SmartPtr(X*) explicit to ensure that no inadvertent conversions cause problems. Without explicit, the following code will be possible and may cause problems
    {
        SomeType* p1 = &obj1;
        SmartPtr<SomeType> ptr1(new SomeType());
    
        if (ptr1 == p1) 
            // Without explicit p1 will be converted to SmartPtr(p1)
            // and will be automatically lead to delete p1
        {
        }
    }
    
  6. What should we do on assignment, i.e. “operator=”? Create a new copy, Ownership transfer, Reference Counting, Reference Linking (keep a circular list of smart ptrs pointing to the same location), Copy on Write (reference count till no modification to the pointed object).

Written by curious

July 1, 2010 at 7:57 am

Posted in Boost, STL

C++: STLĀ IOStream

Open a file for Reading

std::ifstream inputfile;
inputfile.open(filename.c_str(), std::ios::in|std::ios::binary);
if (!inputfile.good())
{
  // error in opening file
}

while (!inputfile.eof())
{
  // read from the input stream
  inputfile >> some_str;
  inputfile >> some_int;
}
inputfile.close();

Open a file for Writing

std::ofstream outputfile;
outputfile.open(filename.c_str(), std::ios::binary);
if (!outputfile.good())
{
  // error in opening file
}

outputfile << some_str;
outputfile << some_int;

outputfile.close();

Reference books:
Standard C++ IOStreams and locales; Angelika Langer, Klaus Kreft

Written by curious

June 27, 2010 at 11:41 am

Posted in STL