Форум 'C/C++' на RSDN.RU

hash_map

Fri, 30 Jul 2010 06:13:55 GMT

всем привет.

расскажите на пальцах как работает hash_map. Уже все облазил .. 2 недели в пустую. проект в VS2008. Как работает хэш-функция (самописная) , точнее как ее подрубать и как происходит созранение элементов в хэш-таблицу.
Так же если возможно, то как решаются коллизии... Пожалуйста на примерах (не из тупого msdn). заранее спасибо

C++ Coding Standards, Item 9. Don't pessimize prematurely

Fri, 30 Jul 2010 05:42:56 GMT

Какие случаи Саттер и Александреску имеют в виду, когда пишут:

Item 18 encourages variables that are declared as locally as possible, but includes the exception that it can be sometimes beneficial to hoist a variable out of a loop. Most of the time that won't obfuscate the code's intent at all, and it can actually help clarify what work is done inside the loop and what calculations are loop-invariant.

(Herb Sutter, Andrei Alexandrescu, C++ Coding Standards: 101 Rules, Guidelines, and Best Practices, Item 9. Don't pessimize prematurely)

Оператор преобразования vs конструктор преобразования

Thu, 29 Jul 2010 17:43:44 GMT

struct A;
struct B
{
  B(const A&);
  operator const A&();
  bool operator==(const B&) const;
};

A a;
B b;

a == b; // ****

В ******** будет вызван (MSVC2008) оператор преобразования, а затем сравнены объекты А.

Я когда писал, думал будет ошибка компиляции — ведь можно преобразовать a в b, а потом сравнить B, а можно наоборот.

Подскажите, почему такой код прокатывает?

Создание и удаление массива виртуальных объектов

Thu, 29 Jul 2010 13:18:49 GMT

Никак не могу понять, что в этом коде сделано неверно:

#include <iostream>
#include <string>

using std::string;
using std::cout;
using std::endl;

class A
{
    string name;
public:
    A(const char *title):
        name(title)
    {
        cout<<"A::A for '"<<name<<"'"<<endl;
    }
    ~A()
    {
        cout<<"A::~A for '"<<name<<"'"<<endl;
    }
};

class B
{
    A ba;
public:
    B():ba("b::a"){}
    virtual ~B(){}
    virtual void f(){}
};

class C : public B
{
    A ca;
public:
    C():ca("c::a"){}
};

int main()
{
    B *ptr = new C[5];
    delete[] ptr;
    return 0;
}

На винде в MSVC вроде работает, а в GCC на линуксе и маке вижу следующее поведение:

A::A for 'b::a'
A::A for 'c::a'
A::A for 'b::a'
A::A for 'c::a'
A::A for 'b::a'
A::A for 'c::a'
A::A for 'b::a'
A::A for 'c::a'
A::A for 'b::a'
A::A for 'c::a'
Segmentation fault

Что я делаю не так?

Cохранить capacity очистив контейнер

Wed, 28 Jul 2010 10:46:34 GMT

Если v — std::vector, то неопределено, какое значение вернет capacity после очистки вызовом clear:

    v.clear();

Можно добиться определенного поведения, когда значение capacity гарантированно будет 0, если вместо clear использовать следующую идиому:

    vector<v_value_type>().swap(v);

А можно ли добиться такого определенного поведения, чтобы при очистке значение capacity гарантированно бы не изменилось?

Pointer to the member VS bug

Wed, 28 Jul 2010 05:10:46 GMT

Проблема:

template< typename T, int T::*Field >
struct foo {};

struct test {
    int x;

    typedef foo<test,&test::x> type;
};

int main() {
    test x;
    return 0;
}

Workaround:

#define TYPEDEF_MEMBER_PTR(T,NAME,...) template< typename T > struct identity_##__LINE__ { typedef __VA_ARGS__ type; }; typedef identity_##__LINE__<T>::type NAME

TYPEDEF_MEMBER_PTR( test, type, foo<test,&test::x> );

void и все остальное: как избежать дублирования?

Tue, 27 Jul 2010 20:11:31 GMT

Допустим есть код типа:

template <typename TRes> struct Boo {
      typedef bool (*func_type)(const Data&, TRes& res);
        bool operator()(const Data&, TRes& res);
        //other logic
};

Boo также нужно реализовать для случая, когда TRes=void,
и func_type вырождается в

bool (*func_type)(const Data&)

дальше в Boo добавляют функции func_type, а потом
по некоторым критериям выбирают соотвествующую функцию.

И этот код практически одинаков для Boo<void> и Boo<не void>,
но приходится его два раза писать, т.к. компилятор не понимает
void&, это как-нибудь обходится?

PEG парсеры

Tue, 27 Jul 2010 13:41:48 GMT

Кто что может сказать по поводу
1) Chilon
2) pegtl

