Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: 1 2 3 [4] 5   Вниз
  Печать  
Автор Тема: Подскажите с STL  (Прочитано 103573 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #90 : 21-09-2010 18:17 » 

С помощью reverse_iterator - можно. Но задом наперёд тогда, надо думать.
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #91 : 21-09-2010 18:21 » 

да, но если поиск идёт не контейнерах, а в двух массивах ?
Записан

Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #92 : 22-09-2010 05:13 » 

По-моему, можно создать для массива reverse_iterator - но сам я так не делал Улыбаюсь Есть базовый класс iterator - по ссылке есть пример, как от него наследуются. Просто определить operator++, делающий --p - вот и reverse.
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #93 : 09-10-2010 21:53 » 

туплю, подскажите , как проще сделать замену в string всех определённых подстрок одним символом

в общем, хочется примерно такую же красоту, как в CString
Код:
CString txt="--11--1111-1-----111---11-";

//заменяем все идущие подряд тире на одно
while(txt.Replace("--","-")); //Replace возвращает не 0, если была замена

//txt=="-11-1111-1-111-11-";



Добавлено через 21 час:
вот так сделал
Код:
#include <algorithm>
#include <string>
//вернёт true, если было что-то удалено
static bool removeAllDups(std::string& stxt,const char ch)
{
char toremove_arr[3]={ch,ch,0};
DWORD pos1=0;
DWORD pos2=0;

//заменяем идущие подряд ch на одни+нули вместо повторов
pos1=0;
while((pos1=stxt.find(toremove_arr,pos1))!=std::string::npos)
{
pos2=stxt.find_first_not_of(ch,pos1+2);
if(pos2==std::string::npos)
{
pos2=stxt.size();
}

std::fill(&stxt[pos1+1],&stxt[pos2],0);
pos1=pos2;
}
DWORD dwdPrevSize=stxt.size();
stxt.erase(std::remove(stxt.begin(),stxt.end(),0),stxt.end());
return dwdPrevSize!=stxt.size();
}
« Последнее редактирование: 10-10-2010 20:01 от Алексей1153 » Записан

Антон (LogRus)
Глобальный модератор

ru
Offline Offline
Пол: Мужской
Внимание! Люблю сахар в кубиках!


WWW
« Ответ #94 : 11-10-2010 03:50 » 

Код: (C++)
string RemoveDups(const string & s, char ch)
{
     string res;
     res.resize(s.size());
     size_t pos = 0;
     bool write_char = true;
     for(size_t i = 0; s.size() != i; ++i)
     {
          if (s[i] != ch || write_char)
          {
                res[pos++] = s[i];
                write_char = s[i] != ch;
          }
     }
     res.resize(pos);
     return res;
}
так по проще будет Улыбаюсь
или вот так
http://cplusplus.com/reference/algorithm/remove_copy_if/


Записан

Странно всё это....
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #95 : 11-10-2010 04:10 » 

Антон (LogRus), а как насчёт скорости ? У тебя много копирований

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

на практике эксперименты ставить сейчас некогда, потом попробую )
Записан

Антон (LogRus)
Глобальный модератор

ru
Offline Offline
Пол: Мужской
Внимание! Люблю сахар в кубиках!


WWW
« Ответ #96 : 11-10-2010 04:30 » 

у меня копирований мало - фактически одно копирование
у тебя копирований много, т.е. каждый сдвиг это копирование всего, что после удаляемого элемента, а если представить, что строка сильно длинее 32/64 байт (т.е. кэш линии), то имеем все шансы каждым сдвигом разрушать кэш
что же касается вызова предиката, то т.к. это шаблон и всё такое, велик шанс, что он просто заинлайнится
« Последнее редактирование: 11-10-2010 04:32 от Антон (LogRus) » Записан

Странно всё это....
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #97 : 11-10-2010 04:40 » new

у тебя копирований много, т.е. каждый сдвиг это копирование
у меня, вообще-то, всего одно копирование
Код:
stxt.erase(std::remove(stxt.begin(),stxt.end(),0),stxt.end());

но много замен символов нулями
Код:
std::fill(&stxt[pos1+1],&stxt[pos2],0);
Записан

Антон (LogRus)
Глобальный модератор

ru
Offline Offline
Пол: Мужской
Внимание! Люблю сахар в кубиках!


WWW
« Ответ #98 : 11-10-2010 05:05 » 

Алексей1153++, угу Улыбаюсь что-то я забыл как работает remove
ну тогда последние аргументы против
1. несколько проходов по строке
2. очень сложный код

Код: (C++)
struct Pred {
    bool write;
    char examl;
    Pred(char ch) : write(true), exampl(ch) {}
    bool operator()(const char c) {
        bool res = c != examl || write;
        write = c != examl;
        return res;
    }
}

