69 lines
2.1 KiB
C++
69 lines
2.1 KiB
C++
#pragma once
|
|
|
|
|
|
#include <assert.h>
|
|
//#include <vector>
|
|
#include <algorithm>
|
|
#include <utility>
|
|
#include <functional>
|
|
|
|
|
|
template <class T, class pred = std::less<T> >
|
|
class KSortVector
|
|
{
|
|
public:
|
|
void insert( const T& value )
|
|
{
|
|
std::vector<T>::iterator it = std::lower_bound( m_vector.begin(), m_vector.end(), value, pred() );
|
|
m_vector.insert( it, value );
|
|
}
|
|
|
|
int search_index( const T& value ) const
|
|
{
|
|
std::vector<T>::const_iterator it = std::lower_bound( m_vector.begin(), m_vector.end(), value, pred() );
|
|
if ( it == m_vector.end() ) return -1;
|
|
if ( pred()( value, *it ) ) return -1;
|
|
int idx = int( it - m_vector.begin() );
|
|
return idx;
|
|
}
|
|
|
|
std::pair<bool,T*> search_or_insert( const T& value )
|
|
{
|
|
std::vector<T>::iterator it = std::lower_bound( m_vector.begin(), m_vector.end(), value, pred() );
|
|
bool bInserted = (it == m_vector.end()) ? true : pred()( value, *it );
|
|
int index = it - m_vector.begin();
|
|
if ( bInserted )
|
|
m_vector.insert( it, value );
|
|
return std::pair<bool,T*>( bInserted, &m_vector[ index ] );
|
|
}
|
|
|
|
typename std::vector<T>::const_iterator begin() const { return m_vector.begin(); }
|
|
typename std::vector<T>::const_iterator end() const { return m_vector.end(); }
|
|
typename std::vector<T>::iterator begin() { return m_vector.begin(); }
|
|
typename std::vector<T>::iterator end() { return m_vector.end(); }
|
|
|
|
typedef typename std::vector<T>::iterator iterator ;
|
|
typedef typename std::vector<T>::const_iterator const_iterator ;
|
|
|
|
void erase( int idx ) { m_vector.erase( m_vector.begin() + idx ); }
|
|
void erase( const T& value )
|
|
{
|
|
int idx = search_index( value );
|
|
assert( idx != -1 );
|
|
if ( idx == -1 ) return;
|
|
m_vector.erase( m_vector.begin() + idx );
|
|
}
|
|
void clear() { m_vector.clear(); }
|
|
|
|
bool has( const T& value ) const { return search_index( value ) != -1; }
|
|
|
|
const T& at( int idx ) const { return m_vector[idx]; }
|
|
const T& operator[] ( int idx ) const { return m_vector[idx]; }
|
|
int size() const { return (int)m_vector.size(); }
|
|
bool empty() const { return m_vector.empty(); }
|
|
T& front() { return m_vector.front(); }
|
|
|
|
private:
|
|
std::vector<T> m_vector;
|
|
};
|