в плане удобности использования/простоты/надежности/скорости etc.
а также по сравнению с boost::spirit

масштаб — начиная от сложных конфигурационных файлов до фронтендов

Вопрос по GNU линкеру

Tue, 27 Jul 2010 10:13:45 GMT

Возможно я пишу не в ту ветку, но...
Господа, помогите пожалуйста напиписать скрипт линкера

Я использовал раньше такой скрипт

PHDRS
{
    text PT_LOAD;
    data PT_LOAD;
    bss PT_DYNAMIC;
}



SECTIONS
{
    OVERLAY 0x00 :
    {
         .text   {*(.text)}   :text
         .data   {  *(.data) *(.rodata) } :data

    }

     .bss   SIZEOF(.data) (OVERLAY) :  { *(.sbss) *(.bss) *(COMMON) } :bss
}

теперь нужно добавить перед секцией .data еще одину пустую секцию message размером 0x1000
и самое главное
в секциии .text VMA = 0x00
.message VMA = 0x00
.data VMA = 0x1000
.bss VMA = SIZEOF(.data)+ 0x1000

Короче нужно из всех секций сделать два сегмента кода и данных в которых адресация начинается с 0x00
Подскажите как это можно написать?
Спасибо.

Насколько "вредно" использование singleton?

Mon, 26 Jul 2010 10:10:08 GMT

После того, как узнал про этот паттерн, постоянно хочется его применять . Кажется очень удобным иметь под рукой объект, в любом месте программы. То есть, и код структурируется по классам, и не нужно с передачей ссылок на объекты возиться. Но вот в "настоящих" ООП приложениях практически не встречаю его (обычно синглтоны — только объекты Application в различных фреймворках). До этого писал на С. Насколько "неправильной" для дизайна больших приложений может быть такая практика?

Шаблонная функция для нескольких типов

Mon, 26 Jul 2010 08:45:42 GMT

Можно ли определить одну шаблонную функцию так, чтобы она принимала только несколько строго определенных, известных заранее классов, или для каждого класса нужно писать отдельную шаблонную функцию? Для всех остальных случаев, не специфицированных явно, планируется иметь обработчик по умолчанию, кидающий исключение "Not implemented". Писать несколько одинаковых функций не хочется. Как быть?

используемые классом возможности

Mon, 26 Jul 2010 05:17:23 GMT

Есть несколько возможных поток данных для программы.
И этих потоков данных может быть несколько одновременно.
Пусть базовый класс для работы с ними IInputDecoder.

Есть базовый класс, который работает с данными поставляемыми
одной из реализаций IInputDecoder. Назовем его IInputHandler.
Для абстрагирования от конкретных полей, форматов и т.д.,
есть набор фильтров, который реализует каждый наследник IInputDecoder.
Что-то типа

struct IFilter {
  virtual ~IFilter() {}
};
struct ExtractFieldFoo : public std::unary_function<double, IInputDecoder>, public IFilter { ... };

Хочется в зависимости от того, какие фильтры использует IInputHandler выбирать
какой из нескольких IInputDecoder будет давать ему данные.

Т.е. синтаксис вроде

struct IInputFiler {
  virtual ~IInputFilter () {}
  virtual is_filter_used(IFilter *) = 0;
  virtual void run() = 0;
};

struct SomeHandler : public IIinputHandler {
  USING_FILTER(ExtractFieldFoo);
  USING_FILTER(ExtractFieldBoo);
  void run() { 
    //some code
  }
};

В результате использования USING_FILTER у SomeHandler должен
а)автоматически возникнуть is_filter_used, который вернет true только
для двух реализаций фильтров
б)в методе run появится возможность использовать эти фильтры

Есть идея как это реализовать объявив SomeHandler в header файле,
и включив его два раза, меняя "#define" перед "#include", но нет ли метода попроще?

Избежать копирования при инициализации объекта

Sun, 25 Jul 2010 05:58:02 GMT

Здравствуйте. Вопрос полного чайника, но хочется оптимизации.
Как избежать копирования при инициализации объекта класса string?
Имеется буфер с длинной строкой, если эту строку присвоить объекту string, то он создаст под нее свой буфер и скопирует туда строку. Там же и будут производиться дальнейшие манипуляции. Можно ли как-то присвоить уже имеющийся буфер этому объекту?

Не шаблонные классы с шаблонными функциями

Sat, 24 Jul 2010 12:15:54 GMT

Итак, есть 2 нешаблонных класса с шаблонными функциями, которые возвращают друг друга


//header1
class A
{
    B GetB();
    template<typename T>
    B GetB(const T& t);
}

//header2
class B
{
    A GetA();
    template<typename T>
    A GetA(const T& t);
}

forward declaration для таких случаев не работает и если описать тело шаблонных функций в классе то выдает ошибку компиляции "use undefined class". Ну а если перенести тела функции в cpp файл, то, понятно, ошибка линковки возникает при использовании шаблонной функции.
Как подружить эти 2 класса чтобы и компилятор не ругался и линковщик слинковал?

конструктор копирования

Sat, 24 Jul 2010 03:00:13 GMT

Здравствуйте, имеется следующий код

#include <iostream>
#include <string>

using namespace std;


class Test
{
    public:
        Test(string theName) : name(theName)
        {
            cout << "Constructor " << name << endl;
        }

        Test(const Test &obj)
        {
            name = obj.name;
            cout << "Copy constructor " << name << endl;
        }

        ~Test()
        {
            cout << "Destructor " << name << endl;
        }

        Test& operator =(const Test &obj)
        {
            cout << "Operator = " << name << endl;
            return *this;
        }

        void show()
        {
            cout << "name : " << name << endl;
        }

    private:
        string name;
};


Test func()
{
    Test obj("test func");

    return obj;
}


int main()
{
    Test one = func();

    one.show();

    return 0;
}

В момент создания объекта one происходит вызов функции, в которой создается объект. Собственно в чем заключается вопрос, конструктор вызывается только для локального объекта в функции func(). но для объекта one конструктор копирования не вызывается,почему ? Вроде бы это называется "оптимизацией возвращаемого значения", но все равно до конца непонятно что именно происходит при создании объекта в главной функции main().

P.S На днях глядел книжку Брюса Эккеля, там был совет, если из функции возвращается объект по значению то лучше делать следующим образом:

return someObjec(lhs, rhs);

вместо того чтобы создавать объект и возвращать его как я сделал в примере выше. Вроде как это экономит ресурсы, т.к не используется конструктор копирования и деструктор.

Указатели на функции классов

Fri, 23 Jul 2010 14:54:36 GMT

Есть класс

class A {
public:
A() {};

private:
void func1( int ) {};
void func2( int) {};

};

Хочу добавить в него указатель на функцию, который будет устанавливаться в конструкторе и при вызове обращаться либо к func1 либо к func2

То есть чтобы можно было из любой процедуры класса вызывать этот указатель (который является членом класса) а сам указатель устанавливать в конструкторе на соответствующую функцию.

Как это можно сделать?

Pattern InstancePool

Thu, 22 Jul 2010 18:36:25 GMT

Хочу предложить вашему внимание паттерн проектирования InstanceManager;
Данный класс позволяет использовать только один экземпляр любого класса в программе не прибегая к помощи синглтонов:

//////////////////////////////////////////////////////////////////////////
// Therading model class example
struct SingleThread
{
  void Lock() {}
  void Unlock() {}
};

template <class T>
struct MutexLocker
{
  MutexLocker(T& m) : MyMutex(&m) { MyMutex->Lock(); };
  ~MutexLocker() { MyMutex->Unlock(); }
private:
  T* MyMutex;
};
//////////////////////////////////////////////////////////////////////////
/// class Instance pool

template<class ThreadingModel = SingleThread>
class InstanceManager
{
  class InstanceBase
  {
  public:
    virtual ~InstanceBase() {}
  };

  template <class T>
  class Instance : public T, public InstanceBase
  {
  };
public:
  ~InstanceManager()
  {
    while (!ObjectPool.empty())
    {
      delete ObjectPool.begin()->second;
      ObjectPool.erase(ObjectPool.begin());
    }
  }
  template <class T>
  T* GetInstance(const T* t = 0)
  {
    const Loki::TypeInfo id(typeid(t));
    ObjectPoolMap::iterator o = ObjectPool.find(id);
    if (o == ObjectPool.end())
    {
      MutexLocker<ThreadingModel> locker(InsertMutex);
      o = ObjectPool.find(id);
      if (o == ObjectPool.end())
      {
        o = ObjectPool.insert(ObjectPoolMap::value_type(id, new Instance<T>())).first;
      }
    }
    return static_cast<T*>(static_cast<Instance<T>* >(o->second));
  }
private:
  ThreadingModel InsertMutex;
  typedef std::map<Loki::TypeInfo, InstanceBase*> ObjectPoolMap;
  ObjectPoolMap ObjectPool;
};

пример использования:

class TestClass
{
public:
  TestClass() { std::cout<< "TestClass" << std::endl;  }
  virtual ~TestClass() { std::cout<< "~TestClass" << std::endl;  }
  void Print() { std::cout<< "TestClass::Print" << std::endl;  }
};

class TestClass2
{
public:
  TestClass2() { std::cout<< "TestClass2" << std::endl;  }
  virtual ~TestClass2() { std::cout<< "~TestClass2" << std::endl;  }
  void Print() { std::cout<< "TestClass2::Print" << std::endl;  }
};

void TestProgramm()
{
  InstanceManager<SingleThreading> manager;
  manager.GetInstance<TestClass>()->Print();
  manager.GetInstance<TestClass2>()->Print();
  manager.GetInstance<TestClass>()->Print();
  manager.GetInstance<TestClass2>()->Print();
  return 0;
}

класс TypeInfo, код взят из библиотеки Loki

namespace Loki
{
  class TypeInfo
  {
  public:
    // Constructors
    TypeInfo(); // needed for containers
    TypeInfo(const std::type_info&); // non-explicit

    // Access for the wrapped std::type_info
    const std::type_info& Get() const;
    // Compatibility functions
    bool before(const TypeInfo& rhs) const;
    const char* name() const;

  private:
    const std::type_info* pInfo_;
  };

  // Implementation

  inline TypeInfo::TypeInfo()
  {
    class Nil {};
    pInfo_ = &typeid(Nil);
    assert(pInfo_);
  }

  inline TypeInfo::TypeInfo(const std::type_info& ti)
  : pInfo_(&ti)
  { assert(pInfo_); }

  inline bool TypeInfo::before(const TypeInfo& rhs) const
  {
    assert(pInfo_);
    // type_info::before return type is int in some VC libraries 
    return pInfo_->before(*rhs.pInfo_) != 0;
  }

  inline const std::type_info& TypeInfo::Get() const
  {
    assert(pInfo_);
    return *pInfo_;
  }

  inline const char* TypeInfo::name() const
  {
    assert(pInfo_);
    return pInfo_->name();
  }

  // Comparison operators

  inline bool operator==(const TypeInfo& lhs, const TypeInfo& rhs)
  // type_info::operator== return type is int in some VC libraries
  { return (lhs.Get() == rhs.Get()) != 0; }

  inline bool operator<(const TypeInfo& lhs, const TypeInfo& rhs)
  { return lhs.before(rhs); }

  inline bool operator!=(const TypeInfo& lhs, const TypeInfo& rhs)
  { return !(lhs == rhs); }    

  inline bool operator>(const TypeInfo& lhs, const TypeInfo& rhs)
  { return rhs < lhs; }

  inline bool operator<=(const TypeInfo& lhs, const TypeInfo& rhs)
  { return !(lhs > rhs); }

  inline bool operator>=(const TypeInfo& lhs, const TypeInfo& rhs)
  { return !(lhs < rhs); }
}

Правильное ли поведение компилятора?

Thu, 22 Jul 2010 16:13:32 GMT

Компилятор от Visual Studio 2010

std::ostream& myFunction(std::ostream& lArg, volatile const char* rArg) 
{ 
    return lArg << rArg; //warning C4800: 'volatile const char *' : forcing value to bool 'true' or 'false' (performance warning)
}

Почему так происходит?

error: Stack around the variable 'prbs' was corrupted

Thu, 22 Jul 2010 15:58:18 GMT

не пойму, в чем ошибка. подскажите как исправить?

Run-Time Check Failure #2 — Stack around the variable 'prbs' was corrupted.

#include <iostream>

using namespace std;

void shift(int *a, int new_val)
{
     for (int i=3; i>0; i--)
     {
         a[i] = a[i-1];
     }
     a[0]=new_val;
}


int main(int argc, char *argv[])
{


     int prbs[3] = {1,1,1};

     int tap;

     for (int i=0; i<16;i++)
     {
         tap = prbs[0] ^ prbs[2];
         shift(prbs,tap);
         printf("%d",tap);
     }



     system("pause");
     return 0;
}

Вопрос для знатоков stl: разбить контейнер на части

Thu, 22 Jul 2010 14:27:36 GMT

Допустим есть контейнер std::vector<T> m_vec; (лист или вектор не важно)
В нём к примеру 100 элементов.
Как быстро, за минимальное количество строк разбить этот контейнер на n контейнеров, которые будут содержать по maximum m элементов.
Допустим если там 100 элементов, и нужно разбить на контейнеры по 30, то на выходе должно быть четыре контейнера
std::vector< std::vector<T> > [0].size() = 30
std::vector< std::vector<T> > [1].size() = 30
std::vector< std::vector<T> > [2].size() = 30
std::vector< std::vector<T> > [3].size() = 10

лист или вектор не принципиально
только не спрашивайте зачем