unordered_test.cpp

stl的源码

  CPPUNIT_ASSERT( bucketSizes == int_uset.size() );
#endif
}

void UnorderedTest::equal_range()
{
#if defined (STLPORT)
  typedef unordered_multiset<size_t> umset;
  {
    //General test
    umset iumset;
    iumset.max_load_factor(10.0f);

    size_t nbBuckets = iumset.bucket_count();

    for (size_t i = 0; i < nbBuckets; ++i) {
      iumset.insert(i);
      iumset.insert(i + nbBuckets);
      iumset.insert(i + 2 * nbBuckets);
      iumset.insert(i + 3 * nbBuckets);
      iumset.insert(i + 4 * nbBuckets);
    }

    CPPUNIT_ASSERT( nbBuckets == iumset.bucket_count() );
    CPPUNIT_ASSERT( iumset.size() == 5 * nbBuckets );

    pair<umset::iterator, umset::iterator> p = iumset.equal_range(1);
    CPPUNIT_ASSERT( p.first != p.second );

    size_t nbElems = iumset.size();
    nbElems -= distance(p.first, p.second);
    for (umset::iterator j = p.first; j != p.second;) {
      iumset.erase(j++);
    }

    CPPUNIT_ASSERT( nbElems == iumset.size() );

    p = iumset.equal_range(2);
    CPPUNIT_ASSERT( p.first != p.second );
    nbElems -= distance(p.first, p.second);
    iumset.erase(p.first, p.second);
    CPPUNIT_ASSERT( nbElems == iumset.size() );
  }

  {
    //More specific test that tries to put many values in the same bucket
    umset iumset;

    size_t i;
    //We are going to add at least 20 values, to get a stable hash container while doing that
    //we force a large number of buckets:
    iumset.rehash(193);

    size_t nbBuckets = iumset.bucket_count();
    const size_t targetedBucket = nbBuckets / 2;

    //Lets put 10 values in the targeted bucket:
    for (i = 0; i < 10; ++i) {
      iumset.insert(targetedBucket + (i * nbBuckets));
    }

    //We put again 10 values in the targeted bucket and in reverse order:
    for (i = 9; i <= 10; --i) {
      iumset.insert(targetedBucket + (i * nbBuckets));
    }

    //Now we put some more elements until hash container is resized:
    i = 0;
    while (iumset.bucket_count() == nbBuckets) {
      iumset.insert(i++);
    }

    //CPPUNIT_ASSERT( iumset.bucket_size(targetedBucket) == 21 );

    pair<umset::iterator, umset::iterator> p = iumset.equal_range(targetedBucket);
    CPPUNIT_ASSERT( p.first != p.second );
    CPPUNIT_ASSERT( distance(p.first, p.second) == 3 );

    // Now we remove some elements until hash container is resized:
    nbBuckets = iumset.bucket_count();
    while (iumset.bucket_count() == nbBuckets &&
           !iumset.empty()) {
      iumset.erase(iumset.begin());
    }
    CPPUNIT_ASSERT( iumset.load_factor() <= iumset.max_load_factor() );

    // Adding an element back shouldn't change number of buckets:
    nbBuckets = iumset.bucket_count();
    iumset.insert(0);
    CPPUNIT_ASSERT( iumset.bucket_count() == nbBuckets );
  }

  {
    srand(0);
    for (int runs = 0; runs < 2; ++runs) {
      size_t magic = rand();
      umset hum;
      size_t c = 0;
      for (int i = 0; i < 10000; ++i) {
        if ((rand() % 500) == 0) {
          hum.insert(magic);
          ++c;
        }
        else {
          size_t r;
          while ((r = rand()) == magic)
            ;
          hum.insert(r);
        }

        /*
        if ((float)(hum.size() + 1) / (float)hum.bucket_count() > hum.max_load_factor()) {
          cout << "Hash container dump: Nb elems: " << hum.size() << ", Nb buckets: " << hum.bucket_count() << "\n";
          for (size_t b = 0; b < hum.bucket_count(); ++b) {
            if (hum.bucket_size(b) != 0) {
              umset::local_iterator litBegin(hum.begin(b)), litEnd(hum.end(b));
              cout << "B" << b << ": ";
              for (umset::local_iterator lit = litBegin; lit != litEnd; ++lit) {
                if (lit != litBegin) {
                  cout << " - ";
                }
                cout << *lit;
              }
              cout << "\n";
            }
          }
          cout << endl;
        }
        */
      }
      CPPUNIT_ASSERT( hum.count(magic) == c );
    }
  }
#endif
}

void UnorderedTest::benchmark1()
{
#if defined (STLPORT)
  typedef unordered_multiset<size_t> umset;

  const size_t target = 500000;
  umset iumset;
  iumset.max_load_factor(10);
  size_t i;
  for (i = 0; i < target; ++i) {
    iumset.insert(i);
  }

  for (i = 0; i < target; ++i) {
    iumset.erase(i);
  }
#endif
}

void UnorderedTest::benchmark2()
{
#if defined (STLPORT)
  typedef unordered_multiset<size_t> umset;

  const size_t target = 500000;
  umset iumset;
  iumset.max_load_factor(10);
  size_t i;
  for (i = 0; i < target; ++i) {
    iumset.insert(target - i);
  }

  for (i = 0; i < target; ++i) {
    iumset.erase(target - i);
  }
#endif
}

struct Key
{
  Key() : m_data(0) {}
  explicit Key(int data) : m_data(data) {}

  int m_data;

#if defined (__DMC__) // slist<_Tp,_Alloc>::remove error
  bool operator==(const Key&) const;
#endif
};

struct KeyHash
{
  size_t operator () (Key key) const
  { return (size_t)key.m_data; }

  size_t operator () (int data) const
  { return (size_t)data; }
};

struct KeyEqual
{
  bool operator () (Key lhs, Key rhs) const
  { return lhs.m_data == rhs.m_data; }

  bool operator () (Key lhs, int rhs) const
  { return lhs.m_data == rhs; }

  bool operator () (int lhs, Key rhs) const
  { return lhs == rhs.m_data; }
};

struct KeyHashPtr
{
  size_t operator () (Key const volatile *key) const
  { return (size_t)key->m_data; }

  size_t operator () (int data) const
  { return (size_t)data; }
};

struct KeyEqualPtr
{
  bool operator () (Key const volatile *lhs, Key const volatile *rhs) const
  { return lhs->m_data == rhs->m_data; }

  bool operator () (Key const volatile *lhs, int rhs) const
  { return lhs->m_data == rhs; }

  bool operator () (int lhs, Key const volatile *rhs) const
  { return lhs == rhs->m_data; }
};

