From cc3c4241760be3e6047d7e0695271b16d20669bc Mon Sep 17 00:00:00 2001 From: Dariusz Murakowski Date: Wed, 12 Nov 2014 15:45:17 -0500 Subject: [PATCH] Fix sorted_vector compile errors (presumably due to gcc vs MSVC differences). --- main.cpp | 777 ++++++++++++++++++++++++++++---------------------------- sorted_vector.h | 601 ++++++++++++++++++++++--------------------- 2 files changed, 690 insertions(+), 688 deletions(-) diff --git a/main.cpp b/main.cpp index 6fb6acc..9eb137a 100644 --- a/main.cpp +++ b/main.cpp @@ -1,387 +1,390 @@ - -#pragma warning(disable:4786) - -#include -#include "sorted_vector.h" -#include -#include "assert.h" -#include -#include - -struct STest{ - std::string s; - int id; -}; - -STest MakeSTest() -{ - static int id= 0; - int nLen= rand()%10; - char* letters[]={"0","1"}; - STest stest; - - for(int i=0;i -bool is_unique(It beg,It beyond,Pred pred) -{ - return std::adjacent_find(beg,beyond,std::not2(pred))==beyond; -} -template -FwIt unsorted_find(FwIt beg,FwIt beyond,Pred pred) -{ - for(FwIt prev ;(prev=beg)!=beyond && ++beg!=beyond;){ - if( pred(*beg,*prev) ){ - return prev; - } - } - return beyond; -} -template -void TestSet(std::vector& v) -{ - std::set std_set; - {SimpTimer t("build std::set"); - for(unsigned i=0;i::iterator it= std_set.find(v[i]); - std::set::size_type nCount= std_set.count(v[i]); - assert( nCount==0 && it==std_set.end() - || nCount!=0 && it!=std_set.end()); - } - } -} -template -void TestSortedVector_AsSet(std::vector& v) -{ - codeproject::sorted_vector svec; - {SimpTimer t("build sortedvec_set (naiv)"); - for(unsigned i=0;i svec1; - {SimpTimer t("build sortedvec_set (opt.)"); - codeproject::sorted_vector::Cont& vec= svec1.get_container(); - for(unsigned i=0;i::iterator it= svec1.find(v[i]); - codeproject::sorted_vector::size_type nCount= svec1.count(v[i]); - assert( nCount==0 && it==svec1.end() - || nCount!=0 && it!=svec1.end()); - } - } - for(unsigned i=0;i -void TestMultiSet(std::vector& v) -{ - std::multiset svec; - - {SimpTimer t("build multiset"); - for(unsigned i=0;i::iterator it= svec.find(v[i]); - std::multiset::size_type nCount= svec.count(v[i]); - assert( nCount==0 && it==svec.end() - || nCount!=0 && it!=svec.end()); - } - } -} - -template -void TestSortedVector_AsMultiSet(std::vector& v) -{ - codeproject::sorted_vector svec; - {SimpTimer t("build sortedvec_multiset (naiv)"); - for(unsigned i=0;i svec1; - {SimpTimer t("build sortedvec_multiset (opt.)"); - codeproject::sorted_vector::Cont& vec= svec1.get_container(); - for(unsigned i=0;i::iterator it= svec1.find(v[i]); - codeproject::sorted_vector::size_type nCount= svec1.count(v[i]); - assert( nCount==0 && it==svec1.end() - || nCount!=0 && it!=svec1.end()); - } - } -/*test various functions*/ - const codeproject::sorted_vector svec2(svec); - assert(svec==svec2); - for(unsigned i=0;i svec3(v.begin(),v.end()); - assert(svec3==svec2); - codeproject::sorted_vector svec4(v.begin(),v.begin()+(v.end()-v.begin())/2); - svec4= svec3; - assert(svec4==svec3); - while(svec4.size()>0){ - svec4.pop_back(); - } -} - - - - -template -void ExecTests(std::vector& v) -{ - std::cout << "std::set versus 'sorted_vector as set'" << std::endl; - TestSet(v); - TestSortedVector_AsSet(v); - std::cout << "std::multiset versus 'sorted_vector as multiset'" << std::endl; - TestMultiSet(v); - TestSortedVector_AsMultiSet(v); -} - -template -void TestSetOperations(const std::vector& v0, - const std::vector& v1, - const std::vector& v2, - Pred pred) -{ -//A) compute the result of the set-operation: (v0-v1)+v2 - intersect(v1,v2) - codeproject::sorted_vector svec(v0.begin(),v0.end(),pred); - codeproject::sorted_vector svec_v1(pred); svec_v1= v1; - codeproject::sorted_vector svec_v2(pred); svec_v2= v2; - unsigned i,j; - for(i=0;i svec1(v0.begin(),v0.end(),pred); - for(unsigned k=0;k::size_type nSize= svec.size(); - codeproject::sorted_vector::size_type nSize1= svec1.size(); -//test whether results are the same - assert(svec==svec1); -} - - -codeproject::sorted_vector -BuildIntersection(std::vector& v0,std::vector& v1) -{ - codeproject::sorted_vector svec(v0.begin(),v0.end()); - codeproject::sorted_vector svecIntersection; - for(unsigned i=0;i -BuildIntersection1(std::vector& v0,std::vector& v1) -{ - codeproject::sorted_vector svec(v0.begin(),v0.end()); - codeproject::sorted_vector svecIntersection; - codeproject::sorted_vector::Cont& vInterSect= - svecIntersection.get_container(); - for(unsigned i=0;i A(a, a + N); - sorted_vector B(b, b + N); - sorted_vector C; - - cout << "Set A: "; - copy(A.begin(), A.end(), ostream_iterator(cout, " ")); - cout << endl; - cout << "Set B: "; - copy(B.begin(), B.end(), ostream_iterator(cout, " ")); - cout << endl; - - cout << "Union: "; - set_union(A.begin(), A.end(), B.begin(), B.end(), - ostream_iterator(cout, " "), - ltstr()); - cout << endl; - return 0; -} - -void TestAllSet() -{ - using namespace std; - using namespace codeproject; - typedef sorted_vector StrSet; - StrSet months; - months.insert("jan"); - months.insert("feb"); - months.insert("mar"); - months.insert("apr"); - months.insert("may"); - months.insert("jun"); - months.insert("jul"); - months.insert("aug"); - months.insert("sep"); - months.insert("oct"); - months.insert("nov"); - months.insert("dec"); - StrSet::iterator it= months.find("jul"); - assert(strcmp(*it,"jul")==0); - cout << "previous of jul (in alphabetical order) is " << (it[-1]) << endl; - cout << "next of jul (in alphabetical order) is " << (it[1]) << endl; - - cout << "months in alphabetical order: " << endl; - copy(months.begin(),months.end(),ostream_iterator(cout," ")); - cout << endl << "months in reverse alphabetical order: " << endl; - copy(months.rbegin(),months.rend(),ostream_iterator(cout," ")); - /*test count*/ - { - for(StrSet::iterator it= months.begin();it!=months.end();++it){ - assert(months.count(*it)==1); - } - } - /*test copy construction and comparison operators*/ - StrSet monthsCopy(months); - assert( months==monthsCopy - && months<=monthsCopy && months>=monthsCopy - && !(monthsmonthsCopy)); - - std::pair pairMismatch= - mismatch(months.begin(),months.end(),monthsCopy.begin()); - assert(pairMismatch.first==months.end() && pairMismatch.second==monthsCopy.end()); - - /*test insertion of already present element*/ - copy(months.begin(),months.end(),inserter(monthsCopy,monthsCopy.begin())); - assert(months.size()==monthsCopy.size()); - - /*test insert member functions*/ - months.insert(monthsCopy.begin(),monthsCopy.end()); - assert(months==monthsCopy); - StrSet months1(months.begin(),months.begin()+3); - months1.insert(months.begin()+1,months.end()); - assert(months1==months); - months1.insert("aug"); - months1.insert("xxx"); - months1.insert(months1.find("xxx"),"yyy"); - months1.insert("zzz"); - assert(months1>months && months1.size()==months.size()+3); - /*test erase member functions*/ - months1.erase(months1.find("xxx"),months1.end()); - assert(months1.size()==months.size()); - - /*test lower_bound,upper_bound,equal_range*/ - assert( strcmp(*months.lower_bound("jul"),"jul")==0); - - - cout << endl; -} - - -int main() -{ -//timed tests - std::vector v; - int i; - for(i=0;i<50000;i++){v.push_back(rand());} - std::cout << "--------------Tests with element type int-------------" << std::endl; - ExecTests(v); - - std::vector vt; - for(i=0;i<50000;i++){vt.push_back(MakeSTest());} - std::cout << "-Tests with element type 'STest' (string,int)--------" << std::endl; - ExecTests(v); - -//set operations-test - std::vector v1,v2; - for(i=0;i<10000;i++){v1.push_back(rand());} - for(i=0;i<10000;i++){v2.push_back(rand());} - TestSetOperations(v,v1,v2,std::greater()); - - assert(BuildIntersection(v1,v2)==BuildIntersection1(v1,v2)); - SGITest(); - TestAllSet(); - return 0; -} \ No newline at end of file + +#pragma warning(disable:4786) + +#include +#include "sorted_vector.h" +#include +#include "assert.h" +#include +#include +#include // ostream_iterator +#include // strcmp + +struct STest{ + std::string s; + int id; +}; + +STest MakeSTest() +{ + static int id= 0; + int nLen= rand()%10; + const char* letters[]={"0","1"}; + STest stest; + + for(int i=0;i +bool is_unique(It beg,It beyond,Pred pred) +{ + return std::adjacent_find(beg,beyond,std::not2(pred))==beyond; +} +template +FwIt unsorted_find(FwIt beg,FwIt beyond,Pred pred) +{ + for(FwIt prev ;(prev=beg)!=beyond && ++beg!=beyond;){ + if( pred(*beg,*prev) ){ + return prev; + } + } + return beyond; +} +template +void TestSet(std::vector& v) +{ + std::set std_set; + {SimpTimer t("build std::set"); + for(unsigned i=0;i::iterator it= std_set.find(v[i]); + typename std::set::size_type nCount= std_set.count(v[i]); + assert( nCount==0 && it==std_set.end() + || nCount!=0 && it!=std_set.end()); + } + } +} +template +void TestSortedVector_AsSet(std::vector& v) +{ + codeproject::sorted_vector svec; + {SimpTimer t("build sortedvec_set (naiv)"); + for(unsigned i=0;i svec1; + {SimpTimer t("build sortedvec_set (opt.)"); + typename codeproject::sorted_vector::Cont& vec= svec1.get_container(); + for(unsigned i=0;i::iterator it= svec1.find(v[i]); + typename codeproject::sorted_vector::size_type nCount= svec1.count(v[i]); + assert( nCount==0 && it==svec1.end() + || nCount!=0 && it!=svec1.end()); + } + } + for(unsigned i=0;i +void TestMultiSet(std::vector& v) +{ + std::multiset svec; + + {SimpTimer t("build multiset"); + for(unsigned i=0;i::iterator it= svec.find(v[i]); + typename std::multiset::size_type nCount= svec.count(v[i]); + assert( nCount==0 && it==svec.end() + || nCount!=0 && it!=svec.end()); + } + } +} + +template +void TestSortedVector_AsMultiSet(std::vector& v) +{ + codeproject::sorted_vector svec; + {SimpTimer t("build sortedvec_multiset (naiv)"); + for(unsigned i=0;i svec1; + {SimpTimer t("build sortedvec_multiset (opt.)"); + typename codeproject::sorted_vector::Cont& vec= svec1.get_container(); + for(unsigned i=0;i::iterator it= svec1.find(v[i]); + typename codeproject::sorted_vector::size_type nCount= svec1.count(v[i]); + assert( nCount==0 && it==svec1.end() + || nCount!=0 && it!=svec1.end()); + } + } +/*test various functions*/ + const codeproject::sorted_vector svec2(svec); + assert(svec==svec2); + for(unsigned i=0;i svec3(v.begin(),v.end()); + assert(svec3==svec2); + codeproject::sorted_vector svec4(v.begin(),v.begin()+(v.end()-v.begin())/2); + svec4= svec3; + assert(svec4==svec3); + while(svec4.size()>0){ + svec4.pop_back(); + } +} + + + + +template +void ExecTests(std::vector& v) +{ + std::cout << "std::set versus 'sorted_vector as set'" << std::endl; + TestSet(v); + TestSortedVector_AsSet(v); + std::cout << "std::multiset versus 'sorted_vector as multiset'" << std::endl; + TestMultiSet(v); + TestSortedVector_AsMultiSet(v); +} + +template +void TestSetOperations(const std::vector& v0, + const std::vector& v1, + const std::vector& v2, + Pred pred) +{ +//A) compute the result of the set-operation: (v0-v1)+v2 - intersect(v1,v2) + codeproject::sorted_vector svec(v0.begin(),v0.end(),pred); + codeproject::sorted_vector svec_v1(pred); svec_v1= v1; + codeproject::sorted_vector svec_v2(pred); svec_v2= v2; + unsigned i,j; + for(i=0;i svec1(v0.begin(),v0.end(),pred); + for(unsigned k=0;k::size_type nSize= svec.size(); + typename codeproject::sorted_vector::size_type nSize1= svec1.size(); +//test whether results are the same + assert(svec==svec1); +} + + +codeproject::sorted_vector +BuildIntersection(std::vector& v0,std::vector& v1) +{ + codeproject::sorted_vector svec(v0.begin(),v0.end()); + codeproject::sorted_vector svecIntersection; + for(unsigned i=0;i +BuildIntersection1(std::vector& v0,std::vector& v1) +{ + codeproject::sorted_vector svec(v0.begin(),v0.end()); + codeproject::sorted_vector svecIntersection; + codeproject::sorted_vector::Cont& vInterSect= + svecIntersection.get_container(); + for(unsigned i=0;i A(a, a + N); + sorted_vector B(b, b + N); + sorted_vector C; + + cout << "Set A: "; + copy(A.begin(), A.end(), std::ostream_iterator(cout, " ")); + cout << endl; + cout << "Set B: "; + copy(B.begin(), B.end(), std::ostream_iterator(cout, " ")); + cout << endl; + + cout << "Union: "; + set_union(A.begin(), A.end(), B.begin(), B.end(), + std::ostream_iterator(cout, " "), + ltstr()); + cout << endl; + return 0; +} + +void TestAllSet() +{ + using namespace std; + using namespace codeproject; + typedef sorted_vector StrSet; + StrSet months; + months.insert("jan"); + months.insert("feb"); + months.insert("mar"); + months.insert("apr"); + months.insert("may"); + months.insert("jun"); + months.insert("jul"); + months.insert("aug"); + months.insert("sep"); + months.insert("oct"); + months.insert("nov"); + months.insert("dec"); + StrSet::iterator it= months.find("jul"); + assert(strcmp(*it,"jul")==0); + cout << "previous of jul (in alphabetical order) is " << (it[-1]) << endl; + cout << "next of jul (in alphabetical order) is " << (it[1]) << endl; + + cout << "months in alphabetical order: " << endl; + copy(months.begin(),months.end(),std::ostream_iterator(cout," ")); + cout << endl << "months in reverse alphabetical order: " << endl; + copy(months.rbegin(),months.rend(),std::ostream_iterator(cout," ")); + /*test count*/ + { + for(StrSet::iterator it= months.begin();it!=months.end();++it){ + assert(months.count(*it)==1); + } + } + /*test copy construction and comparison operators*/ + StrSet monthsCopy(months); + assert( months==monthsCopy + && months<=monthsCopy && months>=monthsCopy + && !(monthsmonthsCopy)); + + std::pair pairMismatch= + mismatch(months.begin(),months.end(),monthsCopy.begin()); + assert(pairMismatch.first==months.end() && pairMismatch.second==monthsCopy.end()); + + /*test insertion of already present element*/ + copy(months.begin(),months.end(),inserter(monthsCopy,monthsCopy.begin())); + assert(months.size()==monthsCopy.size()); + + /*test insert member functions*/ + months.insert(monthsCopy.begin(),monthsCopy.end()); + assert(months==monthsCopy); + StrSet months1(months.begin(),months.begin()+3); + months1.insert(months.begin()+1,months.end()); + assert(months1==months); + months1.insert("aug"); + months1.insert("xxx"); + months1.insert(months1.find("xxx"),"yyy"); + months1.insert("zzz"); + assert(months1>months && months1.size()==months.size()+3); + /*test erase member functions*/ + months1.erase(months1.find("xxx"),months1.end()); + assert(months1.size()==months.size()); + + /*test lower_bound,upper_bound,equal_range*/ + assert( strcmp(*months.lower_bound("jul"),"jul")==0); + + + cout << endl; +} + + +int main() +{ +//timed tests + std::vector v; + int i; + for(i=0;i<50000;i++){v.push_back(rand());} + std::cout << "--------------Tests with element type int-------------" << std::endl; + ExecTests(v); + + std::vector vt; + for(i=0;i<50000;i++){vt.push_back(MakeSTest());} + std::cout << "-Tests with element type 'STest' (string,int)--------" << std::endl; + ExecTests(v); + +//set operations-test + std::vector v1,v2; + for(i=0;i<10000;i++){v1.push_back(rand());} + for(i=0;i<10000;i++){v2.push_back(rand());} + TestSetOperations(v,v1,v2,std::greater()); + + assert(BuildIntersection(v1,v2)==BuildIntersection1(v1,v2)); + SGITest(); + TestAllSet(); + return 0; +} + diff --git a/sorted_vector.h b/sorted_vector.h index b02c0dc..234888e 100644 --- a/sorted_vector.h +++ b/sorted_vector.h @@ -1,301 +1,300 @@ -/* STL-conforming "sorted vector" container - * - * (C) 2002 Martin Holzherr (holzherr@infobrain.com). All rights reserved. - * - * Permission is granted to use, distribute and modify this code provided that: - * · this copyright notice appears, - * · - * The author welcomes any suggestions on the code or reportings of actual - * use of the code. Please send your comments to holzherr@infobrain.com. - * - * The author makes NO WARRANTY or representation, either express or implied, - * with respect to this code, its quality, accuracy, merchantability, or - * fitness for a particular purpose. This software is provided "AS IS", and - * you, its user, assume the entire risk as to its quality and accuracy. - * - * Created: November 19th, 2002 - * Last modified: November 27th, 2002 - (changed namespace from std to codeproject; - uses template member functions for MSCVER>=1300) - - */ - -#ifndef SORTED_VECTOR_ -#define SORTED_VECTOR_ -#define VERSION_SORTED_VECTOR_ 0x00010010 - - -#include -#include -#include -#include - -#pragma pack(push,8) -#pragma warning(push,3) - - -namespace codeproject{ - // TEMPLATE CLASS sorted_vector - - template, class A = std::allocator > - class sorted_vector { -public: - typedef sorted_vector Myt_; - typedef std::vector Cont; - typedef Cont::allocator_type allocator_type; - typedef Cont::size_type size_type; - typedef Cont::difference_type difference_type; - typedef Cont::reference reference; - typedef Cont::const_reference const_reference; - typedef Cont::value_type value_type; - typedef K key_type; - typedef Cont::iterator iterator; - typedef Cont::const_iterator const_iterator; - typedef Pr key_compare; - typedef Pr value_compare; - - typedef Cont::const_reverse_iterator - const_reverse_iterator; - typedef Cont::reverse_iterator reverse_iterator; - - typedef std::pair Pairii_; - typedef std::pair Paircc_; - typedef std::pair Pairib_; - explicit sorted_vector(const Pr& pred = Pr(),const A& al = A()) - :key_compare_(pred),vec_(al){} -#if (_MSC_VER >= 1300) - template - sorted_vector(It first, It beyond, - const Pr& pred = Pr(),const A& al = A()) - :key_compare_(pred),vec_(first,beyond,al) - {stable_sort();} -#else - sorted_vector(const_iterator first, const_iterator beyond, - const Pr& pred = Pr(),const A& al = A()) - :key_compare_(pred),vec_(first,beyond,al) - {stable_sort();} -#endif - sorted_vector(const Myt_& x) - : vec_(x.vec_),key_compare_(x.key_compare_) - {} - ~sorted_vector() {} - Myt_& operator=(const Myt_& x) {vec_.operator=(x.vec_); - key_compare_= x.key_compare_; - return *this;} - Myt_& operator=(const Cont& x){vec_.operator=(x); - sort();return *this;} - - void reserve(size_type n) {vec_.reserve(n);} - iterator begin() {return vec_.begin(); } - const_iterator begin() const {return vec_.begin(); } - iterator end() {return vec_.end();} - const_iterator end() const {return vec_.end();} - reverse_iterator rbegin() {return vec_.rbegin();} - const_reverse_iterator rbegin() const - {return vec_.rbegin();} - - reverse_iterator rend() {return vec_.rend();} - const_reverse_iterator rend() const - {return vec_.rend();} - - - size_type size() const {return vec_.size();} - size_type max_size() const {return vec_.max_size();} - bool empty() const {return vec_.empty();} - A get_allocator() const {return vec_.get_allocator();} - const_reference at(size_type p) const {return vec_.at(p);} - reference at(size_type p) {return vec_.at(p);} - const_reference operator[](size_type p) const - {return vec_.operator[](p);} - - reference operator[](size_type p) {return vec_.operator[](p);} - reference front() {return vec_.front();} - const_reference front() const {return vec_.front();} - reference back() {return vec_.back();} - const_reference back() const {return vec_.back();} - void pop_back() {vec_.pop_back();} - - void assign(const_iterator first, const_iterator beyond) - {vec_.assign(first,beyond);} - void assign(size_type n, const K& x = K()) - {vec_.assign(n,x);} -/*insert members*/ - Pairib_ insert(const value_type& x) - { - if(bNoDuplicates){ - iterator p= lower_bound(x); - if(p==end()||key_compare_(x,*p)){ - return Pairib_(InsertImpl_(p,x),true); - }else{ - return Pairib_(p,false); - } - }else{ - iterator p= upper_bound(x); - return Pairib_(InsertImpl_(p,x),true); - } - } - iterator insert(iterator it, const value_type& x)//it is the hint - { - if(it!=end() ){ - if(bNoDuplicates){ - if(key_compare_(*it,x)){ - if((it+1)==end()||KeyCompare_Gt_(*(it+1),x)){//use hint - return InsertImpl_(it+1,x); - }else if(KeyCompare_Geq_(*(it+1),x)){ - return end(); - } - } - }else{ - if( KeyCompare_Leq_(*it,x) - &&((it+1)==end()||KeyCompare_Geq_(*(it+1),x))){ - return InsertImpl_(it+1,x); - } - } - } - return insert(x).first; - } -#if (_MSC_VER >= 1300) - template - void insert(It first, It beyond) - { - size_type n= std::distance(first,beyond); - reserve(size()+n); - for( ;first!=beyond;++first){ - insert(*first); - } - } -#else - void insert(const_iterator first, const_iterator beyond) - { - size_type n= std::distance(first,beyond); - reserve(size()+n); - for( ;first!=beyond;++first){ - insert(*first); - } - } -#endif - iterator erase(iterator p) {return vec_.erase(p);} - iterator erase(iterator first, iterator beyond) - {return vec_.erase(first,beyond);} - size_type erase(const K& key) - { - Pairii_ begEnd= equal_range(key); - size_type n= std::distance(begEnd.first,begEnd.second); - erase(begEnd.first,begEnd.second); - return n; - } - void clear() {return vec_.clear();} - - bool Eq_(const Myt_& x) const - {return (size() == x.size() - && std::equal(begin(), end(), x.begin())); } - bool Lt_(const Myt_& x) const - {return (std::lexicographical_compare(begin(), end(), - x.begin(), x.end()));} - void swap(Myt_& x) - {vec_.swap(x.vec_);std::swap(key_compare_,x.key_compare_);} - - friend void swap(Myt_& x, Myt_& Y_) - {x.swap(Y_); } - - key_compare key_comp() const {return key_compare_; } - value_compare value_comp() const {return (key_comp()); } - iterator find(const K& k) - { iterator p = lower_bound(k); - return (p==end()||key_compare_(k, *p))? end():p; - } - const_iterator find(const K& k) const - {const_iterator p = lower_bound(k); - return (p==end()||key_compare_(k,*p))?end():p;} - size_type count(const K& k) const - {Paircc_ Ans_ = equal_range(k); - size_type n = std::distance(Ans_.first, Ans_.second); - return (n); } - iterator lower_bound(const K& k) - {return std::lower_bound(begin(), end(), k, key_compare_); } - const_iterator lower_bound(const K& k) const - {return std::lower_bound(begin(), end(), k, key_compare_); } - iterator upper_bound(const K& k) - {return std::upper_bound(begin(), end(), k, key_compare_); } - const_iterator upper_bound(const K& k) const - {return std::upper_bound(begin(), end(), k, key_compare_); } - Pairii_ equal_range(const K& k) - {return std::equal_range(begin(), end(), k, key_compare_); } - Paircc_ equal_range(const K& k) const - {return std::equal_range(begin(), end(), k, key_compare_); } - -/*functions for use with direct std::vector-access*/ - Cont& get_container() - {return vec_;} - void sort()//restore sorted order after low level access - { std::sort(vec_.begin(),vec_.end(),key_compare_); - if( bNoDuplicates ){ - vec_.erase(Unique_(),vec_.end()); - } - } - void stable_sort()//restore sorted order after low level access - { std::stable_sort(vec_.begin(),vec_.end(),key_compare_); - if( bNoDuplicates ){ - erase(Unique_(),end()); - } - } -protected: - iterator Unique_() - { iterator front_= vec_.begin(),out_= vec_.end(),end_=vec_.end(); - bool bCopy_= false; - for(iterator prev_; (prev_=front_)!=end_ && ++front_!=end_; ){ - if( key_compare_(*prev_,*front_)){ - if(bCopy_){ - *out_= *front_; - out_++; - } - }else{ - if(!bCopy_){out_=front_;bCopy_=true;} - } - } - return out_; - } - iterator InsertImpl_(iterator p,const value_type& x) - {return vec_.insert(p,x);} - bool KeyCompare_Leq_(const K& ty0,const K& ty1) - {return !key_compare_(ty1,ty0);} - bool KeyCompare_Geq_(const K& ty0,const K& ty1) - {return !key_compare_(ty0,ty1);} - bool KeyCompare_Gt_(const K& ty0,const K& ty1) - {return key_compare_(ty1,ty0);} - - key_compare key_compare_; - Cont vec_; -}; - - -template inline - bool operator==(const sorted_vector& x, - const sorted_vector& Y_) - {return x.Eq_(Y_); } -template inline - bool operator!=(const sorted_vector& x, - const sorted_vector& Y_) - {return !(x == Y_); } -template inline - bool operator<(const sorted_vector& x, - const sorted_vector& Y_) - {return x.Lt_(Y_);} -template inline - bool operator>(const sorted_vector& x, - const sorted_vector& Y_) - {return Y_ < x; } -template inline - bool operator<=(const sorted_vector& x, - const sorted_vector& Y_) - {return !(Y_ < x); } -template inline - bool operator>=(const sorted_vector& x, - const sorted_vector& Y_) - {return (!(x < Y_)); } -} -#pragma warning(pop) -#pragma pack(pop) -#elif VERSION_SORTED_VECTOR_ != 0x00010010 -#error You have included two sorted_vector.h with different version numbers -#endif +/* STL-conforming "sorted vector" container + * + * (C) 2002 Martin Holzherr (holzherr@infobrain.com). All rights reserved. + * + * Permission is granted to use, distribute and modify this code provided that: + * · this copyright notice appears, + * · + * The author welcomes any suggestions on the code or reportings of actual + * use of the code. Please send your comments to holzherr@infobrain.com. + * + * The author makes NO WARRANTY or representation, either express or implied, + * with respect to this code, its quality, accuracy, merchantability, or + * fitness for a particular purpose. This software is provided "AS IS", and + * you, its user, assume the entire risk as to its quality and accuracy. + * + * Created: November 19th, 2002 + * Last modified: November 27th, 2002 + (changed namespace from std to codeproject; + uses template member functions for MSCVER>=1300) + + */ + +#ifndef SORTED_VECTOR_ +#define SORTED_VECTOR_ +#define VERSION_SORTED_VECTOR_ 0x00010010 + + +#include +#include +#include +#include + +#pragma pack(push,8) +#pragma warning(push,3) + + +namespace codeproject{ + // TEMPLATE CLASS sorted_vector + + template, class A = std::allocator > + class sorted_vector { +public: + typedef sorted_vector Myt_; + typedef typename std::vector Cont; + typedef typename Cont::allocator_type allocator_type; + typedef typename Cont::size_type size_type; + typedef typename Cont::difference_type difference_type; + typedef typename Cont::reference reference; + typedef typename Cont::const_reference const_reference; + typedef typename Cont::value_type value_type; + typedef K key_type; + typedef typename Cont::iterator iterator; + typedef typename Cont::const_iterator const_iterator; + typedef Pr key_compare; + typedef Pr value_compare; + typedef typename Cont::const_reverse_iterator const_reverse_iterator; + typedef typename Cont::reverse_iterator reverse_iterator; + + typedef typename std::pair Pairii_; + typedef typename std::pair Paircc_; + typedef typename std::pair Pairib_; + + explicit sorted_vector(const Pr& pred = Pr(),const A& al = A()) + :key_compare_(pred),vec_(al){} +#if !(_MSC_VER >= 1300) + template + sorted_vector(It first, It beyond, + const Pr& pred = Pr(),const A& al = A()) + :key_compare_(pred),vec_(first,beyond,al) + {stable_sort();} +#else + sorted_vector(const_iterator first, const_iterator beyond, + const Pr& pred = Pr(),const A& al = A()) + :key_compare_(pred),vec_(first,beyond,al) + {stable_sort();} +#endif + sorted_vector(const Myt_& x) + : vec_(x.vec_),key_compare_(x.key_compare_) + {} + ~sorted_vector() {} + Myt_& operator=(const Myt_& x) {vec_.operator=(x.vec_); + key_compare_= x.key_compare_; + return *this;} + Myt_& operator=(const Cont& x){vec_.operator=(x); + sort();return *this;} + + void reserve(size_type n) {vec_.reserve(n);} + iterator begin() {return vec_.begin(); } + const_iterator begin() const {return vec_.begin(); } + iterator end() {return vec_.end();} + const_iterator end() const {return vec_.end();} + reverse_iterator rbegin() {return vec_.rbegin();} + const_reverse_iterator rbegin() const + {return vec_.rbegin();} + + reverse_iterator rend() {return vec_.rend();} + const_reverse_iterator rend() const + {return vec_.rend();} + + + size_type size() const {return vec_.size();} + size_type max_size() const {return vec_.max_size();} + bool empty() const {return vec_.empty();} + A get_allocator() const {return vec_.get_allocator();} + const_reference at(size_type p) const {return vec_.at(p);} + reference at(size_type p) {return vec_.at(p);} + const_reference operator[](size_type p) const + {return vec_.operator[](p);} + + reference operator[](size_type p) {return vec_.operator[](p);} + reference front() {return vec_.front();} + const_reference front() const {return vec_.front();} + reference back() {return vec_.back();} + const_reference back() const {return vec_.back();} + void pop_back() {vec_.pop_back();} + + void assign(const_iterator first, const_iterator beyond) + {vec_.assign(first,beyond);} + void assign(size_type n, const K& x = K()) + {vec_.assign(n,x);} +/*insert members*/ + Pairib_ insert(const value_type& x) + { + if(bNoDuplicates){ + iterator p= lower_bound(x); + if(p==end()||key_compare_(x,*p)){ + return Pairib_(InsertImpl_(p,x),true); + }else{ + return Pairib_(p,false); + } + }else{ + iterator p= upper_bound(x); + return Pairib_(InsertImpl_(p,x),true); + } + } + iterator insert(iterator it, const value_type& x)//it is the hint + { + if(it!=end() ){ + if(bNoDuplicates){ + if(key_compare_(*it,x)){ + if((it+1)==end()||KeyCompare_Gt_(*(it+1),x)){//use hint + return InsertImpl_(it+1,x); + }else if(KeyCompare_Geq_(*(it+1),x)){ + return end(); + } + } + }else{ + if( KeyCompare_Leq_(*it,x) + &&((it+1)==end()||KeyCompare_Geq_(*(it+1),x))){ + return InsertImpl_(it+1,x); + } + } + } + return insert(x).first; + } +#if (_MSC_VER >= 1300) + template + void insert(It first, It beyond) + { + size_type n= std::distance(first,beyond); + reserve(size()+n); + for( ;first!=beyond;++first){ + insert(*first); + } + } +#else + void insert(const_iterator first, const_iterator beyond) + { + size_type n= std::distance(first,beyond); + reserve(size()+n); + for( ;first!=beyond;++first){ + insert(*first); + } + } +#endif + iterator erase(iterator p) {return vec_.erase(p);} + iterator erase(iterator first, iterator beyond) + {return vec_.erase(first,beyond);} + size_type erase(const K& key) + { + Pairii_ begEnd= equal_range(key); + size_type n= std::distance(begEnd.first,begEnd.second); + erase(begEnd.first,begEnd.second); + return n; + } + void clear() {return vec_.clear();} + + bool Eq_(const Myt_& x) const + {return (size() == x.size() + && std::equal(begin(), end(), x.begin())); } + bool Lt_(const Myt_& x) const + {return (std::lexicographical_compare(begin(), end(), + x.begin(), x.end()));} + void swap(Myt_& x) + {vec_.swap(x.vec_);std::swap(key_compare_,x.key_compare_);} + + friend void swap(Myt_& x, Myt_& Y_) + {x.swap(Y_); } + + key_compare key_comp() const {return key_compare_; } + value_compare value_comp() const {return (key_comp()); } + iterator find(const K& k) + { iterator p = lower_bound(k); + return (p==end()||key_compare_(k, *p))? end():p; + } + const_iterator find(const K& k) const + {const_iterator p = lower_bound(k); + return (p==end()||key_compare_(k,*p))?end():p;} + size_type count(const K& k) const + {Paircc_ Ans_ = equal_range(k); + size_type n = std::distance(Ans_.first, Ans_.second); + return (n); } + iterator lower_bound(const K& k) + {return std::lower_bound(begin(), end(), k, key_compare_); } + const_iterator lower_bound(const K& k) const + {return std::lower_bound(begin(), end(), k, key_compare_); } + iterator upper_bound(const K& k) + {return std::upper_bound(begin(), end(), k, key_compare_); } + const_iterator upper_bound(const K& k) const + {return std::upper_bound(begin(), end(), k, key_compare_); } + Pairii_ equal_range(const K& k) + {return std::equal_range(begin(), end(), k, key_compare_); } + Paircc_ equal_range(const K& k) const + {return std::equal_range(begin(), end(), k, key_compare_); } + +/*functions for use with direct std::vector-access*/ + Cont& get_container() + {return vec_;} + void sort()//restore sorted order after low level access + { std::sort(vec_.begin(),vec_.end(),key_compare_); + if( bNoDuplicates ){ + vec_.erase(Unique_(),vec_.end()); + } + } + void stable_sort()//restore sorted order after low level access + { std::stable_sort(vec_.begin(),vec_.end(),key_compare_); + if( bNoDuplicates ){ + erase(Unique_(),end()); + } + } +protected: + iterator Unique_() + { iterator front_= vec_.begin(),out_= vec_.end(),end_=vec_.end(); + bool bCopy_= false; + for(iterator prev_; (prev_=front_)!=end_ && ++front_!=end_; ){ + if( key_compare_(*prev_,*front_)){ + if(bCopy_){ + *out_= *front_; + out_++; + } + }else{ + if(!bCopy_){out_=front_;bCopy_=true;} + } + } + return out_; + } + iterator InsertImpl_(iterator p,const value_type& x) + {return vec_.insert(p,x);} + bool KeyCompare_Leq_(const K& ty0,const K& ty1) + {return !key_compare_(ty1,ty0);} + bool KeyCompare_Geq_(const K& ty0,const K& ty1) + {return !key_compare_(ty0,ty1);} + bool KeyCompare_Gt_(const K& ty0,const K& ty1) + {return key_compare_(ty1,ty0);} + + key_compare key_compare_; + Cont vec_; +}; + + +template inline + bool operator==(const sorted_vector& x, + const sorted_vector& Y_) + {return x.Eq_(Y_); } +template inline + bool operator!=(const sorted_vector& x, + const sorted_vector& Y_) + {return !(x == Y_); } +template inline + bool operator<(const sorted_vector& x, + const sorted_vector& Y_) + {return x.Lt_(Y_);} +template inline + bool operator>(const sorted_vector& x, + const sorted_vector& Y_) + {return Y_ < x; } +template inline + bool operator<=(const sorted_vector& x, + const sorted_vector& Y_) + {return !(Y_ < x); } +template inline + bool operator>=(const sorted_vector& x, + const sorted_vector& Y_) + {return (!(x < Y_)); } +} +#pragma warning(pop) +#pragma pack(pop) +#elif VERSION_SORTED_VECTOR_ != 0x00010010 +#error You have included two sorted_vector.h with different version numbers +#endif -- 2.7.4