Форум программистов, компьютерный форум CyberForum.ru

Возможно ли это на с++? - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 21, средняя оценка - 4.86
Teravisor
30 / 30 / 3
Регистрация: 07.08.2011
Сообщений: 89
07.08.2011, 19:46     Возможно ли это на с++? #1
Допустим есть класс
Код
class MyBool{
int data;
//Читаем бит номер num
bool GetVal(num){return data&(1<<num);}
//Записываем в бит номер num значение val
void SetVal(num,val){val?data|=(1<<num):data&=~(1<<num);}
};
т.е. определены побитовое хранение булевых значений, их чтение и запись.
А теперь вопрос: Существует ли способ определить операторы так, чтобы работал следующий код:
Код
MyBool a;
if(a[0])
    a[1]=true;
Соответственно a[0] делает GetVal(0), a[1]=true делает SetVal(1,true)?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Teravisor
30 / 30 / 3
Регистрация: 07.08.2011
Сообщений: 89
07.08.2011, 21:30  [ТС]     Возможно ли это на с++? #21
Цитата Сообщение от Kastaneda Посмотреть сообщение
Возможно, только имхо - быдлокод получится, а вот, чтоб "красиво" было, по-моему не выйдет.
Главное - не красиво внутри, главное внутри эффективно, а снаружи красиво. Поэтому я и не спешу использовать vector<bool> - все vector<> уже не зарекомендовали себя там, где сильно нужна производительность.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
07.08.2011, 21:35     Возможно ли это на с++? #22
Цитата Сообщение от Teravisor Посмотреть сообщение
Поэтому я и не спешу использовать vector<bool> - все vector<> уже не зарекомендовали себя там, где сильно нужна производительность.
да ну? программы на алгоритмах и stl'вских контейнарах в большинстве случаев работают эффективнее написанных ручками
Teravisor
30 / 30 / 3
Регистрация: 07.08.2011
Сообщений: 89
07.08.2011, 21:45  [ТС]     Возможно ли это на с++? #23
Цитата Сообщение от alex_x_x Посмотреть сообщение
да ну? программы на алгоритмах и stl'вских контейнарах в большинстве случаев работают эффективнее написанных ручками
В большинстве, но не всегда. Если кривыми ручками, то конечно.
Но тут я либо не понимаю принцип STL, либо не понимаю как они это хорошо реализовали - разве на получение reference и его использование не тратятся лишние ресурсы?
Например если просто в описанном в первом посте классе задать массив интов, и делать выбор из них нужного - банальным делением - не будет ли так быстрее при доступе к большому количеству битов, хранящихся в интах? Ведь нам на каждом шаге не нужен reference - только деление - результат деления и остаток(в асме знаю, что остаток и результат сразу доступны после 1й команды) и две булевы операции. Или все таки reference быстрее будет работать? Ведь даже у него нет никаких способов указать на конкретный бит одной ссылкой.
По сути с референсами надо перейти по ссылке и все равно выполнить те же операции, чтобы достать бит. Переходы быстрые, но зачем делать лишнее там, где планируется пускать по миллионам записей?

Про вектор я говорил что не годится, т.к. в некоторых случаях лучше делать циклический один раз выделенный массив, чем вектор - намного шустрее работает. Но зависит от того, где и зачем.
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
07.08.2011, 21:52     Возможно ли это на с++? #24
Сообщение было отмечено автором темы, экспертом или модератором как ответ
вот быдлокод:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class MyBool{
int data;
unsigned last_mask;
public:
    MyBool(int d=0):data(d),last_mask(0){}
 
    MyBool& operator[](int num){
        last_mask=1<<num;
        return *this;
    }
 
    void operator=(bool b){
        data=(b ? data|last_mask : data&(~last_mask));
    }
 
    operator bool(){
        return data&last_mask;
    }
    friend std::ostream& operator<<(std::ostream &os,MyBool ob){
        return os<<std::hex<<ob.data;
    }
};
 
 
 
int main(){
    MyBool mb;
    std::cout<<mb<<std::endl;
    mb[0]=true;
    mb[1]=true;
    mb[2]=true;
    std::cout<<mb<<std::endl;
    if(mb[0])
        std::cout<<"mb[0] = true"<<std::endl;
    else std::cout<<"mb[0]=false"<<std::endl;
    return 0;
}
Может кто-нибудь красивее сделает?
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
07.08.2011, 22:05     Возможно ли это на с++? #25
Teravisor, насчет скорости bitset не знаю - мне кажется он скорее для удобства, но в том же std::vector<bool> реализован нужны вам функционал, но не реализованы удобства типа возврата reference и работы с ним
насчет того как может быть быстрее:
1) для разных типов контенеров ( с разным типом доступа ) представлены разные алгоритмы
2) для stl у компилятора большие возможности инлайнить алгоритмы и операции контейнеров

Добавлено через 7 минут
Kastaneda, неплохо!
издержки, что не работает код вида
mb[0]=mb[1]=true;
Teravisor
30 / 30 / 3
Регистрация: 07.08.2011
Сообщений: 89
07.08.2011, 22:14  [ТС]     Возможно ли это на с++? #26
Цитата Сообщение от Kastaneda Посмотреть сообщение
Может кто-нибудь красивее сделает?
Красиво, и потери небольшие. Я до такого не додумался бы)

Цитата Сообщение от alex_x_x Посмотреть сообщение
Teravisor, насчет скорости bitset не знаю - мне кажется он скорее для удобства, но в том же std::vector<bool> реализован нужны вам функционал, но не реализованы удобства типа возврата reference и работы с ним
насчет того как может быть быстрее:
1) для разных типов контенеров ( с разным типом доступа ) представлены разные алгоритмы
2) для stl у компилятора большие возможности инлайнить алгоритмы и операции контейнеров
Да, идея здравая, скорее всего так и сделаю. Придется покопаться в stl и посмотреть какие алгоритмы мне нужны.

Буду теперь копаться и думать.

Спасибо за ваше внимание и помощь в этой теме.

Добавлено через 4 минуты
Цитата Сообщение от alex_x_x Посмотреть сообщение
Добавлено через 7 минут
Kastaneda, неплохо!
издержки, что не работает код вида
mb[0]=mb[1]=true;
А тут возникает как раз проблема - чтобы это предусмотреть придется еще потратить скорости, хотя для конкретно нашего случая это не надо. В этом и проблема STL
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
07.08.2011, 22:49     Возможно ли это на с++? #27
Цитата Сообщение от alex_x_x Посмотреть сообщение
издержки, что не работает код вида
mb[0]=mb[1]=true;
Да, не подумал.
Цитата Сообщение от Teravisor Посмотреть сообщение
А тут возникает как раз проблема - чтобы это предусмотреть придется еще потратить скорости
Можно operator= вот так сделать:
C++
1
2
3
4
    bool operator=(bool b){
        data=(b ? data|last_mask : data&(~last_mask));
        return b;
    }
теперь работает, и ни каких (почти) лишних затрат
Teravisor
30 / 30 / 3
Регистрация: 07.08.2011
Сообщений: 89
07.08.2011, 23:04  [ТС]     Возможно ли это на с++? #28
Цитата Сообщение от Kastaneda Посмотреть сообщение
и ни каких (почти) лишних затрат
То же самое можно сказать и про то, как вы перешли от моих SetVal и GetVal к операторам. Если чуть приглядеться, то можно увидеть что и конвеер некоторых процессоров может работать хуже, и присваивание лишнее... Может компилятор это и оптимизировать сможет, но не факт. А 10 раз по камню это уже гора.
ValeryLaptev
Эксперт C++
1004 / 783 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
07.08.2011, 23:17     Возможно ли это на с++? #29
Цитата Сообщение от Teravisor Посмотреть сообщение
Главное - не красиво внутри, главное внутри эффективно, а снаружи красиво. Поэтому я и не спешу использовать vector<bool> - все vector<> уже не зарекомендовали себя там, где сильно нужна производительность.
Вы не правы. Наши ребята-олимпиадники сравнивали производительность вектора и "самопального" динамического массива в разных задачах. Как правило, реализация с вектором оказывалась всегда хоть немного, но быстрее любых "самопальных" структур.
Jupiter
07.08.2011, 23:19
  #30

