Создание хорошего описания к коду

#yii #структуры #проектирование #проекты

Как возник данный вопрос, я, наверное, уже перейду к сути. Есть запрос на сервак,
у него 26 параметров. (мило правда?) запросов к серваку примерно может быть около 350!
в каждом от 5 до кучи передаваемых параметров.
Смысл в следующем, вот и вопрос.
У меня каждый запрос разбит на свой Action каждый action лежит в отдельном файле
//upd_start
Почему выбрано именно разбиение actions на файлы. Проект достаточно большой. Чтобы
все разработчики не расширяли сам контроллер, а просто дописывали в него 1-2 строчки
для подключения нового экшена + удобно редактировать проект такими кусками, а не целым
файлом, который бы терпел изменения постоянно. По мне так это правильно.
//upd_end
пример:
public function actions()
     {
     /* All actions in this controller 
      * are located in folder 
      * application.controllers.frontend.requests
      */
     return array(
                  'gf' => 'application.controllers.frontend.requests.gf',
                   // и т.д.
                );
      }

Первый вопрос:

На каком языке писать описание ко всему проекту?

В данный момент пытаюсь описывать на ENG, как может быть заметно из вышеописанной
функции, описание на ENG.
В gf.php описание тоже на ENG
@NumSeats          - The total number of passengers for which availability is being
requested
 @StartDt           - Date of Departure or Arrival. 
 @StartPt           - Airport or city code of the customer embarkation.
 @EndPt             - Airport or city code of the customer Destination.
 @StartTm           - Requested departure in 24-hour clock

В принципе, считаю что это правильно! В плане разработки проекта другими участниками,
как русско, так и англо говорящими.
Но есть одно но. Есть люди в компании не особо понимающие ENG язык и тем самым просят
комментировать код на русском языке.
В чем прикол? Ну на русском читать ведь проще! Соглашусь, переводить технический
ENG это пипец как "весело", схожу потихонечку с ума + ко всему не всегда получается
правильно перевести ENG на RUS в связи с разными обстоятельствами (незнание каких-то
оборотов и т.д.) В общем хватает веселых вещей по языкам.
Есть варианты решения, забить на ENG писать только на RUS второе решение писать только
на ENG, третье писать в 2х вариантах и в ENG/RUS что решит траблы обоих случаев, но
увеличит кол-во описания к коду, что на мой взгляд не есть хорошо.
Вот на стадии проектирования проекта и хочу выяснить как лучше делать.
С одной стороны хочется доставить всем удовольствие от разработки и писать описание
для всех, все равно приходится переводить мануал системы на RUS, с другой стороны писать
описалово на 2х языках муторно и как-то по кол-ву кода в файле слишком много.
Будет ли большое описание влиять на производительность кода?
последнее редактирование - 11.06.2013 15:32
Будут дополнения озвучу, пока все.
Жду ваших интересных отзывов по теме. 
Естественно буду продолжать открывать новые вопросы по теме разработки.    

Ответы

Ответ 1

@Shrek, не очень понял, что это за люди, которые хотят на русском.
Если они будут сопровождать проект, то лучше делать комментарии на RUS.
Если же это кто-то просто из любопытных заказчиков, то как Вам удобней (видимо, оставьте
ENG).
А писать комментарии в 2-х вариантах, это ни к чему. Тогда уж лучше их вообще не
писать, т.к. через полгода один из вариантов точно уже не будет соответствовать коду.

Как сортировать массив структур по одному из параметров структуры?

#cpp #visual_cpp #сортировка #структуры

struct Student
{
    char last_name[m];
    char name[m];
    char surname[m];
    int proga[n];
    int sda[n];
    int mat_analiz[n];
    int lin_algebra[n];
    int sum_ball;
}student[k];


Подскажите как отсортировать данную структуру по переменой sum_ball, и если совпадает
то по last_name 
Как ни пробовал, ничего не получается, просто выдает какую-то ахинею.
Раньше с таким не приходилось работать.

Student temp;   

for (int i = 0; i < k; i++)
{
    for (int j = i; j < k; j++)
    {
        if (student[j].sum_ball < student[i].sum_ball)
        {
            temp.last_name = student[i].last_name;
            student[i].last_name = student[j].last_name;
            student[j].last_name = temp;
            //и так дали с другими 

        }
    }
}


Ну например вот так, с массивами так можно а с структурами как? Это ж не правильно
я понимаю
    

Ответы

Ответ 1

Требуемый компаратор может выглядеть, например, так:

[](const Student&a, const Student&b)
{
    if (a.sum_ball < b.sum_ball) return true;
    if (a.sum_ball == b.sum_ball) 
        return strcmp(a.last_name,b.last_name) < 0;
    return false;
}


Вроде бы так...

Как корректно записать/считать в/из файла структуру с полями типа string? [дубликат]

#cpp #строки #структуры

        
             
                
                    
                        
                            На этот вопрос уже дан ответ здесь:
                            
                        
                    
                
                        
                            Ошибка сохранения сложной структуры в файле
                                
                                    (1 ответ)
                                
                        
                                Закрыт 10 месяцев назад.
            
                    
Имеется структура

struct User {
    string login;
    string password;
};


Стоит задача сделать примитивную авторизация пользователя. Т.е. создается файлик,
в него записывается заполненный объект вышеуказанной структуры, а при последующих запусках
производится запрос логина+пароля, считываются данные из файлика и сравниваются. Код:

#include 
#include 
#include 
#include 
#include 

using namespace std;

struct User {
    string login;
    string password;
};

void main ()
{
    SetConsoleCP (1251); // установка универсальной кодировки
    SetConsoleOutputCP (1251);

    string path;
    int realsize=0;
    User u;
    vector  U;
    bool exit = false;

    do
    {
        system("cls");
        cout<<"Укажите, на каком диске находится файл с регистрационными данными:\n";
        getline(cin, path);
        path += ":\\users.txt";
        ifstream fin(path, ios_base::binary | ios_base::in);

        if (fin.is_open())
        {
            cout<<"Отлично, ваш файл найден!\n";
            fin.read((char*)&u, sizeof(User));
            U.push_back(u);
            fin.close();
            cout << "Введите логин:\n";
            getline(cin, u.login);
            cout << "Введите пароль:\n";
            getline(cin, u.password);
            if (!U.at(0).login.compare(u.login) && !U.at(0).password.compare(u.password))
            {
                cout << "Вы авторизованы!\n";
            }
            else
            {
                cout << "Вы не авторизованы!\n";
            }
            exit = true;
        }
        else
        {
            cout << "Файл не найден и будет создан";
            ofstream fout (path, ios_base::binary | ios_base::out);
            if (fout.is_open())
            {
                cout << "Введите логин:\n";
                getline(cin, u.login);
                cout << "Введите пароль:\n";
                getline(cin, u.password);
                fout.write((char*)&u, sizeof(User));
                fout.close();
                cout << "Файл создан и данные внесены!\n";
            }
            else
            {
                cout << "Ошибка при создании файла! Работа приложения будет завершена.\n";
                exit = true;
            }
        }
    } while(!exit);

    system("pause");

}


Вся беда в том, что при выполнении данного кода появляется ошибка:


  Необработанное исключение по адресу 0x0FDECCC8 (msvcp110.dll) в test.exe: 0xC0000005:
нарушение прав доступа при чтении по адресу 0x0067ADE4.


Кадры стека вызовов:



Путем экспериментов установлено, что замена использования вектора на простой динамический
массив никак не влияет на ошибку (т.е. она по-прежнему появляется), а вот замена использования
string на char * приводит к устранению проявления данной ошибки. Погуглив, я пришел
в выводу, что возникает какая-то ошибка в деструкторе string (могу ошибаться). Может
кто-нибудь прояснить ситуацию и дать рекомендации по корректному использованию типа
string в данного рода задачах?  
    

Ответы

Ответ 1

Самый простой способ (как уже упомянул в комментарии @pavel) - использовать текстовый
режим работы с файлом и операторы форматированного ввода/вывода (operator<<, operator>>)
для чтения/записи std::string из/в потока.

Чтение:

ifstream fin(path); 
if (fin) {
   fin >> u.login >> u.password;
}


Запись:

ofstream fout(path); 
if (fout) {
   // Разделители нужны для последующего считывания
   fout << u.login << " " << u.password << "\n"; 
}


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

Функции istream::read, ostream::write в этом случае не используются вовсе. Причина,
по которой они не работают как надо указана в ответе @gbg.


Ответ 2

Запись в файл с помощью 