string result = remove_copy_if(s.begin(), s.end(), Pred('-'));
 
Записан

Странно всё это....
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #99 : 11-10-2010 05:31 » 

я не согласное
Цитата
1. несколько проходов по строке
их как бы всего один Улыбаюсь Иду по строке, засекаю начало цепи одинаковых чаров, и со второго заменяю на нули. Потом дальше

Цитата
2. очень сложный код
пытался сделать для скорости
Записан

Антон (LogRus)
Глобальный модератор

ru
Offline Offline
Пол: Мужской
Внимание! Люблю сахар в кубиках!


WWW
« Ответ #100 : 11-10-2010 05:41 » 

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

1. это всё равно 2 прохода, кэш будет лишний раз обновлятся
2. не помогло, последний вариант, отработал за 3.5 секунды против 5.5 секунды в твоём варианте Улыбаюсь

UPD: Попробовал на длинных строках (36 раз длинее) результат еще более плачевный 31 против 78

Код: (C++)
#include <iostream>
#include <sys/time.h>

unsigned long GetTickCount() {
    timeval t;
    gettimeofday(&t, NULL);
    return t.tv_sec*1000 + t.tv_usec/1000;
}

static bool removeAllDups(std::string& stxt,const char ch)
{
        char toremove_arr[3]={ch,ch,0};
        size_t pos1=0;
        size_t pos2=0;
   
        //заменяем идущие подряд ch на одни+нули вместо повторов
        pos1=0;
        while((pos1=stxt.find(toremove_arr,pos1))!=std::string::npos)
        {
                pos2=stxt.find_first_not_of(ch,pos1+2);
                if(pos2==std::string::npos)
                {
                        pos2=stxt.size();
                }
       
                std::fill(&stxt[pos1+1],&stxt[pos2],0);
                pos1=pos2;
        }
        size_t dwdPrevSize=stxt.size();
        stxt.erase(std::remove(stxt.begin(),stxt.end(),0),stxt.end());
        return dwdPrevSize!=stxt.size();
}

struct Pred {
    bool write;
    char ex;
    Pred(char ch) : write(true), ex(ch) {}
    bool operator()(const char c) {
        bool res = c != ex || write;
        write = c != ex;
        return res;
    }
};

void removeAllDups2(std::string& s,const char ch) {
    std::string::iterator it
        = std::remove_copy_if(s.begin(), s.end(), s.begin(), Pred(ch));
    s.resize(std::distance(s.begin(), it));
}

int main (int argc, char * const argv[]) {
    // insert code here...
    std::string s = "--11--1111-1-----111---11-";
    s = s + s + s + s + s;
    s = s + s + s + s + s;
    unsigned long begin = GetTickCount();
    for (size_t i = 0; i != 10000000; ++i) {
        std::string tmp = s;
        removeAllDups(tmp, '-');
    }
    unsigned long end = GetTickCount();
    std::cout << "res=" << (end - begin) << std::endl;
    std::string tmp = s;
    removeAllDups(tmp, '-');
    std::cout << tmp << "\n";
    return 0;
}
« Последнее редактирование: 11-10-2010 05:47 от Антон (LogRus) » Записан

Странно всё это....
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #101 : 11-10-2010 05:52 » 

ок, учтём ) Значит, предикат даёт преемущество

только там 25 копий, а не 36 вроде )

Добавлено через 3 минуты и 58 секунд:
кстати, мне входную строку сохранять не требуется, значит можно не remove_copy_if , а remove_if применить ?
« Последнее редактирование: 11-10-2010 05:56 от Алексей1153 » Записан

Антон (LogRus)
Глобальный модератор

ru
Offline Offline
Пол: Мужской
Внимание! Люблю сахар в кубиках!


WWW
« Ответ #102 : 11-10-2010 06:12 » 

да с умножением я что-то промахнулся

remove_if подойдёт, у меня он в сущности и используется Улыбаюсь есть если в remove_copy_if передать третьим параметром тоже что и в первый, то получишь remove_if, это я в коде с тупил

думаю преимущество даёт не столько предикат, сколько удаление самых тяжелых операция, т.е. чтение и запись памяти
Записан

Странно всё это....
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #103 : 11-10-2010 06:26 » 

а правильно ли я понимаю работу  remove_copy_if  - он всё, что подходит по условию, складывает в третий параметр (начиная с этого итератора то есть) , а из исходного ничего не удаляет ? Смущает "remove" в названии
Записан

Антон (LogRus)
Глобальный модератор

ru
Offline Offline
Пол: Мужской
Внимание! Люблю сахар в кубиках!


WWW
« Ответ #104 : 11-10-2010 06:32 » 

правильно
только предикат говорит, что удалять, а не оставлять Улыбаюсь
вот такой он не однозначный STL
Записан

Странно всё это....
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #105 : 11-10-2010 06:50 » 

