[PDF] More Effective STL More Effective STL. Norbert Pataki.

View - Download More Effective STL

Previous PDF

Next PDF

IntroductionMisusage of STLMy proposed solutionsConclusion

More Effective STL

Norbert Pataki

Dept. Programming Languages and Compilers

patakino@elte.huC++ Meetup 2015

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Evolution

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Programming languages

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Standard Template Library (STL)

STL - part of C++ Standard

based on the generic programming paradigm

Components

handy generic containers container-indepedent algorithms iterators: bridge the gap allocators: accountable for allocation and deallocation of memoryfunctors, lambdas: for execution of user-defined code snippets without significant overheadbinders, adaptors, etc.

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

New problems

Compiler diagnostics

Portability

Performance

Memory leak

Corrupt, incorrect containers

Other bugs at runtime

Strange behaviour

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Compilation error diagnostics

std::list a; std::sort( a.begin(), a.end() );

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Compilation error diagnostics

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Compilation error diagnostics

C++ templates: unconstrained

template const T& max( const T& a, const T& b ) return a < b ? b : a; }Concept

Concept lite

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Missing compilation error diagnostics

class complex public: complex( double re, double im ) // without operator<, as usual std::set d; // Compiles

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Missing compilation error diagnostics

class complex public: complex( double re, double im ) // without operator<, as usual std::set d; d.insert( complex( 1.11, 2.22 ) );

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Error message

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Prophecy

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Functors for sortedness

struct descending bool operator()( int a, int b ) const return !( a < b );

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Functors for sortedness

const int not_found = 404; std::set s; s.insert( not_found ); s.insert( not_found ); std::cout << s.size(); // 2 std::cout << s.count( not_found ); // 0 std::multiset m; m.insert( not_found ); m.insert( not_found ); std::cout << m.size(); // 2 std::cout << m.count( not_found ); // 0

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Problem