fout.write((char*)&u, sizeof(User));


действительно запишет побайтово содержимое структуры User, но т.к. она содержит не
POD типы (std::string), то пользы от этого мало, т.к. сами данные ваших строк скорей
всего в куче находятся.

В вашем случае можно записать логин и пароль в файл (при условии, что в них не используется
перевод строки), по одному на строчку, и также читать. Пример:

int main() {
    struct User {
        std::string login;
        std::string password;
    };

    {
        User user{ "login", "password" };

        // Пишем логин и пароль в файл в две строчки
        std::ofstream f("users.txt");
        f << user.login << std::endl << user.password;
    }

    {
        User user;

        // Читаем из файла
        std::ifstream f("users.txt");
        std::getline(f, user.login);
        std::getline(f, user.password);

        std::cout << user.login << std::endl << user.password << std::endl;
    }
}


Ответ 3

Так работать не будет. string не является POD - типом, то есть сам объект типа string
не содержит данные строки, они размещаются в другом месте (куда их затолкает аллокатор).

Правило простое - все, что не является POD нельзя просто так взять и скопировать
побайтно.

Решение - использовать для хранения данных типы, являющиеся POD

struct mu_ugly_pod
{
    char user_name[100500];
    char user_last_name[100500];
};


Такая штуковина должна писаться и читаться без проблем. Увы, все удобства, связанные
со string в данном случае пропадут.

Структуры. Выделение памяти в структуре для строк по указателям

#cpp #структуры

Нашел в интернете такой пример использования структуры

struct building     //Создаем структуру!
{                  
    char *owner;       //здесь будет храниться имя владельца
    char *city;        //название города
    int amountRooms;   //количество комнат
    float price;       //цена
};                 

int main()
{
    building apartment1;   //это объект структуры с типом данных, именем структуры,
building

    apartment1.owner = "Денис"; //заполняем данные о владельце и т.д.
    apartment1.city = "Симферополь";      
    apartment1.amountRooms = 5;
    apartment1.price = 150000;


Для *owner и *city - что-то не вижу выделения памяти, значит ли это, что данные запишутся
хз куда, и не удалятся по завершении программы?
    

Ответы

Ответ 1

Данные останутся на своем месте, т.е. никуда не переместятся и не перезапишутся.
В ваших полях owner и city хранятся указатели на них (адреса первых символов).

Так что вы не можете их удалять (не вздумайте написать delete[]city, например) -
они не были выделены динамически, и не имеете права их перезаписывать (типа city[0]='A')
- это строковые литералы.


Ответ 2

Строковый литерал в С и С++ является немодифицируемым объектом типа "массив" со статическим
классом памяти. То есть когда вы в своем коде пишете "Симферополь" вы фактически создаете
безымянный символьный массив, который фактически является статической переменной. Она
существует с самого начала жизни программы и до самого ее конца. Вся необходимая память
уже выделена и освобождать ее - не ваша задача.


Ответ 3

по хорошему имя владельца и название города в структуре должны быть константными

    struct building     //Создаем структуру!
{                  
    const char *owner;       //здесь будет храниться имя владельца
    const char *city;        //название города
    int amountRooms;   //количество комнат
    float price;       //цена
};


тогда с main() все нормально, так как инициализация есть выделение памяти

sizeof() и битовые поля

#cpp #структуры #sizeof

Вот имеется структура:

struct Data
{
    char A : 4;
    unsigned B: 12;
};


Если убрать в ней поле A, то sizeof(Data) выдаст 4. Нормально.
Убрать поле B, sizeof(Data) вернет 1. Нормально.
А если оставить  A и B, то sizeof(Data) вернет 8!. Непонятно.  

Почему 8, а не 5?
    

Ответы

Ответ 1

Низкоуровневые детали размещения в памяти битовых полей не стандартизованы и определяются
реализацией. 

Однако с абстрактной точки зрения битовые поля выделяются внутри т.наз. единиц аллокации.
Обычно единица аллокации - это просто полноценное поле того самого типа, который указан
в объявлении битового поля. Последовательные битовые поля пакуются в последнюю выделенную
единицу аллокации, пока она не заполнится.

И в некоторых реализациях смена типа в объявлении битового поля приводит к досрочному
завершению заполнения текущей единицы аллокации и выделению новой единицы аллокации.
Т.е. в данном случае при работе с такими реализациями в вашем примере получится две
отдельные единицы аллокации: типа char и типа unsigned. В таких реализациях эти единицы
аллокации обычно ведут себя так же как и обычные поля соответствующего типа, т.е. фактически
вы имеете дело с

struct Data
{
    char unit1;
    unsigned unit2;
};


А такая структура имеет размер 8 из соображений выравнивания. Если же вы явно запросите
выравнивание в 1, то такая структура получит размер 5.

В компиляторе GCC, например, используется совсем другой подход к выделению новых
единиц аллокации и там ваша структура получит размер 4.


Ответ 2

Если поле имеет размер 12 бит и хочется сэкономить на размере, то совершенно нет
смысла делать его типом int, имеющим размер 4 байта. Структуру из примера можно переписать так

struct Data {
    uint16_t A : 4;
    uint16_t B : 12;
};


Занимает всего два байта.

Поведение сборщика мусора по отношению к структурам

#c_sharp #структуры #сборщик_мусора #производительность

Недавно прочитал статью Предельная производительность: C#

Из-за того, что структуры хранятся в stack’е, они не требуют сборки мусора

поясните пожалуйста, это действительно так?    

Ответы

Ответ 1

Краткое содержание. Нет, структуры не обязательно хранятся в стеке, а объекты --
в куче. Да, с хорошими шансами структура всё же попадёт в стек. Нет, вам не стоит на
это рассчитывать, пользоваться этим и пытаться оптимизировать таким образом.

На самом деле следует понимать простую вещь: выделение переменной на стеке дешевле,
поскольку её можно легко уничтожить, не включая в цикл сборки мусора. Выгода на самом
деле только в этом. (Аллокация что на стеке, что в куче -- не более, чем увеличение
одного указателя, она очень быстрая.)
Очевидно, оптимизатор будет размещать в стеке те переменные, которые, как он может
доказать, не нужны после смерти текущего фрейма. Часто про структуры можно такое доказать,
но не всегда. Например, структура может быть частью объекта класса, и должна умереть
вместе с классом. Или метод будет неявно переписан в стиле продолжений, например, если
это генератор (yield return & Co.) или Task<> с async/await. Или переменная попала
в замыкание некоторой лямбда-функции. И так далее. Но обычно структуры не нужны после
отработки метода, так что оптимизатор может вытеснить их в стек.
С другой стороны, про некоторые объекты можно тоже утверждать, что они не нужны после
окончания фрейма -- и тогда оптимизатор тоже имеет полное право (но не обязанность,
конечно) разместить и их на стеке.
Обратите внимание на такую тонкость: если вы возвращаете из метода структуру, вы
на самом деле возвращаете её копию, поэтому структура, с которой вы работали, может
попасть в стек. С классами же не так: они копируются не по значению, а по ссылке, поэтому
возвращаемый объект переживает создавшую его функцию, и следовательно не имеет права
жить в стеке.
Использованы материалы из блога Эрика Липперта, на которые была ссылка выше.

Добавлю ещё пару цитат из Эрика:

Использование стека для локальных переменных-структур -- всего лишь оптимизация,
которую CLR выполняет для вас. Существенная особенность структур -- семантика копирования
по значению, а вовсе не то, что в некоторых случаях их уничтожение может быть оптимизировано
рантайм-библиотекой.



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



Превращение типа, который должен на самом деле быть ссылочным типом, в структуру
-- это нано-оптимизация, дающая выгоду в пару наносекунд, и вероятно не стоящая того.
На вашем месте я бы проводил такую оптимизацию только если данные профилирования покажут,
что существует реальная, большая проблема у ваших реальных клиентов, которую можно
исправить использованием структур. Не имея таких данных на руках, я всегда бы делал
выбор между классами и структурами основываясь на том, представляет ли тип семантически
значение или ссылку на что-то. (То есть, имеет ли объект смысл помимо значения, содержащегося
в нём, обладает ли он самостоятельной сущностью -- VladD)


Ответ 2

Из-за того, что структуры хранятся в stack’е, они не требуют сборки мусора
поясните пожалуйста, это действительно так?

Если речь идет о локальных переменных, то это действительно так. GC работает с кучей.
Очевидно, что структуры не всегда хранятся в стеке. Например, если какой-то класс
содержит поля, являющиеся структурами, то память под них однозначно будет выделена
в куче, и, следовательно, будут уничтожаться GC.
P.S.: Если структура содержит управляемые поля, то память под эти поля выделится
в куче, а в стеке окажутся лишь ссылки на эти управляемые поля. Довольно логично, но
некоторые упускают это из виду.

Как записывать и считывать структуру в файл с расширением *.dat?

#c #структуры

Мне необходимо создать файл, содержащий сведения о личной коллекции книголюба. Структура
записи: шифр книги, автор, название, год издания, местоположение (номер стеллажа и т.п.).

Причем, запись (input()) и чтение (output()) структур производятся в файл/из файла
с расширением *.dat .
При каждой новой записи у нас, по сути, добавляется новая структура.
Так вот, у меня не выходит никак нормально считывать. Выводит только последнюю записанную. 
Так же не получается вводить новый шифр книги для следующей структуры, он просто
gets(B.key); пропускает.

#include 
#include 
#include 
#include 


void input(void);
void output(void);

struct cd
{
    char key[12];
    char author[30];
    char title[20];
    int year;
    int location;
} B;

FILE *f;

void main(void)
{
    int n = 0;
    system("cls");
    setlocale(LC_CTYPE, "rus");
    while(n != 3)
    {
        puts("1. Ввод данных в базу");
        puts("2. Вывод всех авторов");
        puts("Для выхода из программы нажмите любую другую клавишу...");
        puts("\nВаш выбор: ");
        scanf("%d",&n);
        fflush(stdin);
        switch(n)
        {
            case 1: input(); break;
            case 2: system("cls"); output(); break;
            default: exit(1);
        }
    }
}

void input(void)
{
    setlocale(LC_CTYPE, "rus");
    int k = 0;
    if(( f = fopen("knigolub.dat","w")) == NULL)
    {
        puts("Невозможно открыть файл");
        exit(1);
    }
    while (k != 10) {
        system("cls");
        puts("Введите сведения о книге...\n\n");
        printf("Введите шифр книги: ");
        gets(B.key);
        printf("Введите автора: ");
        gets(B.author);
        printf("Введите название: ");
        gets(B.title);
        printf("Введите год издания: ");
        scanf("%i", &B.year);
        printf("В какой стеллаж поместить? Введите его номер: ");
        scanf("%i", &B.location);
        fwrite(&B, sizeof(B), 1, f);
        puts("Продолжить работу?[y/n]");
        char s;
        scanf("%s", &s);
        switch ((int) s) {
            case (int) 'y': return input();
            case (int) 'n': return main();
        }
    }
}

void output (void)
{
    char letter;
    setlocale(LC_CTYPE, "rus");
    if((f=fopen("knigolub.dat","r")) == NULL)
    {
        puts("Невозможно открыть файл");
        exit(1);
    }
    printf("Шифр книги\tАвтор\tНазвание\tГод издания\tНомер стеллажа\n\n");
    while ((letter == fgetc(f)) != EOF) {
        printf("%s\t%s\t%s\t%i\t%i\t\n", B.key, B.author, B.title, B.year, B.location);
    }
    getch();
    system("cls");
    fclose(f);
}

    

Ответы

Ответ 1

Под *.dat обычно подразумевают некий бинарный псевдоформат. Потому  fw = fopen("knigolub.dat","wb"))
и fr = fopen("knigolub.dat","rb")) и чтение-запись выполняем через fread и fwrite.
Пусть в начале файла идет число записей (size_t):