Не по теме:

а если еще сравнить исходники вектора в составе vs и gcc, так мелкософт это просто кучка непрофессионалов

grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
07.08.2011, 23:27     Возможно ли это на с++? #31
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Мне кажется, что данная задача — это как раз тот случай, когда разумно воспользоваться прокси-объектами.
Ниже мои наброски. Несмотря на то, что исходный код раздулся, хороший оптимизирующий компилятор имеет широкий простор для деятельности и способен повыкидывать нафиг все прослойки.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
 
using namespace std;
 
class MyBoolContainer
{
private:
    class Accessor
    {
        public:
            Accessor(MyBoolContainer *p, unsigned i) : idx(i), ptr(p) {}
            Accessor& operator= (Accessor const& v)
                { return ((*this) = (bool)v); }
            Accessor& operator= (bool v)
            {
                if (v)
                    ptr->SetBit(idx);
                else
                    ptr->ClearBit(idx);
                return *this;
            }
            operator bool () const
                { return ptr->GetBit(idx); }
        private:
            unsigned idx;
            MyBoolContainer *ptr;
    };
 
public:
    MyBoolContainer() : val() {}
 
    Accessor operator[] (unsigned idx)
        { return Accessor(this, idx); }
 
    void SetBit(unsigned i)
        { val |= (1 << i); }
 
    void ClearBit(unsigned i)
        { val &= ~(1 << i); }
 
    bool GetBit(unsigned i) const
        { return 0 != (val & (1 << i)); }
 
    unsigned ToInt() const { return val; }
 
private:
    unsigned val;
};
 
int main()
{
    int i;
    cout << "input 1 or 0" << endl;
    cin >> i;
 
    MyBoolContainer c;
 
    c[0] = c[2] = (i&1);
    c[3] = 1;
    c[4] = c[3];
 
    cout << boolalpha;
    cout << "c[0] : " << c[0] << endl;
    cout << "c[1] : " << c[1] << endl;
    cout << "c[2] : " << c[2] << endl;
    cout << "c[3] : " << c[3] << endl;
    cout << "c[4] : " << c[4] << endl;
    cout << "c[5] : " << (c[5] = c[2]) << endl;
    cout << "c[3] == c[5] : " << (c[3] == c[5]) << endl;
    cout << "all in hex: " << hex << c.ToInt() << endl;
 
    return 0;
}
Наверняка тут ещё осталось место, где можно (или даже нужно) приложить руки, это всего лишь эскиз
Teravisor
30 / 30 / 3
Регистрация: 07.08.2011
Сообщений: 89
07.08.2011, 23:30  [ТС]     Возможно ли это на с++? #32
Цитата Сообщение от ValeryLaptev Посмотреть сообщение
Вы не правы. Наши ребята-олимпиадники сравнивали производительность вектора и "самопального" динамического массива в разных задачах. Как правило, реализация с вектором оказывалась всегда хоть немного, но быстрее любых "самопальных" структур.
Ключевое слово здесь - динамического. Где вы видели в предложенном мной коде динамический массив? Плюс вектор массивов зачастую еще быстрее работает. Поэтому я вектор и отметаю сразу - каким бы гениальным он не был, он будет медленнее чем нединамический массив, если его можно конечно использовать.
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
07.08.2011, 23:36     Возможно ли это на с++? #33
Цитата Сообщение от Teravisor Посмотреть сообщение
Ключевое слово здесь - динамического.
boost::array
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
07.08.2011, 23:51     Возможно ли это на с++? #34
Цитата Сообщение от Kastaneda Посмотреть сообщение
теперь работает, и ни каких (почти) лишних затрат
Зато вот так не работает:
C++
1
2
mb[0]=true;
mb[1]=mb[0];
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
07.08.2011, 23:59     Возможно ли это на с++? #35
grizlik78, у вас фактически реализация как bitset c Accessor вместо reference
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
08.08.2011, 00:00     Возможно ли это на с++? #36
alex_x_x, ну общий принцип-то давно в книжках описан. Но я не подсматривал, честно
Teravisor
30 / 30 / 3
Регистрация: 07.08.2011
Сообщений: 89
08.08.2011, 00:15  [ТС]     Возможно ли это на с++? #37
Цитата Сообщение от alex_x_x Посмотреть сообщение
boost::array
А поддерживает ли побитовое хранение?

