Где почитать про структуры данных?

pitrik2

Посоветуйте какой-нибудь сайт, где можно почитать про разные структуры данных.
Нужно именно не алгоритмы, а структуры.
Целевой язык с++, но наверное подойдёт любой похожий язык.
Идеально чтобы там было: название структуры, её описание, примеры где может использоваться, псевдо-код или даже с++ код, а также указание где она уже реализована: например в бусте, в с++11 или в gcc extensions.
Вариант использования 1: Часто бывает что ищу структуру, а названия не знаю. Гугл нифига не помогает. Надеюсь на таком сайте быстро находить.
Вариант использования 2: Буду почитывать сайт для общего развития. Сколько лет программирую, а всё велосипеды выдумываю.
Вот пример, что прям щас ищу и никак не найду в гугле: структура, которая хранит два указателя на область памяти где лежит строка: на её начало и конец.
что-то типа такого

class <No idea how this pattern is called>String

{

    char* begin;

    char* end;



    ctr(char* begin, char* end) : begin(_begin end(_end) {}

    ctr(char* begin, size_t len) : begin(_begin end(_begin + len) {}

    ctr(string& str) : begin(str.c_str end(begin + str.length {}

};

    

evgen5555

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

а какая у этой структуры мотивация?

Dasar

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

чем это отличается от стандартной структуры: строка, хранящая свою длину отдельным полем?

Serab

ну наверное резать строки без доп. выделений памяти.

pitrik2

а какая у этой структуры мотивация?

эээ, такая же как у обычного std::string?
сишные строки char* не хранят длину строки, операции типа strlen(str) занимают много времени
хранить отдельно size_t len не удобно, такую пару фиг положишь в контейнер, а также фиг скормишь оператору
один из примеров когда это удобно:

const char* str = "Life is inevitable. Death is inevitable. Our choices remain inevitable.";

std::vector<MyString> tokens;

tokenize(str, '.', tokens);

std::cout << "Third sentence is: " << tokens[2] << std::endl;

evgen5555

так после деления строки ж будут не эквивалентны оригиналу

pitrik2

чем это отличается от стандартной структуры: строка, хранящая свою длину отдельным полем?

эээ
1. там выделяется лишняя память
2. у нее тяжелое создание - делается strcpy
2. когда ту структуру будешь менять, оригинальная не изменится

pitrik2

какая у этой структуры мотивация?

чем это отличается от стандартной структуры: строка, хранящая свою длину отдельным полем?

ребят
собстна я про это топик и завёл: ищу сайт где будет написано что хорошего в той или иной структуре

Serab

нэ понэл. Типа неизменяемые строки обычно внутри так и устраивают, чтобы можно было вырезать. Изменяемые тоже можно, но тяжелее: copy on write надо делать.

Dasar

> 1. там выделяется лишняя память
памяти выделяется столько же, сколько в твоем примере
> 2. у нее тяжелое создание - делается strcpy
можно делать копирование, можно не делать
> 2. когда ту структуру будешь менять, оригинальная не изменится
у структуры "строка с длиной" - всё тоже самое

evgen5555

ну там констов нету нигде, сбивает с толку
я согласен про неизменяемую строку, но мы далеко в лес ушли

pitrik2

> 1. там выделяется лишняя память
памяти выделяется столько же, сколько в твоем примере
> 2. у нее тяжелое создание - делается strcpy
можно делать копирование, можно не делать
> 2. когда ту структуру будешь менять, оригинальная не изменится
у структуры "строка с длиной" - всё тоже самое

я начинаю сомневаться что я тебя понимаю...
"строка с длиной" - это ты так называешь std:string?

Dasar

"строка с длиной" - это ты так называешь std:string?

std:string один из вариантов сложной реализации структуры "строка с длиной".
под свои задачи можно сделать более простую реализацию.

pitrik2

std:string один из вариантов сложной реализации структуры "строка с длиной".
под свои задачи можно сделать более простую реализацию.

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

Dasar

Я о том, что "строка с длиной" намного более изученный и обкатанный вариант.
При этом "строка с длиной" в один один делает тоже самое, что и структура из начального поста.
ps
так же строка с длиной создает меньше возможностей для катастрофических ошибок, чем два указателя. Неверно переданная длина создает проблему много меньше, чем когда begin и end взяты от разных строк.

pitrik2

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

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

Maurog

Вариант использования 1: Часто бывает что ищу структуру, а названия не знаю. Гугл нифига не помогает. Надеюсь на таком сайте быстро находить.
Вариант использования 2: Буду почитывать сайт для общего развития. Сколько лет программирую, а всё велосипеды выдумываю.

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

elenangel

ы?

 std::pair<std::string::iterator, std::string::iterator> 

karkar

По идее, такая пара итераторов begin/end называется range.
Вот тут душеполезная статья о них:
http://www.informit.com/articles/printerfriendly.aspx?p=1407...