Challenge Accepted:C++ Standard Template Library

Bevezetés

˝ Megoldási lehetoségek

Nehézségek

Összefoglalás

Challenge Accepted: C++ Standard Template Library Pataki Norbert ELTE Informatikai Kar, Programozási Nyelvek és Fordítóprogramok Tanszék [email protected]

Szakmai Esti Mesék

Challenge Accepted:C++ Standard Template Library

Pataki Norbert

Bevezetés

Nehézségek

˝ Megoldási lehetoségek

Összefoglalás

C++ Standard Template Library

Felépítése konténerek: vector, set, map, stb. algoritmusok: copy, find_if, sort, stb.

˝ Elonyök Muveletigény ˝ garanciák

Challenge Accepted:C++ Standard Template Library

Pataki Norbert

Bevezetés

Nehézségek

˝ Megoldási lehetoségek

Összefoglalás

21 nap alatt...

Challenge Accepted:C++ Standard Template Library

Pataki Norbert

Bevezetés

Nehézségek

˝ Megoldási lehetoségek

Összefoglalás

Olvasnivalók

Challenge Accepted:C++ Standard Template Library

Pataki Norbert

Bevezetés

Nehézségek

˝ Megoldási lehetoségek

Összefoglalás

Általános nehézségek

Fordítási hibaüzenetek Hordozhatósági problémák Teljesítmény csökkenés Memória szivárgás Korrupt, inkorrekt konténerek Egyéb futási ideju˝ hibák Különös viselkedés

Challenge Accepted:C++ Standard Template Library

Pataki Norbert

Bevezetés

Nehézségek

˝ Megoldási lehetoségek

Összefoglalás

Fordítási hibaüzenetek

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

Challenge Accepted:C++ Standard Template Library

Pataki Norbert

Bevezetés

Nehézségek

˝ Megoldási lehetoségek

Összefoglalás

Fordítási hibaüzenetek

Challenge Accepted:C++ Standard Template Library

Pataki Norbert

Bevezetés

Nehézségek

˝ Megoldási lehetoségek

Összefoglalás

Fordítási hibaüzenetek

C++ templates: megszorítás nélküli template const T& max( const T& a, const T& b ) { return a < b ? b : a; } Concept Concept lite

Challenge Accepted:C++ Standard Template Library

Pataki Norbert

Bevezetés

Nehézségek

˝ Megoldási lehetoségek

Összefoglalás