а, ну тогда понятно. Криво назвали ))
Записан

Ochkarik
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #106 : 12-10-2010 10:11 » 

Народ, подскажите с STL - класс List.
он потокозащищенный?

ЗЫ c STL никогда не сталкивался - где искать - долго соображаю... а народ требует ответа)
Записан

RTFM уже хоть раз наконец!  RTFM :[ ну или хотя бы STFW...
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #107 : 12-10-2010 10:14 » 

Ochkarik, нет, в STL всё без межпоточной синхронизации

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

Ochkarik
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #108 : 12-10-2010 10:16 » 

Алексей1153++, сенькаю! собственно у человека и были такие подозрения)

Добавлено через 2 минуты и 23 секунды:
PS интересно.. а отчего оно не hread-safety? это же не модно?
« Последнее редактирование: 12-10-2010 10:19 от Ochkarik » Записан

RTFM уже хоть раз наконец!  RTFM :[ ну или хотя бы STFW...
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #109 : 12-10-2010 10:47 » 

Ochkarik, То ли Рома, Вад, то ли Антон говорили, что там всё по минимуму - для скорости. Синхронизация же не всегда нужна. Приделать можно всегда. Да и нет же в стандарте C++ кроссплатформенной синхронизации, в конце концов ))
Записан

Антон (LogRus)
Глобальный модератор

ru
Offline Offline
Пол: Мужской
Внимание! Люблю сахар в кубиках!


WWW
« Ответ #110 : 12-10-2010 11:12 » 

от себя дополню, в стандарте нет понятия поток и синхронизации между потоками тоже Улыбаюсь поэтому её нет и в STL
вообще некоторые реализации кое-что делают для работы в много поточной среде, но не защиту, а некоторые рюшки, что убрать неожиданное поведение, например, могут поставить volatile перед переменной или что-то в таком роде
для более детально изучения вопроса рекомендую глянуть в исходники STLport или борландвого STL, что в сущности одно и тоже
Записан

Странно всё это....
Ochkarik
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #111 : 12-10-2010 11:19 » 

Антон (LogRus), Алексей1153++, исчерпывающе)
Записан

RTFM уже хоть раз наконец!  RTFM :[ ну или хотя бы STFW...
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #112 : 15-02-2011 04:59 » 

Вопрос:

как наиболее просто найти в std::map<int,int> наименьший неиспользованный ключ в диапазоне [A,B)
Записан

Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #113 : 15-02-2011 06:10 » 

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

Самый простой способ, который я вижу: взять lower_bound(A) и upper_bound(B), и проитерироваться между ними, проверяя, есть ли где "дырка".
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #114 : 15-02-2011 06:30 » 

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

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

а насчёт upper_bound - не согласен. Судя по описанию, это тоже самое, что  lower_bound, только последний это >= , а первый - лишь больше
Цитата
lower_bound

Finds the position of the first element in an ordered range that has a value
 greater than or equivalent
 to a specified value, where the ordering criterion may be specified by a binary predicate.



upper_bound  

Finds the position of the first element in an ordered range that has a value
 that is greater than
a specified value, where the ordering criterion may be specified by a binary predicate.


Записан

Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #115 : 15-02-2011 06:56 » 

Алексей1153++, может в дополнение к map хранить vector или list неиспользуемых ключей? Улыбаюсь
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Антон (LogRus)
Глобальный модератор

ru
Offline Offline
Пол: Мужской
Внимание! Люблю сахар в кубиках!


WWW
« Ответ #116 : 15-02-2011 06:59 » 

Алексей1153++, возьми 2 раза lower_bound и пройдись от итератора до итератора
ну + всякие мелкие проверки, что они не указывают на конец и отсутсвие ключа
Записан

Странно всё это....
Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #117 : 15-02-2011 07:04 » 

Алексей1153++, да, разумеется, ошибся: для интервала a <= x < b нужно 2 lower_bound. А откуда лишние проверки? У тебя настолько маленький map, что быстрее от начала дошагать, чем за O(log(N)) получить lower_bound?
Записан
Антон (LogRus)
Глобальный модератор

ru
Offline Offline
Пол: Мужской
Внимание! Люблю сахар в кубиках!


WWW
« Ответ #118 : 15-02-2011 07:22 » 

второй lower_bound даже не нужен, ибо один фиг ты до итерируешься до него от первого, просто будет чуть другое условие выхода из цикла
Записан

Странно всё это....
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #119 : 15-02-2011 07:25 » 

Алексей1153++, может в дополнение к map хранить vector или list неиспользуемых ключей? Улыбаюсь
юмор оценил Ага

Вад, Антон (LogRus), мап небольшой, да и надо не часто. Я сделал простой пробег итератором (всё равно lower_bound то же самое делает)
Записан

Страниц: 1 2 3 [4] 5   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines