#ifndef ASSOCIATIVE_H
#define ASSOCIATIVE_H
#include <algorithm>
#include <functional>
#include <iterator>
#include <stdexcept>
#include <type_traits>
#include <vector>
template<class iterator> auto structure_dereference_operator(const iterator& r) -> typename std::iterator_traits<iterator>::pointer {return r.operator->();}
template<class type> typename std::iterator_traits<type*>::pointer structure_dereference_operator(const type*& r) {return r;}
#pragma warning(push)
#pragma warning(disable : 4820) //warning C4820: 'associative<key_,mapped_>' : '3' bytes padding added after data member 'associative<key_,mapped_>::comp_'
//http://msdn.microsoft.com/en-us/library/xdayte4c.aspx
// carefully designed to also work on a linked list. Not that you should, because that would be silly.
template <class key_,
class mapped_,
class traits_ = std::less<key_>,
class undertype_ = std::vector<std::pair<key_,mapped_> >
>
class associative
{
public:
typedef traits_ key_compare;
typedef key_ key_type;
typedef mapped_ mapped_type;
typedef std::pair<const key_type, mapped_type> value_type;
typedef typename undertype_::allocator_type allocator_type;
typedef typename allocator_type::template rebind<value_type>::other value_allocator_type;
typedef typename undertype_::const_iterator const_iterator;
typedef typename value_allocator_type::const_pointer const_pointer;
typedef typename value_allocator_type::const_reference const_reference;
typedef typename undertype_::const_reverse_iterator const_reverse_iterator;
typedef typename value_allocator_type::difference_type difference_type;
typedef typename value_allocator_type::pointer pointer;
typedef typename value_allocator_type::reference reference;
typedef typename undertype_::size_type size_type;
static_assert(std::is_same<typename undertype_::value_type, std::pair<key_,mapped_> >::value, "container::value_type must be std::pair<key_,mapped_>");
static_assert(std::is_same<typename undertype_::reference, typename allocator_type::reference>::value, "container::reference must be allocator_type::reference");
static_assert(std::is_same<typename undertype_::pointer, typename allocator_type::pointer>::value, "container::pointer must be allocator_type::pointer");
class value_compare {
key_compare pred_;
public:
inline value_compare(key_compare pred=key_compare()) : pred_(pred) {}
inline bool operator()(const value_type& left, const value_type& right) const {return pred_(left.first,right.first);}
inline bool operator()(const value_type& left, const key_type& right) const {return pred_(left.first,right);}
inline bool operator()(const key_type& left, const value_type& right) const {return pred_(left,right.first);}
inline bool operator()(const key_type& left, const key_type& right) const {return pred_(left,right);}
inline key_compare key_comp( ) const {return pred_;}
};
class iterator {
public:
typedef typename value_allocator_type::difference_type difference_type;
typedef typename value_allocator_type::value_type value_type;
typedef typename value_allocator_type::reference reference;
typedef typename value_allocator_type::pointer pointer;
typedef std::bidirectional_iterator_tag iterator_category;
inline iterator() : data() {}
inline iterator(const iterator& rhs) : data(rhs.data) {}
inline iterator(const typename undertype_::iterator& rhs) : data(rhs) {}
inline iterator& operator=(const iterator& rhs) {data=rhs.data;}
inline iterator& operator=(const typename undertype_::iterator& rhs) {data=rhs;}
inline bool operator==(const iterator& rhs) const {return data==rhs.data;}
inline bool operator!=(const iterator& rhs) const {return data==rhs.data;}
inline iterator& operator++() {++data; return *this;}
inline iterator operator++(int) {return iterator(data++);}
inline iterator& operator--() {--data; return *this;}
inline iterator operator--(int) {return iterator(data--);}
inline reference operator*() const { return reinterpret_cast<reference>(*data);}
inline pointer operator->() const {return reinterpret_cast<pointer>(structure_dereference_operator(data));}
protected:
typename undertype_::iterator data;
};
typedef std::reverse_iterator<iterator> reverse_iterator;
inline associative() : internal_(), comp_() {}
explicit associative(const key_compare& traits) : internal_(), comp_(traits) {}
inline associative(const key_compare& traits, const allocator_type& allocator) :internal_(allocator), comp_(traits) {}
inline associative(const associative& rhs) : internal_(rhs.internal_), comp_(rhs.comp_) {}
inline associative(associative&& rhs) : internal_(std::move(rhs.internal_)), comp_(std::move(rhs.comp_)) {}
template<class input_iterator>
inline associative(input_iterator first, input_iterator last) : internal_(first, last), comp_()
{if (std::is_sorted(internal_.begin(), internal_.end())==false) std::sort(internal_.begin(), internal_.end(), comp_);}
template<class input_iterator>
inline associative(input_iterator first, input_iterator last, const key_compare& traits) : internal_(first, last, traits), comp_(traits)
{if (std::is_sorted(internal_.begin(), internal_.end())==false) std::sort(internal_.begin(), internal_.end(), comp_);}
template<class input_iterator>
inline associative(input_iterator first, input_iterator last, const key_compare& traits, const allocator_type& allocator) : internal_(first, last, allocator), comp_(traits)
{if (std::is_sorted(internal_.begin(), internal_.end())==false) std::sort(internal_.begin(), internal_.end(), comp_);}
inline ~associative() {}
inline associative& operator=(const associative& right){internal_=right.internal_; comp_=right.comp_;}
inline associative& operator=(associative&& right){internal_=std::move(right.internal_); comp_=std::move(right.comp_);}
inline const_iterator begin() const {return internal_.begin();}
inline iterator begin() {return internal_.begin();}
inline const_iterator cbegin() const {return internal_.cbegin();}
inline const_iterator end() const {return internal_.end();}
inline iterator end() {return internal_.end();}
inline const_iterator cend() const {return internal_.cend();}
inline const_reverse_iterator rbegin() const {return internal_.rbegin();}
inline reverse_iterator rbegin() {return internal_.rbegin();}
inline const_reverse_iterator crbegin() const {return internal_.crbegin();}
inline const_reverse_iterator rend() const {return internal_.rend();}
inline reverse_iterator rend() {return internal_.rend();}
inline const_reverse_iterator crend() const {return internal_.crend();}
inline std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const {return std::equal_range(internal_.begin(), internal_.end(), key, comp_);}
inline std::pair<iterator, iterator> equal_range(const key_type& key) {return std::equal_range(internal_.begin(), internal_.end(), key, comp_);}
inline iterator lower_bound(const key_type& key)
{return std::lower_bound(internal_.begin(), internal_.end(), key, comp_);}
inline const_iterator lower_bound(const key_type& key) const {return std::lower_bound(internal_.begin(), internal_.end(), key, comp_);}
inline iterator upper_bound(const key_type& key) {return std::upper_bound(internal_.begin(), internal_.end(), key, comp_);}
inline iterator upper_bound(const key_type& key, iterator lower) {
while(++lower!=internal_.end()&&comp_(key,lower->first))
;
return lower;
}
inline const_iterator upper_bound(const key_type& key) const {return std::upper_bound(internal_.begin(), internal_.end(), key, comp_);}
inline const_iterator upper_bound(const key_type& key, const_iterator lower) const {
while(++lower!=internal_.end()&&comp_(key,lower->first))
;
return lower;
}
mapped_type& at(const key_type& key) {
iterator i = internal_.lower_bound(key);
if (i == internal_.end() || comp_(i->first,key) || comp_(key, i->first))
throw std::out_of_range("invalid associative<K, T> key");
return i->second;
}
const mapped_type& at(const key_type& key) const{
iterator i = internal_.lower_bound(key);
if (i == internal_.end() || comp_(i->first,key) || comp_(key, i->first))
throw std::out_of_range("invalid associative<K, T> key");
return i->second;
}
inline size_type count(const key_type& key) const {
auto range = std::equal_range(internal_.begin(), internal_.end(), key, comp_);
return size_type(std::distance(range.first, range.second));
}
template<class rhs_type>
inline std::pair<iterator, bool> emplace(rhs_type&& rhs) {return emplace_(lower_bound(rhs.first), std::move(rhs));}
template<class rhs_type>
std::pair<iterator, bool> emplace_hint(const_iterator where, rhs_type&& rhs) {
if (where==internal_.end()) { return emplace_(lower_bound(rhs.first), std::move(rhs));}
if (comp_(where->first,rhs.first)) { return emplace_(lower_bound(rhs.first), std::move(rhs));}
const_iterator n=where;
++n;
if(n==internal_.end() || comp(n, rhs.first)) { return emplace_(lower_bound(rhs.first), std::move(rhs));}
return emplace_(where, std::move(rhs));
}
inline iterator erase(iterator where) {return internal_.erase(where);}
inline iterator erase(iterator first, iterator last) {return internal_.erase(first, last);}
inline size_type erase(const key_type& key) {auto r=count(key); internal_.erase(std::lower_bound(internal_.begin(), internal_.end(), key, comp_)); return r;}
template<class predicate>
inline iterator remove_if(predicate pred) {internal_.erase(std::remove_if(internal_.begin(),internal_.end(),pred), internal_.end());}
inline iterator find(const key_type& key) {return std::lower_bound(internal_.begin(), internal_.end(), key, comp_);}
inline const_iterator find(const key_type& key) const {return std::lower_bound(internal_.begin(), internal_.end(), key, comp_);}
inline std::pair<iterator, bool> insert(const value_type& rhs) {return insert_(lower_bound(rhs.first), rhs);}
iterator insert(const_iterator where, const value_type& rhs) {
if (where==internal_.end()) { return internal_.insert(lower_bound(rhs.first), rhs);}
if (comp_(where->first,rhs.first)) { return internal_.insert(lower_bound(rhs.first), rhs);}
const_iterator n=where;
++n;
if(n==internal_.end() || comp(n, rhs.first)) { return internal_.insert(lower_bound(rhs.first), rhs);}
return internal_.insert(where, rhs);
}
template<class input_iterator>
void insert(input_iterator first, input_iterator last) {
int s = internal_.size();
while(first!=last)
internal_.insert(internal_.end(),*(first++));
iterator mid(internal_.begin());
std::advance(mid, s);
std::inplace_merge(internal_.begin(), mid, internal_.end());
}
template<class rhs_type>
inline std::pair<iterator, bool> insert(rhs_type&& rhs) {return emplace_(lower_bound(rhs.first), std::move(rhs));}
template<class rhs_type>
inline iterator insert(const_iterator where, rhs_type&& rhs) {return emplace(where, std::move(rhs));}
inline mapped_type& operator[](const key_type& key) {return emplace(value_type(key, mapped_type())).first->second;}
inline mapped_type& operator[](const key_type&& key) {return emplace(value_type(std::move(key), mapped_type())).first->second;}
inline mapped_type& operator[](const key_type& key) const {return at(key);}
inline void clear() {internal_.clear();}
inline bool empty() const {return internal_.empty();}
inline size_type size( ) const {return internal_.size();}
inline void swap(associative& rhs) {internal_.swap(rhs.internal_); std::swap(comp_,rhs.comp_);}
inline friend void swap(associative& left, associative& right) {left.swap(right);}
inline allocator_type get_allocator() const {return internal_.get_allocator();}
inline key_compare key_comp() const{return comp_.key_comp();}
inline value_compare value_comp() const{return comp_;}
inline size_type max_size() const{return internal_.max_size();}
inline friend bool operator==(const associative& left, const associative& right) {return std::equal(left.internal_.begin(), left.internal_.end(), right.internal_.begin(), left.comp_);}
inline friend bool operator!=(const associative& left, const associative& right) {return !std::equal(left.internal_.begin(), left.internal_.end(), right.internal_.begin(), left.comp_);}
inline friend bool operator< (const associative& left, const associative& right) {return std::lexicographical_compare(left.internal_.begin(), left.internal_.end(), right.internal_.begin(), right.internal_.end(), left.comp_);}
inline friend bool operator<=(const associative& left, const associative& right) {return std::lexicographical_compare(right.internal_.begin(), right.internal_.end(), left.internal_.begin(), left.internal_.end(), left.comp_);}
inline friend bool operator> (const associative& left, const associative& right) {return !std::lexicographical_compare(right.internal_.begin(), right.internal_.end(), left.internal_.begin(), left.internal_.end(), left.comp_);}
inline friend bool operator>=(const associative& left, const associative& right) {return !std::lexicographical_compare(left.internal_.begin(), left.internal_.end(), right.internal_.begin(), right.internal_.end(), left.comp_);}
protected:
undertype_ internal_;
value_compare comp_;
template<class rhs_type>
std::pair<iterator,bool> emplace_(iterator where, rhs_type&& rhs) {
if (where==internal_.end())
return std::make_pair(internal_.emplace(where, std::move(rhs)), true);
if (comp_(*where, rhs))
return std::make_pair(where, true);
return std::make_pair(internal_.emplace(where, std::move(rhs)), true);
}
template<class rhs_type>
std::pair<iterator,bool> insert_(iterator where, const rhs_type& rhs) {
if (where==internal_.end())
return std::make_pair(internal_.insert(where, rhs), true);
if (comp_(*where, rhs))
return std::make_pair(where, true);
return std::make_pair(internal_.insert(where, rhs), true);
}
};
#pragma warning(pop)
namespace std {
template<class key_, class mapped_, class traits_, class undertype_>
inline void swap(associative <key_, mapped_, traits_, undertype_>& left, associative <key_, mapped_, traits_, undertype_>& right)
{left.swap(right);}
};
#endif //ASSOCIATIVE_H
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <string>
#include <vector>
#ifdef _DEBUG
#define WARMUP_TIME_MILLISECONDS 1
#define TEST_TIME_MILLISECONDS 9
#else
#define WARMUP_TIME_MILLISECONDS 10
#define TEST_TIME_MILLISECONDS 450
#endif
template<unsigned int size>
struct payload {
int data[size/4];
payload() {data[0]=rand();}
bool operator==(const payload& rhs) const {return data[0]==rhs.data[0];}
bool operator<(const payload& rhs) const {return data[0]<rhs.data[0];}
};
template<class payload, class container>
void test_internal(const std::vector<std::pair<payload, payload>>& data, const char* classname, const char* payloadname) {
clock_t beg,end,elapsed,freq;
unsigned int count=0;
bool timed=false;
freq = CLOCKS_PER_SEC;
std::vector<std::pair<payload, payload>> shuffled(data.begin(), data.end());
std::random_shuffle(shuffled.begin(), shuffled.end());
std::vector<std::pair<payload, payload>> sorted(data.begin(), data.end());
std::sort(sorted.begin(), sorted.end());
timed = false;
elapsed = 0;
std::cout << payloadname << ' ' << std::setw(4) << data.size() << ' ' << classname << ' ';
do {
beg = clock();
container a(data.begin(), data.end());
end = clock();
elapsed += end-beg;
if (elapsed>WARMUP_TIME_MILLISECONDS && !timed) {
elapsed =0;
count=0;
timed = true;
}
++count;
} while(elapsed<TEST_TIME_MILLISECONDS);
std::cout << std::setw(9) << count << ' ';
timed = false;
elapsed = 0;
{
container a(data.begin(), data.end());
do {
beg = clock();
auto i=a.find(shuffled[count%data.size()].first);
end = clock();
elapsed += end-beg;
if (elapsed>WARMUP_TIME_MILLISECONDS && !timed) {
elapsed =0;
count=0;
timed = true;
}
++count;
} while(elapsed<TEST_TIME_MILLISECONDS);
}
std::cout << std::setw(9) << count << ' ';
timed = false;
elapsed =0;
{
do {
container a(data.begin(), data.end());
beg = clock();
for(unsigned int i=0; i<shuffled.size(); ++i)
a.erase(shuffled[i].first);
end = clock();
elapsed += end-beg;
if (elapsed>WARMUP_TIME_MILLISECONDS && !timed) {
elapsed =0;
count=0;
timed = true;
}
++count;
} while(elapsed<TEST_TIME_MILLISECONDS);
}
std::cout << std::setw(9) << count << '\n';
}
template<class payload>
void test(const std::vector<std::pair<payload, payload>> &data, const char* payload_name) {
std::vector<std::pair<payload, payload>> use(data.begin(), data.begin()+8);
for( ; ; ) {
test_internal<payload, std::map <payload,payload>>(use, "std::map", payload_name);
test_internal<payload, associative<payload,payload,std::less<payload>,std::vector<std::pair<payload,payload>>>>(use, "astv/vec", payload_name);
if (use.size()<1024)
use.insert(use.end(), data.begin()+use.size()*1ull, data.begin()+use.size()*2ull);
else if (use.size() != data.size())
use.insert(use.end(), data.begin()+use.size(), data.end());
else break;
}
}
int main() {
typedef associative<char,char,std::less<char>,std::list<std::pair<char,char>>> compile_but_dont_use;
//std::vector<std::pair<std::string,std::string>> dynamic_data;
////dynamic_data.reserve(2000);
//{
// std::ifstream i("F:/Code/Contests/About53/2000words.txt");
// std::string line;
// for(;dynamic_data.size()<2000 && i>>line;)
// dynamic_data.push_back(std::make_pair(line, line));
// std::random_shuffle(dynamic_data.begin(), dynamic_data.end());
//}
std::cout << "bigger counts are best inserts lookups erases\n";
//test(dynamic_data, "std::string ");
//test(std::vector<std::pair<payload< 4>,payload< 4>>>(2000), "payload< 4>");
test(std::vector<std::pair<payload< 8>,payload< 8>>>(2000), "payload< 8>");
test(std::vector<std::pair<payload< 16>,payload< 16>>>(2000), "payload< 16>");
test(std::vector<std::pair<payload< 32>,payload< 32>>>(2000), "payload< 32>");
test(std::vector<std::pair<payload< 64>,payload< 64>>>(2000), "payload< 64>");
test(std::vector<std::pair<payload<128>,payload<128>>>(2000), "payload<128>");
return 0;
}