Re: index of std::vector with condition
* Stuart Golodetz, on 13.07.2010 01:53:
Philipp Kraus wrote:
Hello,
is there a fast way to create a index with condition of a std::vector?
For illustrating:
I have a vector mydata with some data and I would like to create a
vector with unique elements
std::vector<T> l_unique( mydata );
std::sort( l_unique.begin(), l_unique.end() );
l_unique.erase( std::unique( l_unique.begin(), l_unique.end()),
l_unique.end() );
in the next step I will do this
std::vector< std::vector<std::size:t> > index;
for(std::size_t i=0; i < l_unique.size(); ++i) {
std::vector<std::size_t> y;
for(std::size_t n=0; n < mydata.size(); ++n)
if (mydata[n] == l_unique[i])
y.push_back(n);
index.push_back(y);
}
Can I do this two for loops more efficient? I would like to get the
index position in my data vector from a unique set of the elements
within the vector.
Thanks for help
Phil
Anything wrong with this sort of approach?
int arr[] = {3,2,2,3,3,1,1,5,6};
std::vector<int> v(&arr[0], &arr[sizeof(arr)/sizeof(int)]);
std::map<int,std::vector<size_t> > index;
for(size_t i=0, size=v.size(); i<size; ++i)
{
index[v[i]].push_back(i);
}
Yes, it accesses non-existing elements of 'index'.
One reasonable way to build an index is as follows:
<code>
#include <iostream>
#include <map>
#include <algorithm>
#include <stddef.h>
typedef ptrdiff_t Size;
typedef ptrdiff_t Index;
template< class Type, Size n >
Size size( Type (&)[n] ) { return n; }
int main()
{
typedef std::multimap< int, Index > Map;
typedef Map::value_type MapValue;
typedef Map::iterator MapIter;
int const arr[] = { 3,2,2,3,3,1,1,5,6 };
Map map;
for( Index i = 0; i < size( arr ); ++i )
{
map.insert( MapValue( arr[i], i ) );
}
for( MapIter it = map.begin(); it != map.end(); ++it )
{
std::cout << it->first << " -> " << it->second << std::endl;
}
std::cout << std::endl;
std::cout << "All occurrences of 3:" << std::endl;
for( MapIter it = map.lower_bound( 3 ); it != map.upper_bound( 3 ); ++it )
{
std::cout << it->second << " ";
}
std::cout << std::endl;
}
</code>
The general idea is sorting the original data set. In the code above the sorting
is done externally by insertion into a tree (inside 'map'). Alternatively it can
be done in-place by applying e.g. std::sort.
Cheers & hth.,
- Alf
--
blog at <url: http://alfps.wordpress.com>