Hiányzó fordítási hibaüzenetek class complex { // ... public: complex( double re, double im ) { // ... } }; // operator< nélkül, szokás szerint // ... std::set d; // Lefordul Challenge Accepted:C++ Standard Template Library

Pataki Norbert

Bevezetés

Nehézségek

˝ Megoldási lehetoségek

Összefoglalás

Hiányzó fordítási hibaüzenetek class complex { // ... public: complex( double re, double im ) { // ... } }; // operator< nélkül, szokás szerint // ... std::set d; d.insert( complex( 1.11, 2.22 ) ); Challenge Accepted:C++ Standard Template Library

Pataki Norbert

Bevezetés

Nehézségek

˝ Megoldási lehetoségek

Összefoglalás

Fordítási hibaüzenet

Challenge Accepted:C++ Standard Template Library

Pataki Norbert

Bevezetés

Nehézségek

˝ Megoldási lehetoségek

Összefoglalás

Prófécia

Challenge Accepted:C++ Standard Template Library

Pataki Norbert

Bevezetés

Nehézségek

˝ Megoldási lehetoségek

Összefoglalás

˝ Egyezoség

Mikor egyezik meg két érték (a és b)? ˝ Egyenloség: a == b Ekvivalencia: (!( a < b ) && !( b < a ))

Challenge Accepted:C++ Standard Template Library

Pataki Norbert

Bevezetés

Nehézségek

˝ Megoldási lehetoségek

Összefoglalás

Rendezések

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

Challenge Accepted:C++ Standard Template Library

Pataki Norbert

Bevezetés

Nehézségek

˝ Megoldási lehetoségek

Összefoglalás

Rendezések 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

Challenge Accepted:C++ Standard Template Library

Pataki Norbert

Bevezetés

Nehézségek

˝ Megoldási lehetoségek

Összefoglalás

A probléma háttere

˝ o˝ rendezés szerint !(404 >= 404) Ekvivalencia az eloz && !(404 >= 404), ami szerint a 404 nem ekvivalens a 404-gyel. A funktor nem teljesíti a szigorú részben rendezés feltételét

Challenge Accepted:C++ Standard Template Library

Pataki Norbert

Bevezetés

Nehézségek

˝ Megoldási lehetoségek

Összefoglalás

˝ Algoritmusok elofeltételei/feltevései

Rendezett intervallumok algoritmusai: lower_bound, upper_bound, equal_range, binary_search unique, stb. copy, transform, stb.

Challenge Accepted:C++ Standard Template Library

Pataki Norbert

Bevezetés

Nehézségek

˝ Megoldási lehetoségek

Összefoglalás

Keresés rendezett konténerekben

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

Challenge Accepted:C++ Standard Template Library

Pataki Norbert

Bevezetés

Nehézségek

˝ Megoldási lehetoségek

Összefoglalás

Hiba detektálás

Statikus elemzés Template metaprogramming Runtime validáció Megfontolások Compiler- és könyvtárfüggetlenség Muveletigény ˝ garanciák Külön tool vagy fordítóprogram feladat Fordítás és futási ido˝ növekedés Könyvtári módosítást igényel-e

Challenge Accepted:C++ Standard Template Library

Pataki Norbert

Bevezetés

Nehézségek

˝ Megoldási lehetoségek

Összefoglalás

Téziseim

Formális eszközök Fordítási ideju˝ megoldások Futási ideju˝ megközelítések

Challenge Accepted:C++ Standard Template Library

Pataki Norbert

Bevezetés

Nehézségek

˝ Megoldási lehetoségek

Összefoglalás

Visual Studio warning

warning C4100: ’t’ : unreferenced formal parameter ... see reference to function template instantiation ’void warning(T)’ being compiled with [ T=COPY_ALGORITHM_WITHOUT_INSERTER_ITERATOR ]

Challenge Accepted:C++ Standard Template Library

Pataki Norbert

Bevezetés

Nehézségek

˝ Megoldási lehetoségek

Összefoglalás

g++ warning

In instantiation of ’void warning(T) [ with T = COPY_ALGORITHM_WITHOUT_INSERTER_ITERATOR ]’: ... instantiated from here ... warning: unused parameter ’t’

Challenge Accepted:C++ Standard Template Library

Pataki Norbert

Bevezetés

Nehézségek

˝ Megoldási lehetoségek

Összefoglalás

˝ Fordítási ellenorzések

believe-me mark transform, copy... vector, COAP find, count algoritmusok: rendezett adatszerkezeten nincs believe-me mark

...

Challenge Accepted:C++ Standard Template Library

Pataki Norbert

Bevezetés

Nehézségek

˝ Megoldási lehetoségek

Összefoglalás

˝ Futási ideju˝ ellenorzések

struct descending : strict_weak_ordering { bool operator()( int a, int b ) const { return !( a < b ); } };

Challenge Accepted:C++ Standard Template Library

Pataki Norbert

Bevezetés

Nehézségek

˝ Megoldási lehetoségek

Összefoglalás

˝ Futási ideju˝ ellenorzések

Funktorok tulajdonságai Másoló algoritmusok javítása ˝ Algoritmus elofeltételek stb.

Challenge Accepted:C++ Standard Template Library

Pataki Norbert

Bevezetés

Nehézségek

˝ Megoldási lehetoségek

Összefoglalás

Összefoglalás

C++ Standard Template Library ˝ ˝ elonyök / hibalehetoségek

Megközelítések statikus elemzés template metaprogramming runtime validáció

Challenge Accepted:C++ Standard Template Library

Pataki Norbert