P.S. Не пробуйте сравнить по скорости эти варианты на студии. Я попробовал и долго смеялся как она компилит.
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
08.08.2011, 08:42     Возможно ли это на с++? #38
Цитата Сообщение от alex_x_x Посмотреть сообщение
boost::array
Не знаю буста, но в компиляторах, частично поддерживающих 0x, есть такое:
C++
1
2
3
#include<array>
 
std::array<int,10> arr;
Оно?
ValeryLaptev
Эксперт C++
1004 / 783 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
08.08.2011, 12:22     Возможно ли это на с++? #39
Цитата Сообщение от grizlik78 Посмотреть сообщение
Мне кажется, что данная задача — это как раз тот случай, когда разумно воспользоваться прокси-объектами.
Ниже мои наброски. Несмотря на то, что исходный код раздулся, хороший оптимизирующий компилятор имеет широкий простор для деятельности и способен повыкидывать нафиг все прослойки.
Вы будете смеяться, но reference в bitset реализован на основе паттерна прокси...

Добавлено через 3 минуты
Цитата Сообщение от Teravisor Посмотреть сообщение
Ключевое слово здесь - динамического. Где вы видели в предложенном мной коде динамический массив? Плюс вектор массивов зачастую еще быстрее работает. Поэтому я вектор и отметаю сразу - каким бы гениальным он не был, он будет медленнее чем нединамический массив, если его можно конечно использовать.
Нединамический массив требует
1. константного выражения в качестве размера.
2. Должен быть глобальным, если его размер превосходит размер стека. Либо размер стека надо увеличивать.

С динамическими массивами подобных проблем нет. А скорость доступа по указателю - одинакова.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.08.2011, 14:15     Возможно ли это на с++?
Еще ссылки по теме:

C++ Partition для map. Возможно ли это?
C++ Как записать в вектор структуру? Это вообще возможно сделать?
Рекурсивная программа. Составить пары из группы, если это возможно C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Teravisor
30 / 30 / 3
Регистрация: 07.08.2011
Сообщений: 89
08.08.2011, 14:15  [ТС]     Возможно ли это на с++? #40
Цитата Сообщение от ValeryLaptev Посмотреть сообщение
2. Должен быть глобальным, если его размер превосходит размер стека. Либо размер стека надо увеличивать.
Или я вас не понял, или я этого не знал. Где почитать можно в надежных источниках, чтобы определиться? Если ссылка на стандарт, то пункт в нем, пожалуйста, а то он большой.

Цитата Сообщение от ValeryLaptev Посмотреть сообщение
С динамическими массивами подобных проблем нет. А скорость доступа по указателю - одинакова.
Зависит от динамического массива и компилятора: скорость доступа к элементу vector<int> a; и скорость доступа к int* a; будет разной, можно посмотреть уже проведенные замеры в интернете.
Yandex
Объявления
08.08.2011, 14:15     Возможно ли это на с++?
Ответ Создать тему
Опции темы

Текущее время: 14:49. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru