Подскажите с STL

[Вад]

С помощью reverse_iterator - можно. Но задом наперёд тогда, надо думать.

[Алексей++]

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

[Вад]

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

[Алексей++]

туплю, подскажите , как проще сделать замену в 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();
}

[Антон (LogRus)]

Код: (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/

[Алексей++]

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

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

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

[Антон (LogRus)]

у меня копирований мало - фактически одно копирование
у тебя копирований много, т.е. каждый сдвиг это копирование всего, что после удаляемого элемента, а если представить, что строка сильно длинее 32/64 байт (т.е. кэш линии), то имеем все шансы каждым сдвигом разрушать кэш
что же касается вызова предиката, то т.к. это шаблон и всё такое, велик шанс, что он просто заинлайнится

[Алексей++]

у тебя копирований много, т.е. каждый сдвиг это копирование

у меня, вообще-то, всего одно копирование

Код:

stxt.erase(std::remove(stxt.begin(),stxt.end(),0),stxt.end());

но много замен символов нулями

Код:

std::fill(&stxt[pos1+1],&stxt[pos2],0);

[Антон (LogRus)]

Алексей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('-'));
 

[Алексей++]

я не согласное

1. несколько проходов по строке

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

2. очень сложный код

пытался сделать для скорости

[Антон (LogRus)]

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

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;
}

[Алексей++]

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

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

Добавлено через 3 минуты и 58 секунд:
кстати, мне входную строку сохранять не требуется, значит можно не remove_copy_if , а remove_if применить ?

[Антон (LogRus)]

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

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

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

[Алексей++]

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

[Антон (LogRus)]

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

[Алексей++]

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

[Ochkarik]

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

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

[Алексей++]

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

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

[Ochkarik]

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

Добавлено через 2 минуты и 23 секунды:
PS интересно.. а отчего оно не hread-safety? это же не модно?

[Алексей++]

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

[Антон (LogRus)]

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

[Ochkarik]

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

[Алексей++]

Вопрос:

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

[Вад]

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

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

[Алексей++]

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

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]

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

[Антон (LogRus)]

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

[Вад]

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

[Антон (LogRus)]

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

[Алексей++]

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

юмор оценил

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