size_t count = 0;
cd *buffer = NULL;

fread (&count, sizeof(size_t), 1, fr);

buffer = (cd*)malloc(sizeof(cd) * count);

fread (buffer, sizeof(cd), count, fr);


Записываем, соответственно, наоборот - сначала пишем число, затем структуры. Если
нужно добавить структуру в файл - определяем смещение (sizeof(size_t) + sizeof(cd)*count),
а затем записываем записываем в число в начале файла значение count + 1


Ответ 2

Выводит только последнюю записанную.


Дело не в том, что ВЫВОДИТ последнюю записанную структуру, а в том, что при записи
очередной структуры Вы  затираете (!!!) предыдущую. Каждый раз, когда выполняется вызов
input(...), Вы выполняете повторное открытие файла:

f = fopen("knigolub.dat","w")


При этом предыдущее содержимое файла ЗАТИРАЕТСЯ. Надо либо:


Открывать один раз в начале работы всей программы 
Открывать с атрибутом добавления "a" (Open  for  appending:  writing  at end


of file)

Как реализовать динамический массив?

#структуры

Можно ли реализовать список на базе массивов, от которого требуется:


Не константный размер (заранее неизвестен, может расширяться).


Время вставки было О(1) или около того.


Посмотрел реализацию в Java. Там получается, что вставка работает за O(1) во всех
случаях, кроме случая, когда требуется расширение массива (в этот момент из-за копирования
получается O(N)), где массив расширяется в 1,5 раза. Требуется же, чтобы работа операции
вставки в конец работала во всех случаях за константное время.    

Ответы

Ответ 1

Пошел дождь, планы изменились, я набросал простейшую реализацию. Ее, конечно, еще
тестировать надо, но если кому интересно, выкладываю код.
Прошу извинения, он довольно большой, но как поместить код куда нибудь и дать здесь
ссылку на него, я не знаю.
/*
  avp 2011

  Динамический массив размером до 2^32 элементов.

  По сути структура MMU с динамическим выделением сегментов данных
  и блоков оглавления нижнего уровня. Оглавление всегда 2 уровня.

  Структура 32-разрядного адреса:
  10 бит индекс в корневом блоке оглавления
  10 бит индекс в блоке сегментов памяти
  12 бит индекс элемента в сегменте данных

  Корневой блок, нулевой блок сегментов и нулевой сегмент создаются 
  сразу при создании динамического массива.

  struct dyna *dyna_init (int elem_size);
    Создать массив с нулевым сегментом 4096 элементов
    размером elem_size байт каждый.
    Дескриптор (struct dyna) выделяется malloc().

  void dyna_free (struct dyna *dyna);
    Освободить всю память массива и дескриптор.

  void *dyna_get (struct dyna *dyna, unsigned int index);
    Возвращает адрес DynArray[index] или NULL (нет памяти).
    При первом обращении память под соответствующий сегмент данных 
    выделяется автоматически.
    Массив в середине может содержать 'дыры' (аналогично файлу в Unix).

  void *dyna_segment (struct dyna *dyna, unsigned int index);
    Возвращает адрес начала сегментв данных размером 4096 элементов
    динамического массива, содержащий элемент с индексом index.
    Если сегмента нет  (дыра, обращений к эдементам массива, входящих
    в этот сегмент не было), то возвращаем NULL.

    По большому счету, надо использовать posix_memalign() вместо malloc(),
    НО в MinGW ее нет.
 */

#include 
#include 

struct dyna {
  void         **root;    // адресуем по старшим 10 бит.
  unsigned int maxindex;  // максимальный размещенный индекс.
  int          elem_size; // елемент данных в байтах.
};

#define DEBUG 1

struct dyna *
dyna_init (int elem_size)
{
  struct dyna *dyna = malloc(sizeof(*dyna));
  if (!dyna)
    return NULL; // Тут по хорошему надо exit(), ну и далее тоже.

  if (!(dyna->root = calloc(1024,sizeof(void *))))
    return NULL;  
  if (!(dyna->root[0] = calloc(1024,sizeof(void *))))
    return NULL;

  char **table = dyna->root[0];
  // первый сегмент данных
  if (!(table[0] = calloc(4096,dyna->elem_size=elem_size))) 
    return NULL;

  dyna->maxindex = 4095;
  return dyna;
}

void
dyna_free (struct dyna *dyna)
{
  int  i;
  char **tab;

  for (i = 0; i < 1024; i++) {
    if (tab = dyna->root[i]) {
      int j;
      for (j = 0; j < 1024; j++) {
    if (tab[j])
      free(tab[j]);
      }
      free (tab);
    }
  }
  free(dyna->root);
  free(dyna);
}

void *
dyna_segment (struct dyna *dyna, unsigned int index)
{
  int  rix = (index >> 22) & 0x3ff,
    tix = (index >> 12)  & 0x3ff;
  char **tab;

  if (tab = dyna->root[rix])
    return tab[tix];
  return NULL;
}

void *
dyna_get (struct dyna *dyna, unsigned int index)
{
  int  rix = (index >> 22) & 0x3ff,
    tix = (index >> 12)  & 0x3ff,
    dix = index & 0xfff;
  char **tab;

  if (tab = dyna->root[rix]) {
    if (!tab[tix])
      if (!(tab[tix] = calloc(4096,dyna->elem_size)))
    return NULL; // Беда
    // OK tab[tix] содержит адрес сегмента данных с index.
  } else {  // делаем таблицу сегментов и сегмент данных
    if (!(tab = dyna->root[rix] = calloc(1024, sizeof (void *))))
      return NULL; // Совсем беда
    if (!(tab[tix] = calloc(4096,dyna->elem_size)))
      return NULL; // Опять беда
  }
  // OK tab[tix] содержит адрес сегмента данных с index.
  //  char *dat = tab[tix]; // segment addr
  if (index > dyna->maxindex)
    dyna->maxindex = ((index+4096) & 0xfffff000)-1;
  return tab[tix] + dix * dyna->elem_size;
}

#if DEBUG
main ()
{
  struct dyna *dar;
  int *pi, i, *ps, nn[10];

  dar = dyna_init(sizeof(int));
  if (dar) {
    printf ("root = 0x%x, maxi = %d, esiz = %d\n",
        dar->root, dar->maxindex, dar->elem_size);
  } 
  char **tab = dar->root[0];
  printf ("root[0] = 0x%x, tab[0] = 0x%x, tab[1] = 0x%x, segm[0] = 0x%x\n",
      tab,tab[0],tab[1],dyna_segment(dar,5));
                                                                                
                                                                                  
                                                                                  
                                           printf ("segm[0](0) 0x%x; segm[0](2000)
0x%x; segm[0](4095) 0x%x; segm[1](4096) 0x%x; segm[?](100000) 0x%x\n",
  dyna_segment(dar,0),dyna_segment(dar,2000),dyna_segment(dar,4095),
  dyna_segment(dar,4096),dyna_segment(dar,100000));

  pi = dyna_get(dar,i = 4097);
  printf ("root = 0x%x, maxi = %d, esiz = %d\n",
      dar->root, dar->maxindex, dar->elem_size);
      printf ("tab[0] = 0x%x, tab[1] = 0x%x, segm[1] = 0x%x, pi = 0x%x, *pi = %d\n",
      tab[0], tab[1], ps = dyna_segment(dar,i), pi, *pi);
  for (i = 0; i < 3; i++)
    ps[i] = i+10;
  printf ("ps = 0x%x\n",ps);
  for (i = 4096; i < 4099; i++) {
    pi = dyna_get(dar,i);
    printf ("i = %d pi = 0x%x *pi = %d\n",i,pi,*pi);
    nn[i-4096] = *pi;
  }
  for (i = 0; i < 3; i++)
    printf ("nn[%d] = %d ",i,nn[i]);
  putchar('\n');
                                      printf ("segm[0](0) 0x%x; segm[0](2000) 0x%x;
segm[0](4095) 0x%x; segm[1](4096) 0x%x; segm[2](8192) 0x%x\n",
      dyna_segment(dar,0),dyna_segment(dar,2000),dyna_segment(dar,4095),
      dyna_segment(dar,4096),dyna_segment(dar,8192));
  dyna_free (dar);
  printf ("End\n");
  exit (0);
}

#endif

Результаты того, что я запускал, выглядят вполне разумными. Если кто найдет ошибки,
буду признателен.


Ответ 2

Это не ответ, а некоторые соображения 'по поводу'.
Итак, допустим требуется: массив может расти 'вперед', новые элементы добавляются
в конец, время доступа по индексу O(1), занимаемое массивом пространство непрерывно
и при этом расширение массива тоже требует времени O(1). 
Если отбросить непрерывность на всем протяжении, то можно представить набор массивов
(сегментов нашего виртуального массива). Эти сегменты д.б. достаточно большими (тысячи
элементов). Этот список может только расти. При появлении второго и следующих сегментов
делаем оглавление. Вначале оглавление это один сегмент (один уровень косвенности).
Каждый элемент оглавления ссылается (по адресу) на первый элемент соответствующего
сегмента с элементами массива. 
Таким образом оглавление из одного сегмента размером N адресует N*N элементов массива.
Очевидно все адреса вычисляются за O(1). Добавление сегментов памяти в массив тоже O(1).
Дальнейший рост массива приводит к появлению следующих уровней оглавления. Два уровня
позволяют адресовать N*N*N элементов массива за три вычисления адреса. При N = 1000
два уровня оглавления адресуют миллиард элементов массива.
Разумеется к элементам такого "массива" не получится обращаться по традиционной записи
Arr[i]. Для работы с элементами надо разработать удобный набор функций.
Это, конечно, достаточно общие соображения на скорую руку. Надеюсь, хоть частично
угадал, что требовалось.


Ответ 3

Не знаю почему никто не упомянул std::deque, в отличие от std::vector при добавлении
не делает realloc, соответственно работает быстрее. Если элементом очереди будет <
data, next >, то порядок следования становиться не важен...
P.S. мне кажется, что-то похожее описывал @avp в своем ответе


Ответ 4

Если я правильно поняла вопрос, то можно использовать "теневое" копирование. Т.е.
при "расширении" копировать элементы по шагам (несколько элементов при каждой вставке).
У нас есть 2 массива: 

Массив длины N, в который добавляются элементы (активный).
Массив большей длины, например, 2*N, который находится в стадии заполнения.

Мы будем добавлять элементы в первый массив. Далее, когда он заполнится на 0,75*N
(например), начнем копировать по несколько элементов в массив большей длины. Конечно,
количество скопированных элементов за один шаг должно быть выбрано таким образом, чтобы
 копирование завершилось до переполнения старой структуры структуры :) Возьмём, количество
элементов за шаг = 4 (K). Когда элементы меньшего массива полностью скопированы в новый,
больший по размеру массив, старый массив удаляется, а новый принимается в качестве
активной структуры. Далее (при необходимости) снова создается массив большей длины. 
Получится, что доступ к элементам останется O(1), а для добавления элемента понадобится
5 действий (K+1) в худшем случае. А значит, добавление в конец списка будет работать
за линейное время всегда. Такая структура, по-моему, удовлетворяет условиям, но будет
занимать больше памяти.

Как хранятся структуры в памяти?

#cpp #память #структуры

Прочитал, что поля структуры хранятся в памяти последовательно(в порядке объявления)
(+- платформ.зависимое выравнивание). Вопрос такой: как влияют методы в структурах
на их расположение в памяти?
Предположим, есть структура вида:

struct my_Struct{
double n;
void meth();
char ch;
    }


Как экземпляр этой структуры (а именно его поля) будут расположены в памяти? 
И ещё, применимы ли все знания по структурам(и их расположению в памяти) к классам?
И есть ли какая-то разница (с точки зрения памяти) между обычными методами и перегрузками
/ конструкторами / деструкторами?
    

Ответы

Ответ 1

Во-первых, как правильно заметили в комментариях, в С++ структур нет. Ключевое слово
struct создает классы, в которых поля и родители по умолчанию публичные.
Какой-то другой разницы между struct и class, с точки зрения стандарта, насколько
я знаю, нет. 



Поля классов хранятся в порядке объявления только если спецификатор доступа (public/private/protected)
у них одинаковый.

Если спецификатор доступа одинаковый, то из двух полей в памяти идет раньше то, которое
в определении класса написано выше. Если спецификатор доступа у двух полей разный,
то компилятор вправе расположить их относительно друг друга как угодно.

В частности, соответствующий стандарту компилятор может располагать все поля в памяти
по порядку, игнорируя спецификаторы доступа. А может сложить в кучку отдельно private,
protected и public. Могут быть какие-то другие варианты.

Пруф: [class.mem]/19


  Non-static data members of a (non-union) class with the same access control are
allocated so that later members have higher addresses within a class object. The order
of allocation of non-static data members with different access control is unspecified.
Implementation alignment requirements might cause two adjacent members not to be allocated
immediately after each other; so might requirements for space for managing virtual
functions and virtual base classes.




У каждого экземпляра одного класса, очевидно, свой набор из всех нужных полей.

Но вот методы у всех экземпляров одного класса общие - они не занимают место в экземплярах
класса и не влияют на его размер в байтах.*
(Не считая указателя на vtable для виртуальных функций.)

Обычно методы реализуются так же, как и обычные функции, но с добавленным невидимым
параметром this. Так что нет смысла в каждом экземпляре хранить какую-то информацию
о методах, не считая vtable pointer.



*Хотя разницы между class и struct быть не должно, и хотя не виртуальные методы на
размер класса влиять не должны, мне у нас на SO недавно попался пример, в котором GCC
с определенными настройками убирал выравнивание из struct как только к нему добавляли
один любой метод, либо когда struct меняли на class. Видимо для совместимости с каким-то
С-шным компилятором. Если кто-то найдет больше информации по этой теме, буду благодарен.


Ответ 2

Методы никак не влияют на расположение в памяти (посмотреть). Методы априори не могут
занимать память объектов (методы ведь не создаются для каждого объекта отдельно). Метод
- (на низком уровне) это функция для которой просто передается указатель this с помощью
регистра процессора. Из ранее приведенной ссылки:


lea rax, [rbp-12] - взятие адреса объекта (начала последовательности байт принадлежащих
объекту) и помещение его в регистр. Далее метод будет работать как обычная функция,
зная, что в нужном регистре хранится указатель на текущий объект.


Различие между структурой и классом только в доступности по умолчанию: структуры
- public, классы - private (все члены по умолчанию имеют указанный спецификатор доступа)
(class).
Перегруженные функции - это разные функции (каждая из них имеет собственный адрес).
Какая именно функция будет вызвана компилятор решит во время компиляции (в отличии
от виртуальных методов). Посмотреть.

Классы против структур

#структуры #code_style #cpp

Стоит ли в своих кодах C++ использовать структуры? Я так понимаю структуры это пережитки
языка С. С одной стороны структуры в написании и использования проще классов но они
подрывают принципы ООП.
    

Ответы

Ответ 1

В Си++ основная разница между структурой и классом - это модификатор доступа, который
используется по умолчанию для их членов. Для классов, по умолчанию используется модификатор
private, а для структур - public. Конечно, принципы инкапсуляции структуры таким образом
подрывают, но классы, в свою очередь тормозят стадию проектирования, которая затрагивает
структурную эволюцию проекта.
Т.е., к примеру: выделить класс из структуры проще, чем из класса, т.к. для класса
придется пересматривать логику взаимодействия свойств, которые ранее были на одном
уровне доступа. Этот процеесс выливается в дописывание/переписывание методов, обеспечивающих
инкапсуляцию.
Все было бы хорошо, если бы на какой-то очередной стадии проектирования Вы вдруг
не осознаете, что порой ходите кругами, делая пустую работу, прикрывая тылы инкапсуляции.
С одной стороны, можно конечно занять позицию рецензора Си++ и следовать "букве закона
ООП", т.е. смириться с этой неизбежной бюрократией. Но с другой стороны - это ведь
Ваш проект, и Вы вправе строить его по своим законам, давая волю свободному проектированию
какого-то сложного класса на структурах, а его финальные версии закрепить на классах
по всем правилам ООП.


Ответ 2

Стоит ли в своих кодах C++ использовать структуры? 

По мере надобности да.

Я так понимаю структуры это пережитки языка С. 

нет.

С одной стороны структуры в написании и использования проще классов

и чем же они проще? struct длиннее class:) вот код для медитации:
#include 

using namespace std;
struct test {
  test() {
  // у структур есть конструктор
     q = 1;
     cout << "ctor" << endl;
  }

  ~test() {
     // и деструктор!
     cout << "dtor" << endl;
  }
  int get_q() {return q;}
private:
  // и даже приватная часть
  int q;
};

class mega:public test {
   // и от них можно наследоваться.

};

int main() {
   test t;
   cout << t.get_q() << endl;
   mega m;
   return 0;
}


но они подрывают принципы ООП.

нет. Просто по умолчанию в классах все приватное, а в  структурах - публичное. Но
это просто соглашение. Есть ещё пару мелочей.


Ответ 3

При правильном использовании структуры не нарушают принципов ООП. Применять их следует
для логического объединения данных, когда нет смысла, да и логического основания для
создания объектов. 
Например у нас есть картинка. Для сохраниения данных о ее размерах нам нет смысла
создавать класс. В этом случае гораздо лучше и удобнее использовать структуру, которая,
являясь членом класса "картинка", объединит в себе поля "высота" и "ширина". Чаще всего
эти данные будут требоваться нам вместе, поэтому и получать их у картинки будет логичнее
вместе.

Упорядоченный обход префиксного дерева

#алгоритм #структуры #дерево #структуры_данных

Существует префиксное дерево (нагруженное дерево, trie).


Дерево хранит в себе пару ключ/значение.
Необходимо реализовать упорядоченный обход дерева по значению, т.е. необходимо идти
от ветвей с наибольшим значением к ветвям с наименьшим.
Поскольку первая и вторая пары результирующего набора могут быть в противоположных
ветвях, то возникают сложности.

Обновление

Дерево никак не отсортировано. У каждого узла может быть бесконечно потомков. Думаю
хранить в каждом узле максимальное значение на этой ветви. И пытаться делать прицельный
обход.
    

Ответы

Ответ 1

Если вам нужно обходить дерево с максимального значения к минимальному я бы посоветовал
использовать двоичную кучу (двоичное дерево), где значение в любой вершине всегда больше
потомков.

При этом построение кучи O(2n*log n), добавление элемента O(log n)

Разница между вызовом методов класса и структур

#c_sharp #классы #структуры

Имеется такая ситуация

struct Point
{
   int x;
   int y;
   public void SetX(int a){ ...  }
   public void SetY(int a){ ...  } 
}
class A
{
   Point cord = new Point(); 
   public Point Cord      
   {
     get { return cord; }  
   }
   public void MethodA(int a)
   {
       cord.SetX(a);   //здесь все ок
   }
}

class B
{
   A myObj = new A();
   public Point Cord      
   {
     get { return cord; }  
   }
   public void MethodB(int a)
   {
       myObj.Cord.SetX(a);   //а здесь не присваивает значение
   }
}


В классе А метод отрабатывает верно, а в классе B нет( заходит в метод , где то чему
то значение присваивает , но в объекте myObj и в его поле cord типа Point нет)
Интересно чему все таки это значение присваивается и почему с классами работает,
а со структурой нет.
    

Ответы

Ответ 1

Потому что структура это ValueType и копируется полностью.

В результате вызова

get { return cord; } 


Будет новый объект структуры, в котором ты и вызываешь метод SetX.

Ключевое слово This и его применение в Классе\Пользовательской структуре

#c_sharp #net #классы #структуры #keyword

Я заметил,что семантика работы ключевого слова "this" в пользовательских структурах
и классах,кардинально отличается.
К примеру,в структуре мы можем сделать что то подобное :  

struct MyStruct
{
    int x,y;

    void Reset()
    {
        this = new MyStruct(); // удаляем предыдущую структуру и создаем новую О_О
    }
}  


Хотелось бы увидеть всю разницу ключевого слова This, между структурой и классом,а
так же узнать, что там твориться под капотом. 
    

Ответы

Ответ 1

Самое главное различие состоит в том, что переменная this для структурного типа должна
быть явно присвоенной в конструкторе структуры.

Переменная структурного типа, а this  для структур является переменной структурного
типа, считается явно присвоенной , если каждое из ее полей является явно присвоенным

Как это сказывается на структурах?

Это сказывается на работе конструкторов. Рассмотрите следующий пример объявления
структуры

struct EvenOdd
{
    int x, y;
    void make_even()
    {
        x &= ~0 << 1;
    }

    void make_odd()
    {
        y |= 1;
    }

    public EvenOdd( int x, int y )
    {
        this.x = x;
        make_even();
        this.y = y;
        make_odd();
    }
}


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


  Ошибка    CS0188  Невозможно использовать объект this, пока не будут
  назначены все его поля.


потому что в точке вызова метода make_even this еще не является явно присвоенной,
так как член данных структуры y еще не был инициализирован.

После выхода из конструктора переменная this считается явно присвоенной.

Вы можете сделать предыдущий конструктор структуры валидным посредством предварительного
вызова конструктора по умолчанию

    public EvenOdd( int x, int y ) : this()
    {
        this.x = x;
        make_even();
        this.y = y;
        make_odd();
    }


В этом случае внутри тела конструктора с параметрами переменная this уже будет явно
присвоенной.

Если же вы измените это объявление на объявление класса, то никаких проблем с this,
где this уже не переменная, а значение, не будет, и данный класс будет успешно компилироваться.

class EvenOdd
{
    int x, y;
    void make_even()
    {
        x &= ~0 << 1;
    }

    void make_odd()
    {
        y |= 1;
    }

    public EvenOdd( int x, int y )
    {
        this.x = x;
        make_even();
        this.y = y;
        make_odd();
    }
}


Ответ 2

Я думаю, лучше чем спецификация языка вам никто не ответит. (Кстати, спецификация
находится на вашем компьютере, \VC#\Specifications\1033\CSharp Language
Specification.docx.)

Переведу раздел 7.6.7.


  Доступ через this разрешён лишь в теле нестатических конструктора, метода или акцессора
[это геттер или сеттер — VladD]. Смысл this таков:
  
  
  При использовании внутри нестатического конструктора класса this расценивается
как значение. Тип этого значения есть тип [экземпляра] (см. §10.3.1) класса, в котором
происходит использование, и значение есть ссылка на конструируемый объект.
  При использовании внутри нестатического метода или акцессора this расценивается
как значение. Тип этого значения есть тип [экземпляра] (см. §10.3.1) класса, в котором
происходит использование, и значение есть ссылка на объект, у которого был вызван метод
или акцессор.
  При использовании внутри нестатического конструктора структуры this расценивается
как переменная. Тип этой переменной есть тип [экземпляра] (см. §10.3.1) структуры,
в которой происходит использование, и значение представляет конструируемую структуру.
Переменная this в конструкторе [экземпляра] структуры ведёт себя в точности как out-параметр
того же типа; в частности, это означает, что переменная должна быть гарантировано инициализирована
на любом пути выполнения конструктора.
  При использовании внутри нестатического метода или акцессора this расценивается
как переменная. Тип этой переменной есть тип [экземпляра] (см. §10.3.1) структуры,
в которой происходит использование.
  
  
  Если метод или акцессор не является итератором (см. §10.14), переменная this представляет
структуру, для которой метод или акцессор был вызван, и ведёт себя в точности как ref-параметр
данного типа.
  Если метод или акцессор является итератором, переменная this представляет копию
структуры, для которой метод или акцессор был вызван, и ведёт себя в точности как параметр
этого же типа, переданный по значению.
  
  


(Я немного упростил текст, убрав упоминание primary-expression.)



Видно, что для классов this представляет собой значение, а для структур — переменную.
Поэтому для структур можно осуществлять присвоение этой переменной.

Объясните этот синтаксис пожалуйста

#c #структуры

Нет, правда. Поверхностно я знаю C но это... новый синтаксис C99 наверное:

struct node {
    int payload;
    int height;
    struct node *kid[2];
} dummy = {0, 0, {&dummy, &dummy}}, *nnil = &dummy;
// internally, nnil is the new nul


Что вот это значит?:


Создать тип struct node node (оказывается имя типа всё-таки struct node) 
typedef struct node dumy Оказывается: объявить (глобальную?) переменную dummy содержащую
помимо прочего массив состоящий из двух указателей на саму себя
, => node* nnil = опять указатель на эту dummy


Я прав? Это шо за синтаксис такой? C99? (смайлик "я в ужасе")
    

Ответы

Ответ 1

struct node {


Объявили структуру

} dummy


Создали переменную типа struct node

= {0, 0,


Первые два поля переменной dummy - нули (dummy.payload = dummy.height = 0)

{&dummy, &dummy}}


Элементам массива kid (указателям) присвоили адреса переменной dummy (dummy.kid[0]
= dummy.kid[1] = &dummy)

, *nnil 


Создали ещё одну переменную - указатель на переменную типа struct dummy

= &dummy;


Присвоили ей адрес переменной dummy

Всё, никаких хитростей, чистый C безо всяких наворотов.


Ответ 2

В этой конструкции сразу же объявляется структура, объект этой структуры и указатель
на объект этой структуры.

Чтобы это объявление 

struct node {
    int payload;
    int height;
    struct node *kid[2];
} dummy = {0, 0, {&dummy, &dummy}}, *nnil = &dummy;


было более понятным, вы можете его разбить на несколько объявлений. Исходное объявление
эквивалентно следующим объявлениям.

struct node {
    int payload;
    int height;
    struct node *kid[2];
};

struct node dummy = {0, 0, {&dummy, &dummy}};
struct node *nnil = &dummy;


То есть объявляется структура с именем struct node. Затем объявляется объект этой
структуры с именем dummy и его поля, как объекта структуры, инициализируются соответствующими
значениями. Чтобы это объявление было еще более понятным, вы можете даже его переписать
в C99 как

struct node dummy = { .payload = 0, .height = 0, .kid = { [0] = &dummy, [1] = &dummy }};


В этом объявлении объекта dummy его член данных kid, который представляет собой массив
указателей, инициализируется адресом самого объекта dummy. 

И, наконец, в третьем объявлении объявляется указатель с именем nnil на объект dummy

Как называется контейнер хранящий N лучших элементов?

#массивы #структуры #терминология #любой_язык

У меня есть контейнер фиксированного размера содержащий упорядоченные элементы. В
конструкторе я передаю в него его максимальный размер и функцию сравнения. При добавлении
элемента, контейнер использует функцию сравнения и добавляет новый элемент к другим
элементам так, чтобы сохранить порядок от лучшего к худшему и, если достигнут предел,
выбрасывает худший элемент.

Есть ли у такого контейнера каноническое название (английский и русский термины) ?
    

Ответы

Ответ 1

На мой взгляд, канонического названия у такой структуры нет. В зависимости от задачи
она может иметь разные названия. Как примеры:


LRU Cache: в данной структуре данные упорядочиваются по частоте обращений к ним,
наименее используемые удаляются при достижении заданного размера кэша.
MRU Cache: такой же принцип, но в отличии от LRU вытесняется последний использованный
элемент.
EvictingQueue: структура данных из Guava, первый элемент очереди удаляется, если
очередь заполнена. Также есть MinMaxPriorityQueue.
CircularFifoQueue: структура данных из Apache Commons, заменяет старейший элемент,
если очередь заполнена.


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


Ответ 2

Для начала, я бы не стал называть такую структуру данных контейнером. От контейнера
ожидается, что он будет хранить все элементы а не только те, которые ему понадобятся.

По поводу же названия - встречается такая структура нечасто (по причине, изложенной
выше), и общеизвестного названия у нее нет. Я бы назвал ее "буфер лучших элементов".


Ответ 3

В C++ такого рода контейнер называется "очередь с приоритетом" std::priority_queue.
Правда, автоматического вытеснения, о котором упомянуто вопросе, при достижении максимального
размера не происходит. Такую функциональность можно достаточно легко реализовать самостоятельно.
Итоговый вариант можно было бы назвать "Очередь фиксированного размера с приоритетом"
(fixed_size_priority_queue).


Ответ 4

Может быть Circular buffer (кольцевой буфер)


Ответ 5

Я бы использовал обычный multi_set.

Как-то так:

multi_set  best;

if (best.size() < lim || x > *best.begin())
{
  best.insert(x);
  if (best.size() > lim)
    best.erase(best.begin());
}

Структуры данных

#структуры

Какие виды структур данных бывают?(можете указать название структуры в определенном
языке программирования) Хочется узнать их предназначение, сильные и слабые стороны.
Так же интересует классификация, верно ли в вики написано? Список структур данных Развернутый
ответ пока каждой структуре не нужен, просто кратко, для примера рассказать в чем преимущество
этой структуры перед остальными(например самое быстрое время доступа к элементу, способность
динамически менять объем памяти и т.д.)
Может на всё сразу не стоит отвечать, вдруг объем ответа будет значительным, хотя
бы по одной из структур которую хорошо знаете можете отписаться, а я буду добавлять
в основной пост информацию. Очень удобно будет иметь перед глазами такой список, сразу
по нему сверился и выбрал нужное.
1. Линейные структуры данных – это структуры данных, в которых переход от одного
элемента данных к другому не зависит от каких-либо логических условий, т.е. в линейных
структурах используются лишь безусловные связи элементов.
1.1 Список Может всё то же самое, что и массив, но позволяет добавлять элементы в
любое место, удалять элементы из любого места и получать текущее количество элементов.
1.2 Ассоциативный массив
1.3 Хеш-таблица - это обычный массив с необычной адресацией, задаваемой хеш-функцией.
Лучший выбор, если не нужна сортировка информации, а только быстрый доступ к ней.
Тратится дополнительная память.
преимущества:

Важное свойство хеш-таблиц состоит в том, что, при некоторых разумных допущениях,
все три операции (поиск, вставка, удаление элементов) в среднем выполняются за время
O(1), время для наихудшего случая - O(n).

недостатки:

Итерация не в порядке возрастания ключей
Необходимость «перехеширования» при увеличении числа хранимых объектов (?) 
нельзя реализовать быстро работающие дополнительные операции MIN, MAX и алгоритм
обхода всех хранимых пар в порядке возрастания или убывания ключей (?) 
не поддерживает упорядоченности, и не сохраняет порядок следования элементов (?)
возможность коллизий

реализация:

C#: Hashtable

1.4 Стек Набор элементов одного типа, упорядоченных таким образом, чтобы добавлять
и доставать элементы можно было только с одного конца. Операции: добавить элемент в
стек, достать из стека последний добавленный элемент, проверить, является ли стек пустым.
1.5 Очередь Набор элементов одного типа, упорядоченных таким образом, чтобы добавлять
их можно было только в один конец, а получать - с другого конца. Операции: добавить
элемент в конец очереди, достать первый элемент из очереди, получение размера очереди.
1.5.1 Очередь с приоритетом
1.6 Дек - особый вид очереди. Дек (от англ. deq - double ended queue,т.е очередь
с двумя концами) - это такой последовательный список, в котором как включение, так
и исключение элементов может осуществляться с любого из двух концов списка. Частный
случай дека - дек с ограниченным входом и дек с ограниченным выходом.
поддерживаемые операции:

включение элемента справа; 
включение элемента слева;
исключение элемента справа;
исключение элемента слева;
определение размера;
очистка.

1.7 Буферное окно
2. Граф
2.1 Список рёбер
2.2 Деревья
2.2.1 2-3-дерево
2.2.2 Дерево отрезков
2.2.3 Красно-чёрное дерево
2.2.4 BSP-дерево
2.2.5 B-дерево 
Основное предназначение: B-дерево предназначено для хранения информации на жёстком
диске. Время произвольного доступа к жёсткому диску очень велико (миллисекунды), поскольку
оно определяется скоростью вращения диска и перемещения головок. Поэтому важно уменьшить
количество узлов, просматриваемых при каждой операции, то есть высоту дерева, что достигается
путём высокой ветвистости.
преимущества:

Во всех случаях полезное использование пространства вторичной памяти занимает свыше
50 %. С ростом степени полезного использования памяти не происходит снижения качества
обслуживания.
Произвольный доступ к записи реализуется посредством малого количества подопераций
(обращения к физическим блокам).
В среднем достаточно эффективно реализуются операции включения и удаления записей;
при этом сохраняется естественный порядок ключей с целью последовательной обработки,
а также соответствующий баланс дерева для обеспечения быстрой произвольной выборки.
Неизменная упорядоченность по ключу обеспечивает возможность эффективной пакетной
обработки

недостатки: 

Основной недостаток В-деревьев состоит в отсутствии для них средств выборки данных
по вторичному ключу.

2.2.6 Двоичное дерево поиска
2.2.6.1 Самобалансирующееся дерево поиска
2.2.6.1.1 АВЛ-дерево
2.2.6.1.1.1 Дерево Фибоначчи
2.2.6.1.2 Красно-чёрное дерево
2.2.6.1.3 Расширяющееся дерево
2.2.7 Куча
2.2.7.1 Двоичная куча 
2.2.7.2 Биномиальная куча 
2.2.7.3 Фибоначчиева куча 
2.2.7.4 Сливаемая куча 
2.2.8 Суффиксное дерево
2.2.8 Префиксное дерево 
Существует еще следующее разделение структур:
Статические структуры данных
Полустатические структуры данных
Динамические структуры данных
Нелинейные структуры данных
источник
общий вид описания структур:
-основное предназначение, описание
-поддерживаемые операции
-преимущества
-недостатки
-готовая реализация в языке программирования (название функции или класса)
условные обозначения
(?) - под сомнением, поправьте пожалуйста если вдруг неправильно написано или наоборот
утвердите чтобы исключить неоднозначность.
редактирование продолжается..    

Ответы

Ответ 1

Массив. Набор фиксированного количества элементов одного типа, имеющий возможность
прочитать или записать элемент по индексу.
Список. Может всё то же самое, что и массив, но позволяет добавлять элементы в любое
место, удалять элементы из любого места и получать текущее количество элементов.
Множество. Неупорядоченный набор элементов одного типа, каждый из которых может встречаться
в множестве не более одного раза. Основные операции над множеством: добавление элемента
в множество, удаление элемента из множества, проверка наличия элемента в множестве,
получение размера множества.
Словарь. Неупорядоченный набор элементов двух типов, в котором каждый элемент первого
типа связан с одним элементом второго типа, и каждый элемент первого типа (ключ) может
встречаться в словаре не более одного раза. Основные операции над словарём: добавление
пары "ключ-значение", удаление пары по ключу, проверка наличия ключа в словаре, получение
значения по ключу, получение количества пар "ключ-значение".
Очередь. Набор элементов одного типа, упорядоченных таким образом, чтобы добавлять
их можно было только в один конец, а получать - с другого конца. Операции: добавить
элемент в конец очереди, достать первый элемент из очереди, получение размера очереди.
Стек. Набор элементов одного типа, упорядоченных таким образом, чтобы добавлять и
доставать элементы можно было только с одного конца. Операции: добавить элемент в стек,
достать из стека последний добавленный элемент, проверить, является ли стек пустым.


Ответ 2

Тема слишком всеобъемлющая для одного ответа, так что была найдена очень полезная
статья, предлагаю ознакомиться:
Обзор наиболее часто используемых структур данных.

Статический конструктор структуры C#

#c_sharp #структуры #конструктор

Существует ли различие между статическими конструкторами структур и классов и их
вызовами в C#?
    

Ответы

Ответ 1

Есть довольно известное заблуждение, будто статические конструкторы не работают для
структур. Но это не так. просто они срабатывают несколько иначе, нежели для классов. 
Разница например вот в чем: у ссылочных типов (классов в том числе) статический конструктор
вызывается перед первым созданием экземпляра класса. У структур он вызывается при обращении
к статическим членам структуры. Пример: 

struct Foo 
{
    static Foo() 
    {
        Console.WriteLine("from static Foo");
    }   
    public static int Bar = 10;
}

class  FooClass 
{
    static FooClass() 
    {
        Console.WriteLine("from static FooClass");
    }   
    public static int Bar = 10;
}

// перед созданием экземпляра вызовется статический конструктор, 
//который напечатает текст "from static FooClass"
var fooCl = new FooClass();

// а здесь статический конструктор вызван не будет
var foo = new Foo(); // 
// он будет вызван здесь, если раскомментировать следующую строку
//Foo.Bar = 11;  


А теперь небольшое объяснение этому колдунству. Дело в том, что типы-значения в C#
(и структуры в том числе)  имеют массу отличий от ссылочных типов (в том числе классов).
Одним из таких отличий является работа конструктора по умолчанию. Для структур в целях
сохранения быстродействия  (если не ошибаюсь) при вызове конструктора по умолчанию
выполняется инициализация всех полей значениями по умолчанию. Соответственно, создания
экземпляра как такового не происходит, тогда как статический конструктор вызывается
при первом инстанцировании экземпляра. Но если добавить структуре какой-либо конструктор
с аргументами (добавить свой конструктор по умолчанию не получится) и создать экземпляр
структуры через этот конструктор, то вызов статического конструктора произойдёт. Пример: 

struct Foo 
{
    static Foo() 
    {
        Console.WriteLine("from static Foo");
    }   

    public Foo(int i) { }                  
}

// здесь произойдёт вызов статического конструктора, 
// так как происходит "обычное" создание экземпляра
var foo = new Foo(1);

Пользовательская структура как точка входа в программу

#c_sharp #память #структуры #clr

Может ли быть пользовательская структура быть точкой входа (main entry) в программе?  

Вопрос риторический, ибо насколько мне показывает IDE, такое возможно(т.е. достаточно
создать Main метод,и все пройдет на ура).  

Но отсюда вытекает иной вопрос - а чем это чревато и считается ли это дурным тонном!?  
    

Ответы

Ответ 1

точкой входа в программу в языке C# является метод Main. Этот метод обязан быть статическим.
Статические элементы класса или структуры, являются самостоятельными программными единицами,
не требуют наличия экземпляра для вызова и, фактически, используют имя класса или структуры
в которой объявлены только для расширения собственного имени и обеспечения его уникальности.
Статические члены не наследуются, не могут быть абстрактными или виртуальными,  вы
можете даже писать полностью в процедурном стиле, используя только статические классы
и их элементы. 

