STL
http://community.webreview.com/cpp/184406243 custom STL allocator
http://google-sparsehash.googlecode.com/svn/trunk/doc/index.html google's hash_map
http://code.google.com/p/google-sparsehash/
http://code.google.com/p/google-perftools/ performance tools
STL performance: http://www.artima.com/cppsource/lazy_builder.html
set and map are generally implemented as b inary trees. The other option is to use hash tables, and while they are not part of the STL yet, many implementation offer hashed sets and maps. The advantage of hashing is that it provides potentially better performance than a binary tree.
If frequent insertions and deletions are likely but the data does not need to be sorted by a key, the data can be put in a list. If constant-time lookup is a requirement, they can be put in a hash map instead
std::set is the efficient container when insertions are common, although lookup speed
is slower than for vector.
You can find the place to insert in sorted container using
std::lower_bound (O(log n)), but for <vector> inserting the element is (O(n))
http://www.codeproject.com/KB/stl/sorted_vector.aspx - sorted vector
http://www.codeproject.com/KB/stl/setandmap.aspx :
struct gtstr
{
bool operator()(const string& s1, const string& s2) const
{
return (s1 > s2);
}
};
now in our main function:
set<char gtstr*,> setString2;
setString2.insert("this");
setString2.insert("is");
setString2.insert("a");
setString2.insert("test");
setString2.insert("boys");
vector<wstring> split(const wstring &s,const wstring &delimeter)
{
wstring str=s;
int dl=delimeter.size();
int pos;
vector<wstring> result;
while( (pos=str.find(delimeter)) >-1 )
{
result.push_back(str.substr(0,pos));
str=str.substr(pos+dl);
}
result.push_back(str);
return result;
}
five categories of iterators:
input iterators
output iterators
forward iterators
bidirectional iterators
random access
The simplest solution is to have a collection of pointers:
vector<Base*> v;
v.push_back(new Base); // OK
v.push_back(new Derived); // OK too
// cleanup:
for (vector<Base*>::iterator i = v.begin(); i != v.end(); ++i)
delete *i;
The problem with this solution is that after you're done with the container, you need to manually cleanup the objects stored in it. This is both error prone and not exception safe.
Smart pointers are a possible solution, as illustrated below. (An alternative solution is a smart container, like the one implemented in pointainer.h.)
vector< linked_ptr<Base> > v;
v.push_back(new Base); // OK
v.push_back(new Derived); // OK too
// cleanup is automatic
Since the smart pointer automatically cleans up after itself, there is no need to manually delete the pointed objects. Note: STL containers may copy and delete their elements behind the scenes (for example, when they resize themselves). Therefore, all copies of an element must be equivalent, or the wrong copy may be the one to survive all this copying and deleting. This means that some smart pointers cannot be used within STL containers, specifically the standard auto_ptr and any ownership-transferring pointer.
template<typename T>
void removeDuplicates(std::vector<T>& vec)
{
std::sort(vec.begin(), vec.end());
vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
}
Important: Do you have operator< and operator== defined for your class T? Those two would be needed. operator< for std::sort and operator== for std::unique.
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
int getMaxInt(vector<int>& v) { return *max_element(v.begin( ), v.end( )); }
int getMinInt(vector<int>& v) { return *min_element(v.begin( ), v.end( )); }
int main( ) {
vector<int> v;
for (int i=10; i < 20; ++i) v.push_back(i);
cout << "min integer = " << getMinInt(v) << endl;
cout << "max integer = " << getMaxInt(v) << endl;
}
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
template<class Iter_T, class Value_T>
void computeMinAndMax(Iter_T first, Iter_T last, Value_T& min, Value_T& max) {
min = *min_element(first, last);
max = *max_element(first, last);
}
int main( ) {
vector<int> v;
for (int i=10; i < 20; ++i) v.push_back(i);
int min = -1;
int max = -1;
computeMinAndMax(v.begin( ), v.end( ), min, max);
cout << "min integer = " << min << endl;
cout << "max integer = " << max << endl;
}
The min_element and max_element functions work by using operator< to compare the values referenced
by the iterators. This means that if an iterator does not reference a type that supports comparison
through the less-than operator, a compiler error will result.
The min_element and max_element functions, however, can be used with a user-defined comparison functor,
i.e., a function pointer or a function object.
Finding the maximum element for user-defined types
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
struct ChessPlayer {
ChessPlayer(const char* name, int rating)
: name_(name), rating_(rating)
{ }
const char* name_;
int rating_;
};
struct IsWeakerPlayer {
bool operator( )(const ChessPlayer& x, const ChessPlayer& y) {
return x.rating_ < y.rating_;
}
};
int main( )
{
ChessPlayer kasparov("Garry Kasparov", 2805);
ChessPlayer anand("Viswanathan Anand ", 2788);
ChessPlayer topalov("Veselin Topalov", 2788);
vector<ChessPlayer> v;
v.push_back(kasparov);
v.push_back(anand);
v.push_back(topalov);
cout << "the best player is ";
cout << max_element(v.begin( ), v.end( ), IsWeakerPlayer( ))->name_;
cout << endl;
}
#include <algorithm>
#include <vector>
#include <iostream>
#include <iterator>
using namespace std;
struct OutOfRange
{
OutOfRange(int min, int max): min_(min), max_(max)
{ }
bool operator( )(int x) {
return (x < min_) || (x > max_);
}
int min_;
int max_;
};
int main( )
{
vector<int> v;
v.push_back(6);
v.push_back(12);
v.push_back(18);
v.push_back(24);
v.push_back(30);
remove_copy_if(v.begin( ), v.end( ),
ostream_iterator<int>(cout, "\n"), OutOfRange(10,25));
}
The C++ standard provides the C runtime function rand in the <cstdlib> header
that returns a random number in the range of 0 to RAND_MAX inclusive.
The RAND_MAX macro represents the highest value returnable by the rand function.
#include <cstdlib>
#include <ctime>
#include <iostream>
using namespace std;
double doubleRand( ) {
return double(rand( )) / (double(RAND_MAX) + 1.0);
}
int main( ) {
srand(static_cast<unsigned int>(clock( )));
cout << "expect 5 numbers within the interval [0.0, 1.0)" << endl;
for (int i=0; i < 5; i++) {
cout << doubleRand( ) << "\n";
}
cout << endl;
}
Before using the rand function you need to seed the random number generator with a call to srand.
This assures that subsequent calls to rand won't produce the same sequence of numbers each time
the program is run. The simplest way to seed the random number generator is to pass the result
from a call to clock from the <ctime> header as an unsigned int.
Reseeding a random number generator causes number generation to be less random.
The rand function is limited in many ways:
- it only generates integers, and only does so using a uniform distribution;
- the specific random number generation algorithm used is implementation specific and,
thus, random number sequences are not reproducible from system to system given the same seed.
This is a problem for certain kinds of applications, as well as when testing and debugging.
A much more sophisticated alternative to rand is the Boost Random library by Jens Maurer that has inspired the random number facilities proposed for TR1.
The Boost Random library provides several high-quality random number generation functions for both integer and floating-point types, and support for numerous kinds of distributions.
#include <boost/random.hpp>
#include <iostream>
#include <cstdlib>
using namespace std;
using namespace boost;
typedef boost::mt19937 BaseGenerator;
typedef boost::uniform_real<double> Distribution;
typedef boost::variate_generator<BaseGenerator, Distribution> Generator;
double boostDoubleRand( ) {
static BaseGenerator base;
static Distribution dist;
static Generator rng(base, dist);
return rng( );
}
int main( ) {
cout << "expect 5 numbers within the interval [0,1)" << endl;
for (int i=0; i < 5; i++) {
cout << boostDoubleRand( ) << "\n";
}
cout << endl;
}
You can use either the generate or generate_n functions from the <algorithm> header
with a functor that returns random numbers.
#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream>
#include <cstdlib>
using namespace std;
struct RndIntGen
{
RndIntGen(int l, int h)
: low(l), high(h)
{ }
int operator( )( ) const {
return low + (rand( ) % ((high - low) + 1));
}
private:
int low;
int high;
};
int main( ) {
srand(static_cast<unsigned int>(clock( )));
vector<int> v(5);
generate(v.begin( ), v.end( ), RndIntGen(1, 6));
copy(v.begin( ), v.end( ), ostream_iterator<int>(cout, "\n"));
}
The standard C++ library provides the functions generate and generate_n specifically for filling
containers with the result of a generator function. These functions accept a nullary functor
(a function pointer or function object with no arguments) whose result is assigned to contiguous
values in the container. Sample implementations of the generate and generate_n functions are shown here:
template<class Iter_T, class Fxn_T>
void generate(Iter_T first, Iter_T last, Fxn_T f) {
while (first != last) *first++ = f( );
}
template<class Iter_T, class Fxn_T>
void generate_n(Iter_T first, int n, Fxn_T f) {
for (int i=0; i < n; ++i) *first++ = f( );
}
#include <iostream>
#include <complex>
#include <cmath>
#include <iterator>
using namespace std;
unsigned int bitReverse(unsigned int x, int log2n) {
int n = 0;
int mask = 0x1;
for (int i=0; i < log2n; i++) {
n <<= 1;
n |= (x & 1);
x >>= 1;
}
return n;
}
const double PI = 3.1415926536;
template<class Iter_T>
void fft(Iter_T a, Iter_T b, int log2n)
{
typedef typename iterator_traits<Iter_T>::value_type complex;
const complex J(0, 1);
int n = 1 << log2n;
for (unsigned int i=0; i < n; ++i) {
b[bitReverse(i, log2n)] = a[i];
}
for (int s = 1; s <= log2n; ++s) {
int m = 1 << s;
int m2 = m >> 1;
complex w(1, 0);
complex wm = exp(-J * (PI / m2));
for (int j=0; j < m2; ++j) {
for (int k=j; k < n; k += m) {
complex t = w * b[k + m2];
complex u = b[k];
b[k] = u + t;
b[k + m2] = u - t;
}
w *= wm;
}
}
}
int main( ) {
typedef complex<double> cx;
cx a[] = { cx(0,0), cx(1,1), cx(3,3), cx(4,4),
cx(4, 4), cx(3, 3), cx(1,1), cx(0,0) };
cx b[8];
fft(a, b, 3);
for (int i=0; i<8; ++i)
cout << b[i] << "\n";
}
The program above produces the following output:
(16,16)
(-4.82843,-11.6569)
(0,0)
(-0.343146,0.828427)
(0,0)
(0.828427,-0.343146)
(0,0)
(-11.6569,-4.82843)