On Thu, Apr 9, 2009 at 10:19 AM, Kirk, Benjamin (JSC-EG311)
<[email protected]> wrote:
>
> Then there is the fact that the GlobalToLoalMap is derived from a
> std::map...
>
> std::map is very convenient for building up the list, but is not so
> efficient in terms of access or memory requirements.
>
> What I would suggest in this case and can take a hack at instead is that
> GlobalToLocalMap be derived from std::vector. It seems natural since the
> API provides a vector in the first place. we then just sort this vector and
> do the lookups with binary searches, which should smoke the map in terms of
> memory and access time performance.
Take a look at my attached pair_vector class. It's a vector of pairs
which remains unsorted/possibly contains duplicates during insertions.
(Insertion is O(1)) I've tested it and it uses less memory than
std::map. You just need to remember to sort() it before you try to
find() anything, and remember that it will happily insert duplicate
entries. Maybe it would be of use here?
--
John
// $Id: pair_vector.h 1117 2008-10-07 22:33:45Z peterson $
#ifndef __pair_vector_h__
#define __pair_vector_h__
#include <cstdlib> // std::abort
#include <vector>
#include <utility> // std::pair
#include <algorithm> // sort, unique
#include <iostream>
/**
* A version of unsorted_map which uses
* a single vector which contains <const Key, Value> pairs.
*
* @author John W. Peterson, 2008
*/
template <class Key, class Value>
class pair_vector
{
public:
pair_vector()
: require_unique(true),
_sorted(false)
{}
~pair_vector() {}
typedef std::vector<std::pair<Key, Value> > ContainerType;
typedef typename ContainerType::iterator iterator;
typedef typename ContainerType::const_iterator const_iterator;
typedef std::pair</*const*/Key, Value> value_type;
std::pair<iterator, bool> insert(const value_type& x)
{
_data.push_back(x);
// We just inserted something, so we're not sorted!
_sorted = false;
return std::make_pair((++_data.rbegin()).base(), true);
}
/**
* op[] insertion function
*/
Value& operator[](const Key& k)
{
return (*(this->insert(value_type(k, Value()))).first).second;
}
/**
* An object, which can be passed to STL routines, that compares
* the first entry in either pair.
*/
struct pair_less_than
{
bool operator() (const value_type& v1, const value_type& v2) const
{
return v1.first < v2.first;
}
bool operator() (const value_type& v1, const Key& k) const
{
return v1.first < k;
}
};
struct pair_equal
{
bool operator() (const value_type& v1, const value_type& v2) const
{
return v1.first == v2.first;
}
};
/**
* Finds an element whose key is k.
*/
iterator find(const Key& k) // const
{
if (!_sorted)
{
// We could sort for you, but chances are if you are calling find on an
// unsorted_map which has not been sorted, you could be writing bad
algorithms.
// So we throw an error.
std::cout << "Cannot find elements in an unsorted pair_vector. Call
sort() first!" << std::endl;
std::abort();
}
iterator result = std::lower_bound(this->begin(), this->end(), k,
pair_less_than());
// lower_bound can return the location where a value *would* be
// inserted if the actual value is not found. If that happens,
// then we return the end iterator.
return (result == this->end() || ( (*result).first > k) ) ? this->end() :
result;
}
/**
* Returns an iterator pointing to the beginning of the map.
*/
iterator begin()
{
return _data.begin();
}
/**
* Returns an iterator pointing to the end of the map.
*/
iterator end()
{
return _data.end();
}
/**
*
--------------------------------------------------------------------------------
* Additional interfaces not defined by std::map.
*
--------------------------------------------------------------------------------
*/
/**
* Returns the current _sorted flag. If true it means
* the map is currently sorted and searching is allowed.
* If false, the map is currently not sorted. Insertion
* into the map causes it to become unsorted.
*/
bool sorted() { return _sorted; }
/**
* Uses the ability of std::vector to reserve space in an attempt
* to reduce reallocations while building the container.
*/
void reserve(unsigned int n)
{
_data.reserve(n);
}
void sort()
{
if (!_sorted)
{
std::sort( _data.begin(), _data.end(), pair_less_than() );
// Remove duplicate entries?
if (require_unique)
{
// This is in keeping with the normal std::map but incurs
// additional O(N) expense... Therefore we have this as a
// user-selectable feature: sometimes we know we're going
// to insert unique values and we just want them to be
// quickly searchable...
iterator new_end = std::unique(this->begin(), this->end(),
pair_equal());
_data.erase(new_end, _data.end());
}
_sorted=true;
}
}
/**
* Do/do not require uniqueness while sorting
*/
bool require_unique;
private:
bool _sorted;
ContainerType _data;
/* Unimplemented */
pair_vector(const pair_vector& other);
pair_vector& operator=(const pair_vector& other);
};
#endif // #ifndef __pair_vector_h__
------------------------------------------------------------------------------
This SF.net email is sponsored by:
High Quality Requirements in a Collaborative Environment.
Download a free trial of Rational Requirements Composer Now!
http://p.sf.net/sfu/www-ibm-com
_______________________________________________
Libmesh-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/libmesh-devel