Структура - это по сути класс, но с ограниченными возможностями, в котором на уровне
языка запрещено использовать некоторые принципы ООП (запрещено наследование от других
классов или структур, но реализация интерфейсов разрешена, остальное - следствия).
Ну и да, структуры относятся к ValueType, что накладывает еще некоторые ограничения,
но, в то же время, дает возможности недоступные классам. Однако по части статических
элементов - структуры ни чем от классов не отличаются, разве что сама структура не
может быть статической.

Поэтому, с точки зрения CLR, нет никакой разницы, к чему будет привязан метод Main,
и никаких последствий от такой замены не будет. Другой вопрос. как вы будете использовать
этот класс или структуру в дальнейшем, но это уже действительно другой вопрос.

Зачем typedef объвлять с одним и тем же типом

#c #структуры #объявление #typedef

Наверно какие-то C-шные ухищрения. Навроде их классов. Вроде бы и объявление тут
уже есть. Может поэтому? Вот такая строка например (из OpenCV):

typedef struct CvFileStorage    CvFileStorage;


Зачем же так писать? Не нашел никак, сходу, ответ на это. Когда-то (несколько лет
назад), помню что читал об этом. Тогда чистый C был в моде наверное, а сейчас такое
позабыто получается. Еще подобное видел в коде от Windows CE6 и др. Это запомнил:),
а для чего нужно не помню никак. Если еще какие-то доп. куски кода надо привести, то
скажите. Эта строка стоит перед структурой, которая у себя где-то в поле использует
тип из этого typedef-а. Но зачем так писать, а не просто объявить его? Спасибо.
    

Ответы

Ответ 1

Имеется по крайней мере две веские причины объявить этот typedef.

typedef struct CvFileStorage    CvFileStorage;


Первая причина заключается в том, что в C программах вы должны указывать ключевые
слова struct или enum перед именем структуры или перечисления. Это выглядит обременительно
при вводе кода. Очень часто программисты забывают указать эти слова, что приводит к
появлению ошибки компиляции. Поэтому этот typedef упрощает жизнь программистам, позволяя
им не писать эти ключевые слова перед именем структуры или перечисления.

Вторая причина состоит в том, что имена структур и другие идентификаторы находятся
в различных пространствах имен. Поэтому одно и то же имя можно использовать для объявления
структуры и обычной переменной. Например, следующий фрагмент кода является корректным

struct CvFileStorage
{
    //...
};


int CvFileStorage;


В этом фрагменте кода объявляется структура с именем CvFileStorage и переменная типа
int с тем же самым именем. Эти объявления не конфликтует друг с другом, так как, как
уже было написано, перед именем структуры обязательно должно следовать ключевое слово
struct . 

В C вы можете записать, к примеру

struct CvFileStorage
{
    int CvFileStorage;
} CvFileStorage;


Это объявление корректно, так как эти три совпадающих идентификаторs находятся в
различных пространствах имен.

Однако это может вводить в заблуждение читающих код, так как если программист по
ошибке опустит ключевое слово struct перед именем структуры, то может оказаться, что
код по-прежнему с точки зрения синтаксиса языка будет корректным, хотя на самом деле
имелась в виду структура, а не переменная с таким же именем.

Например, в данном выражении программист по невнимательности забыл указать ключевое
слово struct, и тем не менее получил корректное выражение, так как имеется переменная
с таким же именем

sizeof( CvFileStorage )


Чтобы избежать такой путаницы также целесообразно резервировать это имя без ключевого
слова struct  для имени структуры, используя typedef.. 

В С++ ключевое слово struct можно опускать при обращении к структуре. Тогда возникает
вопрос: а как быть с тем, что в C можно объявлять переменную или функцию с таким же
имеенем как имя структуры?

Этот вопрос решается следующим образом: имя переменной или имя функции скрывает объявление
структуры с тем же самым именем. Поэтому при обращении к структуре надо указывать уточненное имя.

Например,

struct CvFileStorage
{
    //...
};

void CvFileStorage();


В этом фрагменте кода объявление функции скрывает объявление одноименной структуры.
 Поэтому если, например, вы хотите объявить объект этой структуры, то надо будет указывать
уточненное имя структуры.

struct CvFileStorage obj;


Или, например, можно написать такие объявления

struct CvFileStorage
{
    //...
};

void CvFileStorage( struct CvFileStorage );


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


Ответ 2

В с++ если нужно объявить переменную типа структуры, нужно просто написать имя типа
и переменную. В чистом си это не так. И нужно всегда писать struct. Это все потому,
что типы для структур и остальные типы как бы находятся в разных областях видимости.
Но так как программисты существа ленивые, то лучше один наз написать

typedef struct CvFileStorage    CvFileStorage;


и потом не задумываться, почему оно не компилируется (потому что забыли struct) или
почему оно работает как то странно (потому что забыли struct, а кто то объявил свой
тип не структуру с таким же именем).

Но часто пишут ещё интереснее:

typedef struct {

// тут объявление структры
} struct_name;


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


Ответ 3

Без этого typedef при любом упоминании структуры CvFileStorage надо писать полностью:

struct CvFileStorage  cv;
void func(struct CvFileStorage* cv);


и так далее. При наличии объявления typedef слово struct можно выбрасывать:

CvFileStorage  cv;
void func(CvFileStorage* cv);

Двоеточие в полях структуры

Объясните, пожалуйста, как тут создается структура? Что делает знак двоеточие :?

/**
 * @brief Bit-field structure of the state of the packet reception
 */
typedef struct{
    uint32_t Length         :16;        /*!< The number of bytes in the packet including header and CRC. */
    uint32_t PF_ERR         :1;         /*!< A sign package PAUSE. */
    uint32_t CF_ERR         :1;         /*!< A sign Management Pack (filtering by MAC and special tags in the field length - 13.14 - octets). */
    uint32_t LF_ERR         :1;         /*!< A sign excess packet length 1518 octets. */
    uint32_t SF_ERR         :1;         /*!< A sign of lack of packet length 64 octets. */
    uint32_t LEN_ERR        :1;         /*!< A sign mismatch between the actual length and the length specified in the length field - 13.14 octets. */
    uint32_t DN_ERR         :1;         /*!< A sign bit of the packet is not a multiple of 8. */
    uint32_t CRC_ERR        :1;         /*!< A sign mismatch packet CRC. */
    uint32_t SMB_ERR        :1;         /*!< A sign of the presence in the packet error nibbles. */
    uint32_t MCA            :1;         /*!< A sign group package (MAC matches HASH). */
    uint32_t BCA            :1;         /*!< A sign of the broadcast packet (MA
= FF:FF:FF:FF:FF:FF). */
    uint32_t UCA            :1;         /*!< A sign individual package (MAC corresponds to the set). */
}ETH_StatusPacketReceptionBitFileds;

    

Ответы

Ответ 1

В названии самой структуры ETH_StatusPacketReceptionBitFileds присутствует словосочетани
BitFileds. Эта структура задает битовые поля, то есть более компактную форму запис
целочисленных членов данных структуры, так как заранее известно, что эти члены данных будут хранить ограниченные значения, и для их представления достаточно выделить несколько битов.

Например, вы могли бы определить эту структуру следующим образом:

typedef struct{
    uint32_t Length;        /*!< The number of bytes in the packet including header and CRC. */
    uint32_t PF_ERR;         /*!< A sign package PAUSE. */
    //...
}ETH_StatusPacketReceptionBitFileds;


Но в таком случае каждый член данных структуры занимал бы память в 32 бита, или 
байта. А если известно, например, что член данных структуры PF_ERR может принимать тольк
два значения 0 или 1, то будет расточительно хранить эти значения в члене данных, имеющи
32 бита, так как для представления 0 или 1 достаточно всего лишь одного бита. Поэтому структура определяется как структура с битовыми полями с заданным количеством битов. Эти битовые поля упаковываются компилятором в объекты, как указано в объявлении битовых полей структуры, типа 
uint32_t. То есть в принципе в одном объекте данного типа может быть упаковано 32 битовых поля размером в 1 бит. Это экономит память, выделяемую под объекты структуры.

Из стандарта C++ (9.6 Bit-fields [class.bit])


  1 A member-declarator of the form


identifieropt attribute-specifier-seqopt: constant-expression



  specifies a bit-field; its length is set off from the bit-field name
  by a colon.,,,
  Bit-fields are packed into some addressable allocation unit.


Ответ 2

После двоеточия для члена структуры задается размер этого члена в битах. Т.е. тако
член является битовым полем. В основном это используется для упаковки данных и при этом сохранения удобного доступа на изменение и чтения значения.
При этом для битового поля запрещена операция взятия адреса.

Собственно в комментарии к структуре уже содержится ответ:


Bit-field structure ...