Equality:operator==Equivalence:(!(keycomp()(a,b) && !(keycomp()(b,a)))Equivalence with the previous functor - e.g.!(404 >=

404) && !(404 >= 404), which evaluated as "404

does not equal to 404"The functor does not meet the strict weak ordering requirement

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Find in ordered containers

std::set s; int x; std::set::iterator i = std::find( s.begin(), s.end(), x ); std::set::iterator it = s.find( x );

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Elements in sets

class Employee std::string user_id; int salary; public:

Employee( const std::string& id): user_id( id )

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Elements in sets

struct EmployeeLess bool operator()( const Employee& a, const Employee& b ) const return a.get_id() < b.get_id();

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Elements in sets

set s; s.find( "johndoe" ) -> set_salary( ... );Compilation error

Before / After C++11

const_cast?mutable?Remove from set and insert with new salary...

New language construct

No payrise :-(

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Copy of predicates

template

FwdIterator remove_if( FwdIterator begin,

FwdIterator end,

Predicate p )

begin = find_if( begin, end, p ); if ( begin == end ) return begin; else

FwdIterator next = begin;

return remove_copy_if( ++next, end, begin, p );

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Strange predicate

class BadPredicate size_t timesCalled; public:

BadPredicate(): timesCalled( 0 ) { }

bool operator()( const Widget& ) return ++timesCalled==3; std::list c; c.erase( remove_if( c.begin(), c.end(), BadPredicate() ), c.end() ); // Which elements are removed?

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Usage of reverse iterators

std::vector v = {3, 1, 2, 3, 4, 5}; v.erase( std::find( v.rbegin(), v.rend(),

3 ).base() );

std::copy( v.begin(), v.end(), std::ostream_iterator( std::cout, " " ) );// 3 1 2 3 5

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Reverse iterators

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Usage ofcopyalgorithmIt is OK:

std::vector data; std::list datacopy( data.size() ); std::copy( data.begin(), data.end(), datacopy.begin() );

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Usage ofcopyalgorithmIt is OK:

std::vector data; std::list datacopy; std::copy( data.begin(), data.end(), std::back_inserter( datacopy ) );

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion Usage ofcopyalgorithmResults in an undefined behaviour: std::vector data; std::list datacopy; std::copy( data.begin(), data.end(), datacopy.begin() );

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Don"t panic

Always look on the bright side of life....

because we have software tools to detect problems

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Possible solutions

Compilation time

Template metaprogramming: compiler-level, preferred Static analysis: lint-like tool, Clang-based approach - with Gábor Horváth (in the Clang codebase)Runtime

Exceptions

Fix the problem

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Generating warnings

template inline void warning( T t ) struct COPY_ALGORITHM_WITHOUT_INSERTER_ITERATOR warning(

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Output of Visual Studio

warning C4100: "t" : unreferenced formal parameter see reference to function template instantiation "void being compiled with

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Output of g++

In instantiation of "void warning(T)

with T = COPY_ALGORITHM_WITHOUT_INSERTER_ITERATOR ... instantiated from here ... warning: unused parameter "t"

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Tag dispatch

template void advance( Iterator& i, Distance n ) advance( i, n, typename template void advance( Iterator& i,

Distance n,

std::random_access_iterator_tag ) i += n;

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Tag dispatch

template void advance( Iterator& i,

Distance n,

std::bidirectional_iterator_tag ) for( Distance j = 0; j < n; ++j ) ++i;

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion Extension ofiterator_traitsclass __inserting_iterator_tag {}; class __non_inserting_iterator_tag {};

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Extension ofiterator_traitstemplate

struct iterator_traits typedef typename T::iterator_category iterator_category; typedef typename T::value_type value_type; typedef typename T::difference_type difference_type; typedef typename T::pointer pointer; typedef typename T::reference reference; typedef __non_inserting_iterator_tag inserter;

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Overloaded algorithm

template

OutputIterator copy( InputIterator first,

InputIterator last,

OutputIterator result )

return copy( first, last, result, typename

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Overloaded algorithm

template

OutputIterator copy( InputIterator first,

InputIterator last,

OutputIterator result,

__non_inserting_iterator_tag ) warning( return copy( first, last, result, inserting_iterator_tag() );

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Overloaded algorithm

template

OutputIterator copy( InputIterator first,

InputIterator last,

OutputIterator result,

inserting_iterator_tag ) while( first != last ) result++ =*first++; return result;

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Believe-me marks

#define ALREADY_ALLOCATED __inserting_iterator_tag() std::vector data; std::list datacopy( data.size() ); std::copy( data.begin(), data.end(), datacopy.begin(),

ALREADY_ALLOCATED );

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Believe-me marks

std::vector v; int x; v.erase( std::find( v.rbegin(), v.rend(), x ).base( I_KNOW_WHAT_BASE_RETURNS ) - 1 );

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Same approach

transform,copy...reverse iterators stateless allocators vector find,countalgorithm: on sorted intervalsno believe-me marks

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Check of the prophecy

template struct strict_weak_ordering strict_weak_ordering() if ( reinterpret_cast (this)-> operator()( T(),T() ) throw bad_functor_exception(); };Evaluate the functor with two equal elements false must be returned because of irreflexivity

More Effective STLNorbert Pataki

IntroductionMisusage of STLMy proposed solutionsConclusion

Check of the prophecy - specialization

template struct strict_weak_ordering strict_weak_ordering() if ( reinterpret_castquotesdbs_dbs18.pdfusesText_24

[PDF] effective writing skills pdf

[PDF] effects of presidential election petition pdf

[PDF] effet de la progestérone sur la paroi de l'utérus

[PDF] effet doppler

[PDF] effet doppler animation

[PDF] effet doppler calcul vitesse

[PDF] effet doppler cours

[PDF] effet doppler définition

[PDF] effet doppler en pdf

[PDF] effet doppler et radars routiers

[PDF] effet doppler exercice

[PDF] effet doppler exercice corrigé

[PDF] effet doppler fizeau

[PDF] effet doppler formule

[PDF] effet doppler formule demonstration