void UnorderedTest::template_methods()
{
#if defined (STLPORT) && defined (_STLP_USE_CONTAINERS_EXTENSION)
  {
    typedef unordered_set<Key, KeyHash, KeyEqual> Container;
    Container cont;
    cont.insert(Key(1));
    cont.insert(Key(2));
    cont.insert(Key(3));
    cont.insert(Key(4));

    CPPUNIT_ASSERT( cont.count(Key(1)) == 1 );
    CPPUNIT_ASSERT( cont.count(1) == 1 );
    CPPUNIT_ASSERT( cont.count(5) == 0 );

    CPPUNIT_ASSERT( cont.find(2) != cont.end() );
    CPPUNIT_ASSERT( cont.equal_range(2) != make_pair(cont.begin(), cont.end()) );

    Container const& ccont = cont;
    CPPUNIT_ASSERT( ccont.find(2) != ccont.end() );
    CPPUNIT_ASSERT( ccont.bucket(2) == ccont.bucket(2) );
    CPPUNIT_ASSERT( ccont.equal_range(2) != make_pair(ccont.begin(), ccont.end()) );
  }

  {
    typedef unordered_set<Key*, KeyHashPtr, KeyEqualPtr> Container;
    Container cont;
    Key key1(1), key2(2), key3(3), key4(4);
    cont.insert(&key1);
    cont.insert(&key2);
    cont.insert(&key3);
    cont.insert(&key4);

    CPPUNIT_ASSERT( cont.count(1) == 1 );
    CPPUNIT_ASSERT( cont.count(5) == 0 );

    CPPUNIT_ASSERT( cont.find(2) != cont.end() );
    CPPUNIT_ASSERT( cont.equal_range(2) != make_pair(cont.begin(), cont.end()) );

    Container const& ccont = cont;
    CPPUNIT_ASSERT( ccont.find(2) != ccont.end() );
    CPPUNIT_ASSERT( ccont.bucket(2) == ccont.bucket(2) );
    CPPUNIT_ASSERT( ccont.equal_range(2) != make_pair(ccont.begin(), ccont.end()) );
  }
  {
    typedef unordered_multiset<Key, KeyHash, KeyEqual> Container;
    Container cont;
    cont.insert(Key(1));
    cont.insert(Key(2));
    cont.insert(Key(1));
    cont.insert(Key(2));

    CPPUNIT_ASSERT( cont.count(Key(1)) == 2 );
    CPPUNIT_ASSERT( cont.count(1) == 2 );
    CPPUNIT_ASSERT( cont.count(5) == 0 );

    CPPUNIT_ASSERT( cont.find(2) != cont.end() );
    CPPUNIT_ASSERT( cont.equal_range(1) != make_pair(cont.end(), cont.end()) );

    Container const& ccont = cont;
    CPPUNIT_ASSERT( ccont.find(2) != ccont.end() );
    CPPUNIT_ASSERT( ccont.bucket(2) == ccont.bucket(2) );
    CPPUNIT_ASSERT( ccont.equal_range(2) != make_pair(ccont.end(), ccont.end()) );
  }

  {
    typedef unordered_multiset<Key const volatile*, KeyHashPtr, KeyEqualPtr> Container;
    Container cont;
    Key key1(1), key2(2), key3(3), key4(4);
    cont.insert(&key1);
    cont.insert(&key2);
    cont.insert(&key3);
    cont.insert(&key4);

    CPPUNIT_ASSERT( cont.count(1) == 1 );
    CPPUNIT_ASSERT( cont.count(5) == 0 );

    CPPUNIT_ASSERT( cont.find(2) != cont.end() );
    CPPUNIT_ASSERT( cont.equal_range(2) != make_pair(cont.begin(), cont.end()) );

    Container const& ccont = cont;
    CPPUNIT_ASSERT( ccont.find(2) != ccont.end() );
    CPPUNIT_ASSERT( ccont.bucket(2) == ccont.bucket(2) );
    CPPUNIT_ASSERT( ccont.equal_range(2) != make_pair(ccont.begin(), ccont.end()) );
  }
#endif
}

#if defined (STLPORT) && \
    (!defined (_STLP_USE_PTR_SPECIALIZATIONS) || defined (_STLP_CLASS_PARTIAL_SPECIALIZATION))
#  if !defined (__DMC__)
/* Simple compilation test: Check that nested types like iterator
 * can be access even if type used to instanciate container is not
 * yet completely defined.
 */
class IncompleteClass
{
  unordered_set<IncompleteClass> usinstances;
  typedef unordered_set<IncompleteClass>::iterator usit;
  unordered_multiset<IncompleteClass> usminstances;
  typedef unordered_multiset<IncompleteClass>::iterator usmit;

  unordered_map<IncompleteClass, IncompleteClass> uminstances;
  typedef unordered_map<IncompleteClass, IncompleteClass>::iterator umit;
  unordered_multimap<IncompleteClass, IncompleteClass> umminstances;
  typedef unordered_multimap<IncompleteClass, IncompleteClass>::iterator ummit;
};
#  endif
#endif